数据结构：线索二叉树

目录
        1.线索二叉树是什么？
        2.包含头文件
        3.结点设计
        4.接口函数定义
        5.接口函数实现

---

线索二叉树是什么？

        线索二叉树（Threaded Binary Tree）是一种对普通二叉树的扩展，它通过在树的某些空指针上添加线索来实现更高效的遍历操作。线索二叉树的目的是减少查找特定节点（如前驱或后继节点）所需的时间，从而提高树的搜索效率。以下是线索二叉树的特点：
        1.普通二叉树的扩展：线索二叉树是基于普通二叉树的，它保留了二叉树的所有性质。
        2.线索：在二叉树的空指针（左子树或右子树的指针）上添加线索，这些线索可以指导我们找到节点的前驱或后继。
        3.前驱和后继：每个节点的前驱是其在中序遍历中直接前的一个节点，后继是直接后的节点。线索二叉树允许我们通过线索快速找到这些节点。

---

包含头文件

1. #include<stdio.h>
2. #include<stdlib.h>

复制代码

---

结点设计

1. #define Initsize 100
2. typedef char Elemtype;
4. typedef struct ThreadTree {
5.         Elemtype data;                                        //定义Elemtype类型的变量存储结点值
6.         struct ThreadTree* lchild;                //定义ThreadTree类型的指针变量lchild存储左子树的地址
7.         struct ThreadTree* rchild;                //定义ThreadTree类型的指针变量rchild存储右子树的地址
8.         int Lvalue, Rvalue;                                //定义int类型的变量Lvalue和Rvalue分别标识线索
9. }ThreadTree,* ThTree;
11. ThTree Pre = NULL;                                        //定义ThTree类型的全局变量Pre指向此次结点的前驱结点

复制代码

---

接口函数定义

1. void InitThTree(ThTree& A);                                //用于初始化线索二叉树
2. void InsertTree(ThTree& A);                                //用于输入数据建立二叉树
3. void InOrder(ThTree A);                                        //用于在二叉树中执行中序遍历
4. void InOrderVisit(ThTree& A);                        //用于在结点中进行中序线索化
5. void InOrderThread(ThTree& A);                        //用于中序遍历线索化二叉树
6. void PreOrder(ThTree A);                                //用于在二叉树中执行先序遍历
7. void PreOrderVisit(ThTree& A);                        //用于先序遍历线索化二叉树
8. void PreOrderThread(ThTree& A);                        //用于先序遍历线索化二叉树
9. void PostOrder(ThTree A);                                //用于执行后序遍历
10. void PostOrderVisit(ThTree& A);                        //用于后序遍历线索化二叉树
11. void PostOrderThread(ThTree& A);                //用于后序遍历线索化二叉树

复制代码

---

接口函数实现

2. void PostOrderThread(ThTree& A) {        //用于后序遍历线索化二叉树
3.         Pre = NULL;
4.         if (A != NULL) {
5.                 PostOrder(A);
6.                 if (A->rchild == NULL){
7.                         Pre->Rvalue = 1;
8.                 }
9.         }
10. }                       
12. void PostOrderVisit(ThTree& A) {        //用于后序遍历线索化二叉树
13.         if (A->lchild == NULL) {                //若传入的结点的左子树为空，则将该结点的左子树线索化
14.                 A->Lvalue = 1;
15.                 A->lchild = Pre;
16.         }
17.         if (A->rchild == NULL && Pre != NULL) {
18.         //若传入的结点的空子树为空，且前驱结点不为空，则将该结点的左子树线索化
19.                 Pre->rchild = A;
20.                 Pre->Rvalue = 1;
21.         }
22.         Pre = A;
23. }                               
25. void PostOrder(ThTree A) {                //用于执行后序遍历
26.         if (A != NULL) {
27.                 PostOrder(A->lchild);
28.                 PostOrder(A->rchild);
29.                 PostOrderVisit(A);
30.         }
31. }
33. void PreOrderThread(ThTree& A) { //用于先序遍历线索化二叉树
34.         Pre = NULL;                                                               
35.         if (A != NULL) {
36.                 PreOrder(A);
37.                 if (Pre->rchild == NULL) {
38.                         Pre->Rvalue = 1;
39.                 }
40.         }
41. }
43. void PreOrderVisit(ThTree& A) {         //用于先序遍历线索化二叉树
44.         if (A->lchild == NULL) {         //若传入的结点的左子树为空，则将该结点的左子树线索化
45.                 A->Lvalue = 1;
46.                 A->lchild = Pre;
47.         }
48.         if (A->rchild == NULL && Pre != NULL) {
49.         //若传入的结点的空子树为空，且前驱结点不为空，则将该结点的左子树线索化
50.                 Pre->Rvalue = 1;
51.                 Pre->rchild = A;
52.         }
53.         Pre = A;
54. }
57. void PreOrder(ThTree A)        {                  //用于在二叉树中执行先序遍历
58.         if (A != NULL) {
59.                 PreOrderVisit(A);
60.                 if (A->Lvalue==0) {
61.                         PreOrder(A->lchild);
62.                 }
63.                 PreOrder(A->rchild);
64.         }
65. }
67. void InOrderThread(ThTree& A) {          //用于中序遍历线索化二叉树
68.         Pre = NULL;                                          //遍历第一个结点时，第一个结点无前驱结点，故Pre为NULL
69.         if (A != NULL) {
70.                 InOrder(A);                                                        //进行中序遍历
71.                 if (Pre->rchild == NULL) {                        //将中序遍历的最后一个结点的右子树线索化
72.                         Pre->Rvalue = 1;                                //因为其结点无后继，故不更新指向
73.                 }
74.         }
75. }
77. void InOrderVisit(ThTree& A) {                //用于在结点中进行线索化
78.         if (A->lchild == NULL) {                //左子树若为空，则将其左子树线索化
79.                 A->Lvalue = 1;
80.                 A->lchild = Pre;
81.         }
82.         if (A->rchild == NULL && Pre != NULL) {//右子树若为空，则将其右子树线索化
83.                 Pre->rchild = A;
84.                 Pre->Rvalue = 1;
85.         }
86.         Pre = A;                //更新指向前驱结点的指针pre
87. }
89. void InOrder(ThTree A) {                        //用于在二叉树执行中序遍历
90.         if (A!= NULL) {                                       
91.                 InOrder(A->lchild);
92.                 InOrderVisit(A);
93.                 InOrder(A->rchild);
94.         }
95. }
97. void InsertTree(ThTree& A) {        //用于输入数据建立二叉树
98.         ThTree Q[Initsize],                //定义ThTree类型的指针数组存储根结点的地址
99.                    W = NULL;                //定义Thtree类型的指针W指向新建的结点的地址
100.         int i=0,                                //定义int类型的变量i作为左右孩子树的标识
101.                 j=0,                                //定义int类型的变量j作为字符串遍历的指针
102.                 top=-1;                                //定义int类型的变量top作为结点数组的指针
103.         char E,R[Initsize];
104.         printf("请以括号法输入数据，并以此建立二叉树：");
105.         scanf_s("%s", R, Initsize);
106.         E = R[i];
107.         while (E != '\0') {
108.                 switch (E) {
109.                 case '(':
110.                         top++;                         //入栈操作
111.                         Q[top] = W;
112.                         i = 1;                        //对新结点做标识，1为左子树的标识
113.                         break;
114.                 case ',':
115.                         i = 2;                        //对新结点做标识，2为右子树的标识
116.                         break;
117.                 case ')':
118.                         top--;                        //出栈操作
119.                         break;
120.                 default:
121.                         W = (ThreadTree*)malloc(sizeof(ThreadTree));                //新建结点
122.                         W->data = E;                                        //更新结点的数据域data的指向
123.                         W->rchild = W->lchild = NULL;
124.                         if (A == NULL) {                                //当传入的结点为空时，则新建的结点为树的根结点
125.                                 A = W;
126.                         }
127.                         else {
128.                                 switch (i) {                                        //判断传入的结点为左子树还是右子树
129.                                 case 1:
130.                                         Q[top]->lchild = W;                        //将栈内的根结点的lchild指向新建的地址
131.                                         break;
132.                                 case 2:
133.                                         Q[top]->rchild = W;                        //将栈内的根结点的rchild指向新建的地址
134.                                         break;
135.                                 }
136.                         }
137.                 }
138.                 j++;
139.                 E = R[j];
140.         }
141.         printf("构建线索二叉树对应的二叉树成功\n");
142. }
144. void InitThTree(ThTree& A) {        //用于初始化线索二叉树
145.         A = NULL;
146.         printf("初始化线索二叉树成功\n");
147. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。