ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据结构：线索二叉树 [打印本页]
作者: 莫张周刘王    时间: 2024-6-7 19:46
标题: 数据结构：线索二叉树
目录
        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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4