现在位置: 首页 / 数据结构 / 正文

二叉树的遍历和线索二叉树-数据结构

二叉树的遍历和线索二叉树-数据结构

二叉树先、中、后序遍历

遍历：按照某种次序把所有结点都访问一遍

层次遍历：基于树的层次特性确定的次序规则

先/中/后序遍历：基于树的递归特性确定的次序规则

二叉树的递归特性：要么是空二叉树，要么就是由根节点+左子树+右子树组成的二叉树

先序遍历先访问根节点，然后递归地对左子树和右子树进行先序遍历。

中序遍历先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。

后序遍历先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。

请读者对照下图，手算二叉树遍历

二叉树手算练习

先序遍历（代码）

思路：若二叉树为空，不进行任何操作，若二叉树非空，访问根节点，先序遍历左子树，先序遍历右子树。空间复杂度为O(h)。

//二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
} BiTNode,*BiTree;

void PreOrder(BiTree T){
    if(T!=NULL)
    {
        visit(T); //putchar(T->data); visit函数的具体实现方式
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
中序遍历（代码）

思路：若二叉树为空，不进行任何操作，若二叉树非空，中序遍历左子树，访问根节点，中序遍历右子树。

//二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
} BiTNode,*BiTree;

void PreOrder(BiTree T){
    if(T!=NULL)
    {
        PreOrder(T->lchild);
        visit(T); //putchar(T->data); visit函数的具体实现方式
        PreOrder(T->rchild);
    }
}
后序遍历（代码）

思路：若二叉树为空，不进行任何操作，若二叉树非空，后序遍历左子树，后序遍历右子树，访问根节点。

//二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
} BiTNode,*BiTree;

void PreOrder(BiTree T){
    if(T!=NULL)
    {
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(T); //putchar(T->data); visit函数的具体实现方式
    }
}

关于三个遍历代码，读者需要掌握函数的递归调用的原理，在进行函数自身再次调用时，系统会开辟栈空间来记录当前函数执行到的位置。

函数的递归调用是指一个函数在执行过程中调用了自身。递归函数执行的基本原理如下：

  1. 调用函数自身：递归函数在执行过程中会调用自身，通常是通过递归调用语句来实现的。

  2. 基本情况（递归出口）：递归函数必须包含一个或多个基本情况（也称为递归出口或停止条件），这些基本情况用来终止递归过程。如果没有基本情况，递归会变成无限循环。

  3. 递归链：递归调用的执行形成了一个递归链，每次调用函数都会创建一个新的函数执行上下文（也称为栈帧），这些上下文会按照后进先出（LIFO）的顺序存储在内存中。

  4. 参数传递：递归函数调用时可以传递参数，这些参数可以控制递归的行为。

下面是一个简单的例子，展示了一个递归函数 factorial()，用于计算阶乘：

#include <stdio.h>

// 声明递归函数
int factorial(int n);

int main() {
    int result = factorial(5);
    printf("Factorial of 5 is: %d\n", result);
    return 0;
}

// 定义递归函数
int factorial(int n) {
    // 基本情况：当n为1时，返回1
    if (n == 1) {
        return 1;
    } else {
        // 递归调用：计算n * factorial(n-1)
        return n * factorial(n - 1);
    }
}

在执行上述代码时，以下是递归调用的执行过程：

  1. 第一次调用 factorial(5)，n 等于 5，不是基本情况，进入else分支。
  2. 执行 return 5 * factorial(4)，然后调用 factorial(4)。
  3. 第二次调用 factorial(4)，n 等于 4，不是基本情况，进入else分支。
  4. 执行 return 4 * factorial(3)，然后调用 factorial(3)。
  5. 第三次调用 factorial(3)，n 等于 3，不是基本情况，进入else分支。
  6. 执行 return 3 * factorial(2)，然后调用 factorial(2)。
  7. 第四次调用 factorial(2)，n 等于 2，不是基本情况，进入else分支。
  8. 执行 return 2 * factorial(1)，然后调用 factorial(1)。
  9. 第五次调用 factorial(1)，n 等于 1，满足基本情况，返回 1。
  10. 返回值传递回 factorial(2)，得到 2 * 1，返回 2。
  11. 返回值传递回 factorial(3)，得到 3 * 2，返回 6。
  12. 返回值传递回 factorial(4)，得到 4 * 6，返回 24。
  13. 返回值传递回 factorial(5)，得到 5 * 24，返回 120。

递归函数的执行过程中会一层层地创建函数执行上下文，直到达到基本情况，然后再逐层返回结果。递归的原理在于不断调用自身，通过将问题分解为更小的子问题来解决。

树的深度
int treeDepth(BiTree T){
    if(T==NULL)
    {
        return 0; // 空树的深度为0
    }else
    {
        int l= treeDepth(T->lchild); // 递归计算左子树的深度
        int r= treeDepth(T->rchild); // 递归计算右子树的深度
        // 树的深度=MAX（左子树深度，右子树深度）+1
        return l>r ? l+1:r+1; // 返回左子树深度和右子树深度的最大值加1
    }
}
二叉树层序遍历

算法思想：

1、初始化一个辅助队列

2、根节点入队

3、若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）

4、重复步骤3，直到队列为空

二叉树的层序遍历

层序遍历代码实现

此代码涉及之前的入队出队操作，请读者回顾之前章节的内容。

由遍历序列构造二叉树

一个中序遍历序列可能对应多种二叉树形态

一个前序遍历序列可能对应多种二叉树形态

一个后序遍历序列可能对应多种二叉树形态

一个层序遍历序列可能对应多种二叉树形态

通过上面的结论可得，若只给出一棵二叉树的前/中/后层序遍历序列中的一种，不能唯一确定一棵二叉树

前序+中序遍历序列
例一：

通过两种不同遍历方法根结点所在的位置，前序遍历算法可以先确定根结点的位置，再通过中序遍历算法，确定左子树和右子树的位置。

前序+中序-1

再重复上面的操作，通过两种不同的遍历算法，前序遍历算法确定根结点的位置，再确定左右子树的位置。

前序+中序-2

例二：

步骤与例一相同，关键读者要熟悉三个遍历算法的规律

前序+中序-3

前序+中序-4

后序 + 中序遍历序列

通过两种不同遍历方法根结点所在的位置，后序遍历算法可以先确定根结点的位置，再通过中序遍历算法，确定左子树和右子树的位置。

后序+中序-1

后序+中序-2

层序 + 中序遍历序列
例一：

通过两种不同遍历方法根结点所在的位置，层序遍历算法可以先确定根结点的位置，再通过中序遍历算法，确定左子树和右子树的位置。

层序+中序-1

层序+中序-2

例2：

请读者自行分析

层序+中序-3

层序+中序-4

层序+中序-5

注意：前序、后序、层序序列的两两组合无法唯一确定一棵二叉树。

线索二叉树

线索二叉树是一种对普通二叉树的扩展，它通过在二叉树节点中添加额外的线索（thread）信息，使得在遍历二叉树时可以更加高效地完成。在线索二叉树中，除了指向左右子节点的指针外，还有指向前驱节点和后继节点的线索。

具体来说，线索二叉树有两种类型的线索：

  1. 前序线索（preorder threading）：节点中的前驱线索指向前序遍历中的前一个节点，后继线索指向后继节点。这样，通过前序线索，可以在常数时间内找到任意节点的前驱和后继节点。

  2. 中序线索（inorder threading）：节点中的前驱线索指向中序遍历中的前一个节点，后继线索指向后继节点。中序线索的使用使得中序遍历时不需要递归或者栈，从而节省了空间和时间。

在构建线索二叉树时，需要在二叉树的基础上增加线索信息。构建过程一般分为两个阶段：

  1. 线索化阶段：根据选择的线索化方式，在遍历二叉树的过程中修改节点的指针，建立线索。

  2. 遍历阶段：利用建立好的线索信息实现相应的遍历算法。

线索二叉树的一个重要应用是在不需要递归或栈的情况下，对二叉树进行高效的遍历操作。此外，它也可以用于优化二叉树的查找操作，尤其是在需要频繁查找节点的前驱和后继时。

二叉树的中序遍历序列

对于如何找到指定结点p在中序遍历序列中的前驱结点和找到p的中序后继结点的问题，有以下思路：

从根节点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点，当q==p时，pre指针指向前驱结点，当pre==p时，q指针指向后继结点。

缺点：找前驱、后继结点很不方便，遍历操作必须从根开始。

中序线索二叉树

指向前驱、后继的指针称为线索，左孩子指针充当前驱线索，右孩子指针充当后继线索。

线索二叉树的存储结构

线索二叉树的存储结构

先序二叉树和后序二叉树的存储格式和原理都基本类似，区别在于相同的二叉树使用不同的遍历方法时，前驱后继指向的结点可能不一样。

中序线索化

代码思路：

1、定义树的结构体，包括数据、左右孩子指针、左右孩子标记。

2、中序遍历二叉树，一边遍历一边进行线索化，使用visit()函数对当前节点进行线索化处理，如果当前结点的左子节点为空，将其左指针指向前一个节点（pre），并将其左线索标记为1。再回头处理前一个结点，如果前一个结点的右指针为空，将其右指针指向当前结点（q），将其右线索标记为1。最后更新前一个结点指针（pre）为当前节点（q）。

3、InThread()函数递归执行。

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

typedef char ElemType;
//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag; //左、右线索标志
}ThreadNode,* ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//线索化处理
void visit(ThreadNode *q){
    if(q->lchild==NULL) //左子树为空，建立前驱线索
    {
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL) //pre结点不为空，并且右子树为空，建立前驱结点的后继线索
    {
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
    if(T!=NULL)
    {
        InThread(T->lchild); //中序遍历左子树
        visit(T); //访问根节点
        InThread(T->rchild); //中序遍历右子树
    }
}

//中序线索化二叉树T
void CreatInThread(ThreadTree T){
    pre=NULL; //pre指针初始化为NULL
    if(T!=NULL) //非空二叉树才能线索化
    {
        InThread(T); //中序线索化二叉树
        if(pre->rchild==NULL)
        {
            pre->rtag=1; //处理遍历后的最后一个节点
        }
    }
}
int main() {
    return 0;
}

中序线索化

注意：pre需要为引用类型，否则修改的只是pre的副本，其次在处理最后一个结点时，为什么不需要判断rchlid是否为NULL呢，因为中序遍历的最后一个节点右孩子指针必为空。

先序线索化

先序线索化与中序线索化有一定的区别，由于遍历顺序的不同，假如已经访问了B结点，接下来访问D结点，此时执行visit函数，对左孩子结点进行线索化，随后再执行先序遍历左子树，但是此时左子树已经指向了B节点，在执行下一步函数调用时，又会继续访问B结点，造成死循环。所以在代码前，需要添加判断条件，判断lchild不是前驱线索，才能进行前序遍历左子树的函数（InThread(T->lchild)）。

先序线索化

后序线索化

后序线索化就不用像前序线索化一样判断，因为在访问根结点的时候，左右子树都已经被访问完成了。

后序线索化

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

在中序线索二叉树中找指定结点*p的中序后继next，有两种情况，若p->rtag==1，则直接返回线索。若p->rtag==0，则代表p必有右孩子，根据中序遍历的规则，若右孩子为单独一个叶子结点，则该结点为当前*p结点的直接后继，若右孩子并非叶子结点，根据规则，循环查找右子树中最左边的结点即为*p结点的后继结点。

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

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

typedef char ElemType;

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

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//找到以p为根的子树中，第一个被中序遍历的节点
ThreadNode *FristNode(ThreadNode *p){
    //循环找到最左下结点（不一定是叶子结点）
    while (p->ltag==0)
    {
        p=p->lchild;
        return p;
    }
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag==0)
    {
        return FristNode(p->rchild);
    } else
    {
        return p->rchild; //rtag==1，则直接返回线索
    }
}

//线索化处理
void visit(ThreadNode *q){
    if(q->lchild==NULL) //左子树为空，建立前驱线索
    {
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL) //pre结点不为空，并且右子树为空，建立前驱结点的后继线索
    {
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法），空间复杂度为O(1)
void Inorder(ThreadNode *T){
    for (ThreadNode *p= FristNode(T); p!=NULL; p= NextNode(p)){
        visit(p);
    }
}
int main() {
    return 0;
}
中序线索二叉树找中序前驱

在中序线索二叉树中找指定结点*p的中序前驱pre，有两种情况，若p->rtag==1，则直接返回线索。若p->ltag==0，则代表p必有左孩子，根据中序遍历的规则，若左孩子为单独一个叶子结点，则该结点为当前*p结点的前驱，若左孩子并非叶子结点，根据规则，循环查找左子树中最右边的结点即为*p结点的前驱结点。

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

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

typedef char ElemType;

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

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//找到以p为根的子树中，最后一个被中序遍历的节点
ThreadNode *LastNode(ThreadNode *p){
    //循环找到最右下结点（不一定是叶子结点）
    while (p->rtag==0)
    {
        p=p->rchild;
        return p;
    }
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    //右子树中最左下结点
    if(p->ltag==0)
    {
        return LastNode(p->lchild);
    } else
    {
        return p->lchild; //rtag==1，则直接返回线索
    }
}

//线索化处理
void visit(ThreadNode *q){
    if(q->lchild==NULL) //左子树为空，建立前驱线索
    {
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL) //pre结点不为空，并且右子树为空，建立前驱结点的后继线索
    {
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
//对中序线索二叉树进行逆向中序遍历
void Inorder(ThreadNode *T){
    for (ThreadNode *p= LastNode(T); p!=NULL; p= PreNode(p)){
        visit(p);
    }
}
int main() {
    return 0;
}
先序线索二叉树找先序后继

在先序线索二叉树中找指定结点*p的先序后继next，有两种情况，若p->rtag==1，则直接返回线索。若p->rtag==0，则代表p必有右孩子，根据先序遍历的规则，若p有左孩子，则先序后继为左孩子，若p没有左孩子，则先序后继为右孩子。

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

// 在先序线索二叉树中找到结点p的先序后继结点
ThreadNode *NextNode(ThreadNode *p) {
  //如果p->rtag==1
  if(p->rtag==1)
  {
      return p->rchild;
  }else
  {
      if(p->lchild!=NULL)
      {
          return p->lchild;
      }else
      {
          return p->rchild;
      }
  }
}
先序线索二叉树找先序前驱

在先序线索二叉树中找指定结点*p的先序前驱pre，此时会发现，左右子树中的结点只可能是根的后继，不可能是前驱结点，除非使用朴素的方法，从头开始先序遍历。但如果改用三叉链表即可找到*p结点的父节点。

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

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

在后序线索二叉树中找指定结点*p的后序前驱pre，，有两种情况，若p->rtag==1，则直接返回线索。若p->ltag==0，则代表p必有左孩子，根据后序遍历的规则，若p有右孩子，则后序前驱为右孩子，若p没有右孩子，则后序前驱为左孩子。

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

// 在后序线索二叉树中找到结点p的后序前驱结点
ThreadNode *NextNode(ThreadNode *p) {
  //如果p->rtag==1
  if(p->rtag==1)
  {
      return p->lchild;
  }else
  {
      if(p->rchild!=NULL)
      {
          return p->rchild;
      }else
      {
          return p->lchild;
      }
  }
}
后序线索二叉树找后续后继

在后序线索二叉树中找指定结点*p的后序后继next，此时会发现，左右子树中的结点只可能是根的前驱，不可能是后继结点，除非使用朴素的方法，从头开始先序遍历。但如果改用三叉链表即可找到*p结点的父节点。

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

排序对比