【数据结构与算法】二叉树的遍历和线索二叉树

深藏阁楼爱情的钟 2024-04-26 02:24 298阅读 0赞

? 本文由 程序喵正在路上 原创，CSDN首发！
? 系列专栏：数据结构与算法
? 首发时间：2022年10月30日
? 欢迎关注?点赞?收藏?留言?
? 一以贯之的努力 不得懈怠的人生

阅读指南

  • 二叉树的先 / 中 / 后序遍历
    • 先序遍历
    • 中序遍历
    • 后序遍历
    • 快速求遍历序列
    • 求树的深度
  • 二叉树的层序遍历
    • 算法思想
    • 代码实现
  • 由遍历序列构造二叉树
  • 线索二叉树
    • 线索二叉树的存储结构
  • 二叉树的线索化
    • 中序线索化
    • 先序线索化
    • 后序线索化
  • 线索二叉树找前驱后继
    • 中序线索二叉树找中序后继
    • 中序线索二叉树找中序前驱
    • 先序线索二叉树找先序后继
    • 先序线索二叉树找先序前驱
    • 后序线索二叉树找后序前驱
    • 后序线索二叉树找后序后继

二叉树的先 / 中 / 后序遍历

二叉树的递归特性：

  • 要么是个空二叉树
  • 要么就是由 “根节点 + 左子树 + 右子树” 组成的二叉树

先序遍历：根左右（NLR）
中序遍历：左根右（LNR）
后序遍历：左右根（LRN）

我们来看一个简单的例子：
在这里插入图片描述

对上面这棵树进行前面说到的三种遍历：

  • 先序遍历： A B D E C F G A B D E C F G ABDECFG
  • 中序遍历： D B E A F C G DBEAFCG DBEAFCG
  • 后序遍历： D E B F G C A DEBFGCA DEBFGCA

先序遍历

先序遍历的操作过程如下：

  1. 若二叉树为空，则什么也不做

  2. 若二叉树非空：
    ① 访问根结点
    ② 先序遍历左子树
    ③ 先序遍历右子树

    //先序遍历
    void PreOrder(BiTree T) {

    1. if (T) {
    3.     visit(T);                  //访问根结点
    4.     PreOrder(T->lchild);    //递归遍历左子树
    5.     PreOrder(T->rchild);    //递归遍历右子树
    6. }

    }

中序遍历

先序遍历的操作过程如下：

  1. 若二叉树为空，则什么也不做

  2. 若二叉树非空：
    ① 先序遍历左子树
    ② 访问根结点
    ③ 先序遍历右子树

    //中序遍历
    void InOrder(BiTree T) {

    1. if (T) {
    3.     InOrder(T->lchild);        //递归遍历左子树
    4.     visit(T);                  //访问根结点
    5.     InOrder(T->rchild);        //递归遍历右子树
    6. }

    }

后序遍历

  1. //后序遍历
  2. void PostOrder(BiTree T) {
  4.     if (T) {
  6.         PostOrder(T->lchild);        //递归遍历左子树
  7.         PostOrder(T->rchild);        //递归遍历右子树
  8.         visit(T);                      //访问根结点
  9.     }
  10. }

快速求遍历序列

在这里插入图片描述

上图是以下列规则画出来的线路：

我们脑部空结点，首先从根结点出发，画一条路，如果左边还有没走的路，优先往左边走，走到路的尽头（空结点）就往回走；如果左边没路了，就往右边走；如果两边都没路，就往上面走

我们惊奇地发现，第一次路过的路线就是先序遍历的序列，第二次路过的路线就是中序遍历的序列，第三路过的路线就是后序遍历的序列

求树的深度

  1. int treeDepth(BiTree T) {
  3.     if (!T) return 0;
  4.     else {
  6.         int l = treeDepth(T->lchild);
  7.         int r = treeDepth(T->rchild);
  8.         //树的深度=Max(左子树深度, 右子树深度)+1
  9.         return l > r ? l + 1 : r + 1;
  10.     }
  11. }

二叉树的层序遍历

算法思想

层序遍历就是一层一层地对二叉树进行遍历

在这里插入图片描述

  1. 初始化一个辅助队列
  2. 根结点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
  4. 重复第 3 3 3 步直到队列为空

代码实现

  1. //二叉树的结点
  2. typedef struct BiTNode {
  4.     char data;
  5.     struct BiTNode *lchild, *rchild;
  6. }BiTNode, *BiTree;
  8. //链式队列结点
  9. typedef struct LinkNode {
  11.     BiTNode *data;
  12.     struct LinkNode *next;
  13. }LinkNode;
  15. typedef struct {
  17.     LinkNode *front, *rear;        //队头队尾
  18. }LinkQueue;
  20. //层序遍历
  21. void LevelOrder(BiTree T) {
  23.     LinkQueue Q;                    //初始化辅助队列
  24.     InitQueue(Q);                    
  25.     BiTree p;
  26.     EnQueue(Q, T);                    //让根结点入队
  27.     while (!IsEmpty(Q)) {
  28.                 //队列不空则循环
  29.         DeQueue(Q, p);                //队头结点出队
  30.         visit(p);                    //访问出队结点
  31.         if (p->lchild) {
  33.             EnQueue(Q, p->lchild);    //左孩子入队
  34.         } 
  35.         if (p->rchild) {
  37.             EnQueue(Q, p->rchild);    //右孩子入队
  38.         } 
  39.     }
  40. }

由遍历序列构造二叉树

如果只给出一棵二叉树的前 / 中 / 后 / 层 序遍历中的一种，我们是不能唯一确定一棵二叉树的

只有给出下列遍历序列，我们才能确定唯一的二叉树

  • 前序 + 中序遍历序列
  • 后序 + 中序遍历序列
  • 层序 + 中序遍历序列

注意：其中都有中序遍历序列，这是因为我们可以通过前序、后序和层序遍历序列来找到根结点，并根据中序序列划分左右子树，再找到左右子树根结点，这样才能确定唯一的一棵二叉树

线索二叉树

在一棵普通的二叉树中，如何找到指定结点 p p p 在中序遍历序列中的前驱和后继呢？

思路：

从根结点出发，重新进行一次中序遍历，指针 p p p 记录当前访问的结点，指针 p r e pre pre 记录上一个被访问的结点

  • 当 q = = p q==p q==p 时， p r e pre pre 为前驱
  • 当 p r e = = p pre==p pre==p 时， q q q 为后继

这样查找的缺点就是很不方便，遍历操作必须从根开始

所以线索二叉树出现了

在 n n n 个结点的二叉树中，有 n + 1 n+1 n+1 个空链域，我们可以利用这些空链域来记录前驱和后继的信息

线索二叉树的存储结构

下面是一棵中序线索二叉树，我们也可以将其称为线索链表

在这里插入图片描述

  1. //线索二叉树结点
  2. typedef struct ThreadNode{
  4.     ElemType data;
  5.     struct ThreadNode *lchild, *rchild;
  6.     int ltag, rtag;        //左、右线索标志
  7. }ThreadNode, *ThreadTree;

说明：

  • t a g = 0 tag=0 tag=0 时，表示指针指向孩子
  • t a g = 1 tag=1 tag=1 时，表示指针是“线索”

添加了 t a g tag tag 后，中序线索二叉树就变成下面这样

在这里插入图片描述

依次类推，我们也可以很容易地得到先序线索二叉树和后序线索二叉树

注意：

  • 先序线索二叉树 —— 线索指向先序前驱、先序后继
  • 中序线索二叉树 —— 线索指向中序前驱、中序后继
  • 后序线索二叉树 —— 线索指向后序前驱、后序后继

二叉树的线索化

中序线索化

首先，我们来看一下怎么暴力找到中序前驱？

  1. //辅助全局变量，用于查找结点 p 的前驱
  2. BiTNode *p;                //p 指向目标结点
  3. BiTNode *pre = NULL;    //pre 指向当前访问结点的前驱
  4. BiTNode *final = NULL;    //final 用于记录最终结果
  6. //访问结点 q
  7. void visit(BiTNode *q) {
  9.     if (q == p) {
  10.             //当前访问结点刚好是结点 p
  11.         final = pre;    //找到 p 的前驱
  12.     } else {
  14.         pre = q;        //pre 指向当前访问的结点
  15.     }
  16. }
  18. //查找中序前驱
  19. void findPre(BiTree T) {
  21.     if (T) {
  23.         findPre(T->lchild);        //递归遍历左子树
  24.         visit(T);                  //访问根结点
  25.         findPre(T->rchild);        //递归遍历右子树
  26.     }
  27. }

学习上面的思想，我们可以得到中序线索化的代码

  1. //线索二叉树结点
  2. typedef struct ThreadNode{
  4.     ElemType data;
  5.     struct ThreadNode *lchild, *rchild;
  6.     int ltag, rtag;        //左右线索标志
  7. }ThreadNode, *ThreadTree;
  9. //全局变量 pre, 指向当前访问结点的前驱
  10. ThreadNode *pre = NULL;
  12. void visit(ThreadNode *q) {
  14.     if (!q->lchild) {
  15.         //左子树为空, 建立前驱线索
  16.         q->lchild = pre;
  17.         q->ltag = 1;
  18.     }
  20.     if (pre != NULL && pre->rchild == NULL) {
  21.         //建立前驱结点的后继线索
  22.         pre->rchild = q;    
  23.         pre->rtag = 1;
  24.     }
  25.     pre = q;
  26. }
  28. //中序遍历二叉树, 一边遍历一边线索化
  29. void InThread(ThreadTree T) {
  31.     if (T) {
  33.         InThread(T->lchild);    //中序遍历左子树
  34.         visit(T);                //访问根结点
  35.         InThread(T->rchild);    //中序遍历右子树
  36.     }
  37. }
  39. //中序线索化二叉树T
  40. void CreateInThread(ThreadTree T) {
  42.     pre = NULL;                //pre 初始化为 NULL
  43.     if (T) {
  44.                     //非空二叉树才能线索化
  45.         InThread(T);        //中序线索化二叉树
  46.         if (!pre->rchild) {
  48.             pre->rtag = 1;    //处理遍历的最后一个结点
  49.         }
  50.     }
  51. }

另一种写法

  1. //中序线索化
  2. void InThread(ThreadTree p, ThreadTree &pre) {
  4.     if (p) {
  6.         InThread(p->lchild, pre);        //递归，线索化左子树
  8.         if (!p->lchild) {
  9.                     //左子树为空，建立前驱线索
  10.             p->lchild = pre;
  11.             p->ltag = 1;
  12.         }
  13.         if (pre && !pre->rchild) {
  14.             //建立前驱结点的后继线索
  15.             pre->rchild = p;
  16.             pre->rtag = 1;
  17.         }
  19.         pre = p;                        //标记当前结点称为刚刚访问过的结点
  20.         InThread(p->rchild, pre);        //递归，线索化右子树
  21.     }
  22. }
  24. //中序线索化二叉树T
  25. void CreateInThread(ThreadTree T) {
  27.     ThreadTree pre = NULL;
  28.     if (T) {
  29.                         //非空二叉树才进行线索化
  30.         InThread(T, pre);        //线索化二叉树
  31.         pre->rchlid = NULL;        //处理遍历的最后一个结点
  32.         pre->rtag = 1;
  33.     }
  34. }

先序线索化

  1. //线索二叉树结点
  2. typedef struct ThreadNode{
  4.     ElemType data;
  5.     struct ThreadNode *lchild, *rchild;
  6.     int ltag, rtag;        //左右线索标志
  7. }ThreadNode, *ThreadTree;
  9. //全局变量 pre, 指向当前访问结点的前驱
  10. ThreadNode *pre = NULL;
  12. void visit(ThreadNode *q) {
  14.     if (!q->lchild) {
  15.         //左子树为空, 建立前驱线索
  16.         q->lchild = pre;
  17.         q->ltag = 1;
  18.     }
  20.     if (pre != NULL && pre->rchild == NULL) {
  21.         //建立前驱结点的后继线索
  22.         pre->rchild = q;    
  23.         pre->rtag = 1;
  24.     }
  25.     pre = q;
  26. }
  28. //先序遍历二叉树, 一边遍历一边线索化
  29. void PreThread(ThreadTree T) {
  31.     if (T) {
  33.         visit(T);                //访问根结点
  34.         if (T->ltag == 0) {
  35.             //lchild 不是前驱线索
  36.             PreThread(T->lchild);    //中序遍历左子树
  37.         }
  38.         PreThread(T->rchild);    //中序遍历右子树
  39.     }
  40. }
  42. //先序线索化二叉树T
  43. void CreatePreThread(ThreadTree T) {
  45.     pre = NULL;                //pre 初始化为 NULL
  46.     if (T) {
  47.                     //非空二叉树才能线索化
  48.         PreThread(T);        //先序线索化二叉树
  49.         if (!pre->rchild) {
  51.             pre->rtag = 1;    //处理遍历的最后一个结点
  52.         }
  53.     }
  54. }

后序线索化

  1. //线索二叉树结点
  2. typedef struct ThreadNode{
  4.     ElemType data;
  5.     struct ThreadNode *lchild, *rchild;
  6.     int ltag, rtag;        //左右线索标志
  7. }ThreadNode, *ThreadTree;
  9. //全局变量 pre, 指向当前访问结点的前驱
  10. ThreadNode *pre = NULL;
  12. void visit(ThreadNode *q) {
  14.     if (!q->lchild) {
  15.         //左子树为空, 建立前驱线索
  16.         q->lchild = pre;
  17.         q->ltag = 1;
  18.     }
  20.     if (pre != NULL && pre->rchild == NULL) {
  21.         //建立前驱结点的后继线索
  22.         pre->rchild = q;    
  23.         pre->rtag = 1;
  24.     }
  25.     pre = q;
  26. }
  28. //后序遍历二叉树, 一边遍历一边线索化
  29. void PostThread(ThreadTree T) {
  31.     if (T) {
  33.         PostThread(T->lchild);    //中序遍历左子树
  34.         PostThread(T->rchild);    //中序遍历右子树
  35.         visit(T);                //访问根结点
  36.     }
  37. }
  39. //后序线索化二叉树T
  40. void CreatePostThread(ThreadTree T) {
  42.     pre = NULL;                //pre 初始化为 NULL
  43.     if (T) {
  44.                     //非空二叉树才能线索化
  45.         PostThread(T);        //后序线索化二叉树
  46.         if (!pre->rchild) {
  48.             pre->rtag = 1;    //处理遍历的最后一个结点
  49.         }
  50.     }
  51. }

线索二叉树找前驱后继

中序线索二叉树找中序后继

在中序线索二叉树种找到指定结点 p p p 的中序后继 n e x t next next

思路：

  • 若 p p p-> r t a g = = 1 rtag==1 rtag==1，说明 p p p 的右孩子指针是 “线索”，则 n e x t = p next=p next=p-> r c h i l d rchild rchild

  • 若 p p p-> r t a g = = 0 rtag==0 rtag==0，则 n e x t next next 为 p p p 的右子树中最左下的结点

    //找到以 p 为根的子树中，第一个被中序遍历的结点
    ThreadNode FirstNode(ThreadNode p) {

    1. //循环找到最左下结点（不一定是叶子结点）
    2. while (p->ltag == 0) p = p->lchild;
    3. return p;

    }

    //在中序线索二叉树中找到结点 p 的后继结点
    ThreadNode NextNode(ThreadNode p) {

    1. //右子树最左下结点
    2. if (p->rtag == 0) return FirstNode(p->rchild);
    3. else return p->rchild;        //rtag==1直接返回后继线索

    }

    //对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
    void Inorder(ThreadNode *T) {

    1. for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
    3.     visit(p);
    4. }

    }

中序线索二叉树找中序前驱

在中序线索二叉树种找到指定结点 p p p 的中序前驱 p r e pre pre

思路：

  • 若 p p p-> l t a g = = 1 ltag==1 ltag==1，说明 p p p 的左孩子指针是 “线索”，则 p r e = p pre=p pre=p-> l c h i l d lchild lchild

  • 若 p p p-> l t a g = = 0 ltag==0 ltag==0，则 p r e pre pre 为 p p p 的左子树中最右下的结点

    //找到以 p 为根的子树中，第一个被中序遍历的结点
    ThreadNode LastNode(ThreadNode p) {

    1. //循环找到最右下结点（不一定是叶子结点）
    2. while (p->rtag == 0) p = p->rchild;
    3. return p;

    }

    //在中序线索二叉树中找到结点 p 的前驱结点
    ThreadNode PreNode(ThreadNode p) {

    1. //左子树最右下结点
    2. if (p->ltag == 0) return LastNode(p->lchild);
    3. else return p->lchild;        //ltag==1直接返回前驱线索

    }

    //对中序线索二叉树进行逆向中序遍历（利用线索实现的非递归算法）
    void RevInorder(ThreadNode *T) {

    1. for (ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p)) {
    3.     visit(p);
    4. }

    }

先序线索二叉树找先序后继

在先序线索二叉树种找到指定结点 p p p 的先序后继 n e x t next next

思路：

  • 若 p p p-> r t a g = = 1 rtag==1 rtag==1，则 n e x t = p next=p next=p-> r c h i l d rchild rchild
  • 若 p p p-> r t a g = = 0 rtag==0 rtag==0，则当 p p p 有左孩子时，先序后继为左孩子；当 p p p 没有左孩子时，先序后继为右孩子

先序线索二叉树找先序前驱

由于在先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱，所以除非从头开始先序遍历，不然是找不到先序前驱的

如果改用三叉链表，我们就可以找到父节点，进而找到先序前驱，需要考虑的情况有：

  1. 如果能找到 p p p 的父节点，且 p p p 是左孩子，那么 p p p 的父节点即为其前驱
  2. 如果能找到 p p p 的父节点，且 p p p 是右孩子，其左兄弟为空，那么 p p p 的父节点即为其前驱
  3. 如果能找到 p p p 的父节点，且 p p p 是右孩子，其左兄弟非空，那么 p p p 的前驱为左兄弟子树中最后一个被先序遍历的结点
  4. 如果 p p p 是根结点，则 p p p 没有先序前驱

后序线索二叉树找后序前驱

在后序线索二叉树种找到指定结点 p p p 的后序前驱 p r e pre pre

思路：

  • 若 p p p-> l t a g = = 1 ltag==1 ltag==1，说明 p p p 的左孩子指针是 “线索”，则 p r e = p pre=p pre=p-> l c h i l d lchild lchild
  • 若 p p p-> l t a g = = 0 ltag==0 ltag==0，如果有右孩子，则后序前驱为右孩子；如果没有右孩子，则后序前驱为左孩子

后序线索二叉树找后序后继

由于在后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继，所以除非从头开始先序遍历，不然是找不到后继的

如果改用三叉链表，我们就可以找到父节点，进而找到后序后继，需要考虑的情况有：

  1. 如果能找到 p p p 的父节点，且 p p p 是右孩子，那么 p p p 的父节点即为其后继
  2. 如果能找到 p p p 的父节点，且 p p p 是左孩子，其右兄弟为空，那么 p p p 的父节点即为其后继
  3. 如果能找到 p p p 的父节点，且 p p p 是左孩子，其右兄弟非空，那么 p p p 的后继即为右兄弟子树中第一个被后序遍历的结点
  4. 如果 p p p 是根结点，则 p p p 没有后序后继

发表评论

表情：
评论列表 （有 0 条评论，298人围观）

还没有评论，来说两句吧...

相关阅读