代码拉取完成，页面将自动刷新
同步操作将从 cyberdash/数据结构（C++模板实现） 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
/*!
* @file test.cpp
* @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
* @brief 线索树测试cpp文件
* @version 0.2.1
* @date 2021-05-13
*/
#include "inorder_threaded_binary_tree.h"
/*!
* @brief **结点访问函数**
* @param node 结点
* @note
* 结点访问函数
* ----------
* ----------
*/
void visit(ThreadedNode<int>* node) {
cout << node->data << " ";
};
/*!
* @brief **测试-中序线索树-获取子树首个线索节点**
* @note
* 测试-中序线索树-获取子树首个线索节点
* -------------------------------
* -------------------------------
*
* -------------------------------
* + **1 构造线索树**\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 打印线索树的首结点数据项**\n
* 获取根结点\n
* 对根结点调用First()\n
* 打印首结点数据项\n
*
*
* -------------------------------
*/
void TestInorderThreadedTreeFirst() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedBinaryTree First |"<<endl;
cout<<"| 测试-中序线索树-获取子树首个线索节点 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
InorderThreadedBinaryTree<int> inorder_threaded_tree; // 声明inorder_threaded_tree
int node_count = 7;
for (int i = 0 ; i < node_count; i++) { // 插入整数0至6
inorder_threaded_tree.InsertRecursive(i);
}
inorder_threaded_tree.CreateThreadRecursive(); // 调用CreateThreadRecursive构造线索
// ---------- 2 打印线索树的首结点数据项 ----------
ThreadedNode<int>* root = inorder_threaded_tree.Root(); // 获取根结点
ThreadedNode<int>* first = inorder_threaded_tree.First(root); // 对根结点调用First()
cout << "中序线索第一个线索节点 :" << first->data << endl; // 打印首结点数据项
cout<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
/*!
* @brief **测试-中序线索树-获取子树最后一个线索节点**
* @note
* 测试-中序线索树-获取子树最后一个线索节点
* -----------------------------------
* -----------------------------------
*
* -----------------------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 打印线索树的最后的结点数据项**\n\n
* 获取根结点\n
* 对根结点调用Last()\n
* 打印最后的线索结点数据项\n
*
*
* -----------------------------------
*/
void TestInorderThreadedTreeLast() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedBinaryTree Last |"<<endl;
cout<<"| 测试-中序线索树-获取子树最后一个线索节点 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
InorderThreadedBinaryTree<int> inorder_threaded_tree; // 声明inorder_threaded_tree
int node_count = 7;
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i); // 插入整数0至6
}
inorder_threaded_tree.CreateThreadRecursive(); //调用CreateThreadRecursive构造线索
// ---------- 2 打印线索树的最后的结点数据项 ----------
ThreadedNode<int>* root = inorder_threaded_tree.Root(); // 获取根结点
ThreadedNode<int>* last_node = inorder_threaded_tree.Last(root); // 对根结点调用Last()
cout << "中序线索最后一个线索节点: " << last_node->data << endl; // 打印最后的线索结点数据项
cout<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
/*!
* @brief **测试-中序线索树-下一个线索结点**
* @note
* 测试-中序线索树-下一个线索结点
* -------------------------
* -------------------------
*
* -------------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 打印线索树的前4个结点的数据项**\n\n
* 按线索顺序获取7个结点\n
* 打印7个线索结点的数据项\n
*
*
* -------------------------
*/
void TestInorderThreadedTreeNext() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedBinaryTree Next |"<<endl;
cout<<"| 测试-中序线索树-下一个线索节点 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
// 声明inorder_threaded_tree
InorderThreadedBinaryTree<int> inorder_threaded_tree;
// 插入整数0至6
int node_count = 7;
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i);
}
// 调用CreateThreadRecursive构造线索
inorder_threaded_tree.CreateThreadRecursive();
// ---------- 2 打印线索树的前4个结点的数据项 ----------
// 按线索顺序获取7个结点
ThreadedNode<int>* first = inorder_threaded_tree.First(inorder_threaded_tree.Root());
ThreadedNode<int>* second = inorder_threaded_tree.Next(first);
ThreadedNode<int>* third = inorder_threaded_tree.Next(second);
ThreadedNode<int>* forth = inorder_threaded_tree.Next(third);
ThreadedNode<int>* fifth = inorder_threaded_tree.Next(forth);
ThreadedNode<int>* sixth = inorder_threaded_tree.Next(fifth);
ThreadedNode<int>* seventh = inorder_threaded_tree.Next(sixth);
// 打印7个线索结点的数据项
cout << "中序线索树第1个线索节点: " << first->data << endl;
cout << "中序线索树第2个线索节点: " << second->data << endl;
cout << "中序线索树第3个线索节点: " << third->data << endl;
cout << "中序线索树第4个线索节点: " << forth->data << endl;
cout << "中序线索树第5个线索节点: " << fifth->data << endl;
cout << "中序线索树第6个线索节点: " << sixth->data << endl;
cout << "中序线索树第7个线索节点: " << seventh->data << endl;
cout<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
/*!
* @brief **测试-中序线索树-前一个线索节点**
* @note
* 测试-中序线索树-前一个线索节点
* -------------------------
* -------------------------
*
* -------------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 测试Pre函数**\n\n
* 声明nodes(结点数组, 长度4)\n
* nodes[0]取线索树首个线索结点\n
* nodes[1]至nodes[3]依次取后序结点\n
* 检测Pre函数\n
*/
void TestInorderThreadedTreePre() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedBinaryTree Pre |"<<endl;
cout<<"| 测试-中序线索树-前一个线索节点 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
// 声明inorder_threaded_tree
InorderThreadedBinaryTree<int> inorder_threaded_tree;
int node_count = 7;
// 插入整数0至6
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i);
}
// 调用CreateThreadRecursive构造线索
inorder_threaded_tree.CreateThreadRecursive();
// ---------- 2 测试Pre函数 ----------
// 声明nodes(结点数组, 长度4)
ThreadedNode<int>* nodes[4];
// nodes[0]取线索树首个线索结点
nodes[0] = inorder_threaded_tree.First(inorder_threaded_tree.Root());
// nodes[1]至nodes[3]依次取后序结点
for (int i = 1; i < 4; i++) {
nodes[i] = inorder_threaded_tree.Next(nodes[i - 1]);
}
// 检测Pre函数
for (int i = 3; i >=1; i--) {
ThreadedNode<int>* pre_node = inorder_threaded_tree.Pre(nodes[i]);
cout << "中序线索树第" << i << "个线索节点: " << pre_node->data << endl;
}
cout<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
/*!
* @brief **测试-中序线索树-父节点**
* @note
* 测试-中序线索树-父节点
* ------------------
* ------------------
*
* ------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 检测Parent函数**\n\n
* 取根结点, 结点2, 结点4, 根结点的父节点\n
* 取结点6, 结点3, 结点1, 结点5, 结点5的父节点, 结点4的父节点, 结点2的父节点\n
* 打印相关结点信息\n
*/
void TestInorderThreadedTreeParent() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedBinaryTree Parent |"<<endl;
cout<<"| 测试-中序线索树-父节点 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
// 声明inorder_threaded_tree
InorderThreadedBinaryTree<int> inorder_threaded_tree;
int node_count = 7;
// 插入整数0至6
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i);
}
// 调用CreateThreadRecursive构造线索
inorder_threaded_tree.CreateThreadRecursive();
// ---------- 2 检测Parent函数 ----------
// 取根结点, 结点2, 结点4, 根结点的父节点
ThreadedNode<int>* root = inorder_threaded_tree.Root();
ThreadedNode<int>* node_2 = root->right_child;
ThreadedNode<int>* node_4 = node_2->left_child;
ThreadedNode<int>* root_parent = inorder_threaded_tree.Parent(root);
// 取结点6, 结点3, 结点1, 结点5, 结点5的父节点, 结点4的父节点, 结点2的父节点
ThreadedNode<int>* node_6 = inorder_threaded_tree.First(root);
ThreadedNode<int>* node_3 = inorder_threaded_tree.Parent(node_6);
ThreadedNode<int>* node_1 = inorder_threaded_tree.Parent(node_3);
ThreadedNode<int>* node_5 = node_1->right_child;
ThreadedNode<int>* node_5_parent = inorder_threaded_tree.Parent(node_5);
ThreadedNode<int>* node_4_parent = inorder_threaded_tree.Parent(node_4);
ThreadedNode<int>* node_2_parent = inorder_threaded_tree.Parent(node_2);
// 打印相关结点信息
if (root_parent != nullptr) {
cout << "根节点的父节点: " << root_parent->data << endl;
} else {
cout<<"根节点的父节点为NULL"<<endl;
}
cout << "结点6的父结点: " << node_3->data << endl;
cout << "结点3的父结点: " << node_1->data << endl;
cout << "结点5的父结点: " << node_5_parent->data << endl;
cout << "结点4的父结点: " << node_4_parent->data << endl;
cout << "结点2的父结点: " << node_2_parent->data << endl;
cout << endl << "------------------------- CyberDash -------------------------" << endl << endl;
}
/*!
* @brief **测试-中序线索树-中序遍历**
* @note
* 测试-中序线索树-中序遍历
* --------------------
* --------------------
*
* --------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 中序遍历**\n\n
* 调用InorderTraverse\n
*
*
* --------------------
*/
void TestInorderThreadedTreeInorderTraverse() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedTree InorderTraverse |"<<endl;
cout<<"| 测试-中序线索树-中序遍历 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
// 声明inorder_threaded_tree
InorderThreadedBinaryTree<int> inorder_threaded_tree;
int node_count = 7;
// 插入整数0至6
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i);
}
// 调用CreateThreadRecursive构造线索
inorder_threaded_tree.CreateThreadRecursive();
// ---------- 2 中序遍历 ----------
cout<<"中序线索树, 中序遍历: "<<endl;
inorder_threaded_tree.InorderTraverse(visit); // 调用InorderTraverse
cout<<endl<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
/*!
* @brief **测试-中序线索树-前序遍历**
* @note
* 测试-中序线索树-前序遍历
* --------------------
* --------------------
*
* --------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 前序遍历**\n\n
* 调用PreorderTraverse\n
*
*
* --------------------
*/
void TestInorderThreadedTreePreorderTraverse() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedTree PreorderTraverse |"<<endl;
cout<<"| 测试-中序线索树-前序遍历 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
// 声明inorder_threaded_tree
InorderThreadedBinaryTree<int> inorder_threaded_tree;
int node_count = 7;
// 插入整数0至6
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i);
}
// 调用CreateThreadRecursive构造线索
inorder_threaded_tree.CreateThreadRecursive();
// ---------- 2 前序遍历 ----------
cout<<"中序线索树, 前序遍历: "<<endl;
inorder_threaded_tree.PreorderTraverse(visit); // 调用PreorderTraverse
cout<<endl<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
/*!
* @brief **测试-中序线索树-后序遍历**
* @note
* 测试-中序线索树-后序遍历
* --------------------
* --------------------
*
* --------------------
* + **1 构造线索树**\n\n
* 声明inorder_threaded_tree\n
* 插入整数0至6\n
* 调用CreateThreadRecursive构造线索\n\n
* + **2 后序遍历**\n\n
* 调用PostorderTraverse\n
*
*
* --------------------
*/
void TestInorderThreadedTreePostorderTraverse() {
cout<<endl;
cout<<"|------------------------ CyberDash ------------------------|"<<endl;
cout<<"| Test InorderThreadedTree PostorderTraverse |"<<endl;
cout<<"| 测试-中序线索树-后序遍历 |"<<endl;
cout<<"| |"<<endl;
cout<<"| 0 |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| / \\ |"<<endl;
cout<<"| 1 2 |"<<endl;
cout<<"| / \\ / |"<<endl;
cout<<"| 3 5 4 |"<<endl;
cout<<"| / |"<<endl;
cout<<"| 6 |"<<endl<<endl;
// ---------- 1 构造线索树 ----------
// 声明inorder_threaded_tree
InorderThreadedBinaryTree<int> inorder_threaded_tree;
int node_count = 7;
// 插入整数0至6
for (int i = 0 ; i < node_count; i++) {
inorder_threaded_tree.InsertRecursive(i);
}
// 调用CreateThreadRecursive构造线索
inorder_threaded_tree.CreateThreadRecursive();
// ---------- 2 后序遍历 ----------
cout<<"中序线索树, 后序遍历: "<<endl;
inorder_threaded_tree.PostorderTraverse(visit); // 调用PostorderTraverse
cout<<endl<<endl<<"------------------------- CyberDash -------------------------"<<endl;
cout<<endl;
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手