树结构-二叉树

本是古典何须时尚 2022-09-10 11:11 203阅读 0赞

## 0 前言 ##

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常见，直观来看，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织结构都可以用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序时，可用树来表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。本文主要讨论二叉树的存储结构及其各种操作。

## 1 二叉树基本概念 ##

### 1.1 二叉树的定义 ###

二叉树(Binary Tree) 是一种常见的树型结构。

**定义**：有且只有一个根结点，除根结点外，每个结点只有一个父结点，最多只有两颗子树（即二叉树中不存在度大于2的结点），并且结点的子树有左右之分，其次序不能任意颠倒。

### 1.2 二叉树的5种基本形态 ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16][]

### 1.3 二叉树的基本性质 ###

二叉树具有下列重要性质。

**性质1**）在二叉树的第 i 层上至多有 ![2^\{i-1\}][2_i-1] 个结点。(i ≥ 1)

**性质2**）深度为 k 的二叉树至多有 ![2^\{k\} - 1][2_k_ - 1] 个结点。(k ≥ 1)

**性质3**）对任何一棵二叉树 T，如果其终端结点数为 ![n\_\{0\}][n_0]，度为 2 的结点数为 ![n\_\{2\}][n_2]，则 ![n\_\{0\}][n_0] = ![n\_\{2\}][n_2] \+ 1。终端结点也称为叶子结点，是指没有子树的结点。

性质3指出，一个二叉树，叶子结点数 = 度为2的结点数 + 1

满二叉树：一棵深度为 k 且有 ![2^\{k\} - 1][2_k_ - 1] 个结点的二叉树称为**满二叉树**。

这种树的特点是每一层上的结点数都达到最大结点数，即第 i 层上有 ![2^\{i-1\}][2_i-1] 个结点数。

如下图 6.4(a) 所示是一棵深度为 4 的满二叉树。

完全二叉树：对一棵满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左而右，由此可引出完全二叉树的定义。

深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为**完全二叉树**。

这种树的特点：（1）叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙结点的最大层次为 L，则其左分支下的子孙结点的最大层次必为 L 或 L+1。

如下图 6.4(b) 所示为一棵深度为 4 的完全二叉树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

**完全二叉树的两个重要性质:**

**性质4**）具有 n 个结点的完全二叉树的深度为 ![k = \\left \\lfloor \\log2^n\\right \\rfloor + 1][k _ _left _lfloor _log2_n_right _rfloor _ 1]

> 证明：假设完全二叉树深度为 k，则根据性质2 和 完全二叉树的定义有：
> 
> ![2^\{k-1\} - 1 < n \\leq 2^\{k\} - 1][2_k-1_ - 1 _ n _leq 2_k_ - 1] 或 ![2^\{k-1\} \\leq n < 2^\{k\}][2_k-1_ _leq n _ 2_k]
> 
> 于是 ![k-1 \\leq \\log 2^\{n\} < k][k-1 _leq _log 2_n_ _ k]，因为 k 是整数，所以 ![k = \\left \\lfloor \\log2^n\\right \\rfloor + 1][k _ _left _lfloor _log2_n_right _rfloor _ 1]。

**性质5**）如果对一棵有 n 个结点的完全二叉树（其深度为 ![\\left \\lfloor \\log2^n\\right \\rfloor + 1][left _lfloor _log2_n_right _rfloor _ 1]）的结点按层序编号（从第 1 层到 第 ![\\left \\lfloor \\log2^n\\right \\rfloor + 1][left _lfloor _log2_n_right _rfloor _ 1] 层，每层从左到右），则对任一结点 i（![1 \\leq i \\leq n][1 _leq i _leq n]），有：

（1）如果 i = 1，则结点 i 是二叉树的根结点，无双亲；如果 i > 1，则其父结点 FATHER(i) 的编号为 ![\\left \\lfloor \\ i/2\\right \\rfloor][left _lfloor _ i_2_right _rfloor] 。

（2）如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子结点 LChild(i) 的编号为 2i。

（3）如果 2i+1 > n，则结点无右孩子；否则其右孩子结点RChild(i) 的编号为 2i+1。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_14_color_FFFFFF_t_70_g_se_x_16][]

**分析如下**：

（1）i = 1时，由完全二叉树的定义可知，其左孩子是结点 2。若 n < 2，即不存在结点2，此时结点 i 无左孩子。结点 i 的右孩子也只能是结点 3，若结点 3 不存在，即 n < 3，此时结点 i 无右孩子。

（2）对于 i > 1 可分为两种情况讨论：

① 设第 j（![1\\leq j \\leq \\left \\lfloor \\ \\log 2^n\\right \\rfloor][1_leq j _leq _left _lfloor _ _log 2_n_right _rfloor]）层的第一个结点的编号为 i（由二叉树的定义和性质2可知 ![i = 2^\{j-1\}][i _ 2_j-1]），则其左孩子必为第 j+1 层的第一个结点，其编号为 ![2^\{j\} = 2(2^\{j-1\})= 2i][2_j_ _ 2_2_j-1_ 2i]，若 2i > n，则结点 i 无左孩子；其右孩子必为 第 j+1 层的第二个结点，起编号为 2i+1，若 2i+1 > n，则其无右孩子。

② 假设第 j（![1\\leq j \\leq \\left \\lfloor \\ \\log 2^n\\right \\rfloor][1_leq j _leq _left _lfloor _ _log 2_n_right _rfloor]）层上某个结点的编号为 i（![2^\{j-1\} \\leq i < 2^\{j\}-1][2_j-1_ _leq i _ 2_j_-1]），且 2i+1 < n，则其左孩子为 2i，右孩子为 2i+1。

如果编号 i+1 的结点是编号为 i 的结点的右兄弟（图6.5(a)）或者堂兄弟（图6.5(b)），若它有左孩子，则编号必为 2(i+1)=2i+2；若它有右孩子，则其编号必为 2(i+1)+1=2i+3。

### 1.4 二叉树的存储结构 ###

**1. 顺序存储结构**

// - - - - - 二叉树的顺序存储表示 - - - - -
    #define MAX_TREE_SIZE  100                  //二叉树的最大结点数
    typedef TElemType SqBiTree[MAX_TREE_SIZE];  //0号单元存储根节点
    SqBiTree bt;

按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下，自左而右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i 的结点元素存储在如上定义的一个一维数组中下标为 i-1 的位置中。

例如，在图 6.6(a) 所示为 上图 6.4(b) 所示完全二叉树的顺序存储结构。对于一般二叉树，则应该将其每个结点与完全二叉树上的结点相对照，存储在一维数组的对应位置中，如图 6.6(b) 所示，图中以 "0" 表示不存在此结点。由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为 ![\{\\color\{Red\} 2^\{k\}-1\}][color_Red_ 2_k_-1] 的一维数组。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_19_color_FFFFFF_t_70_g_se_x_16][]

**2. 链式存储结构**

由二叉树的定义可知，二叉树的结点（如图 6.7(a)所示）由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含了 3 个域：数据域和左、右指针域，如图 6.7(b)所示。有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域，如图 6.7(c)所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_14_color_FFFFFF_t_70_g_se_x_16 1][]

利用这两种结点结构所得的二叉树的存储结构分别称之为**二叉链表**和**三叉链表**，如图 6.8 所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

链表的头指针指向二叉树的根节点。容易证得，在含有 n 个结点的二次链表中有 n+1 个空链域。我们可以利用这些空链域存储其他有用的信息，从而得到另一种链式存储结构——线索链表。

以下是二叉链表的定义和部分基本操作的函数原型说明：

//函数结果状态代码
    #define TRUE           1
    #define FALSE          0
    #define OK             1
    #define ERROR          0
    #define INFEASIBLE     -1
    #define OVERFLOW       -2
    
    //Status 是函数的类型，其值是函数结果状态代码
    typedef int Status;
    //自定义结点元素的数据类型
    typedef char TElemType;
    
    // - - - - - 二叉树的二叉链表存储表示 - - - - -
    typedef struct BiTNode {
    	TElemType       data;               //数据域
    	struct BiTNode  *lchild, *rchild;   //左右孩子指针
    }BiTNode, *BiTree;
    
    // - - - - - 基本操作的函数原型说明(部分) - - - - -
    Status CreateBitTree(BiTree T);
      //按先序次序输入二叉树中结点的值(如一个字符)，空格字符表示空树。
      //构造二叉链表表示的二叉树T
    Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
      //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
      //先序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
      //一旦 Visit()失败，则操作失败
    Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
      //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
      //中序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
      //一旦 Visit()失败，则操作失败
    Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
      //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
      //后序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
      //一旦 Visit()失败，则操作失败
    Status LevelOrderTraverse(BiTree T, Status (*Visit)(TElemType e));
      //采用二叉链表存储结构，Visit 是对结点操作的应用函数。
      //层序遍历二叉树T，对每个结点调用函数 Visit 一次且仅一次。
      //一旦 Visit()失败，则操作失败

在不同的存储结构中，实现二叉树的操作方法也不同，如找结点 x 的双亲结点 PARENT(T, e)，在三叉链表中很容易实现，而在二叉链表中则需要从根结点出发进行逐一巡查。由此，在具体应用中采用什么存储结构，除根结点二叉树的形态之外，还应考虑需进行何种操作。

## 2 遍历二叉树（C实现） ##

**遍历二叉树**(Traversing binary tree)，即如何按某条搜索路径巡访二叉树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。“访问” 的含义，可以是对结点作各种处理，如输出结点的信息等。

回顾二叉树的递归定义可知，二叉树有 3 个基本单元组成：根结点、左子树和右子树。因此，若能一次遍历这三部分，便是遍历了整个二叉树。假如以 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则可有 DLR、LDR、LRD、DRL、RDL、RLD 这6种遍历二叉树的方案。若限定先左后右，则只有前 3 种方案，分别称之为：先序遍历(DLR)、中序遍历(LDR)和后序遍历(LRD)。基于二叉树的递归定义，可得下述遍历二叉树的递归遍历算法定义。

### 2.1 遍历二叉树的递归算法 ###

**先序遍历（根左右）**

算法思路：若二叉树为空，则直接返回；否则

（1）访问根结点；

（2）先序遍历左子树；

（3）再先序遍历右子树。

**中序遍历（左根右）**

算法思路：若二叉树为空，则直接返回；否则

（1）中序遍历左子树；

（2）访问根结点；

（3）再中序遍历右子树。

**后序遍历（左右根）**

算法思路：若二叉树为空，则直接返回；否则

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

先序遍历、中序遍历和后序遍历二叉树的递归算法在二叉链表上的代码实现如下：

//最简单的Visit函数
    Status PrintElement(TElemType e)
    {//输出结点
        printf("%d ",e);  //输出当前结点的数据域的值
        return OK;
    }
    
    /**
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    先序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: PreOrderTraverse(T, PrintElement);
    */
    Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        Visit(T->data); //访问根节点
        if(T->lchild)   //先遍历左子树
            PreOrderTraverse(T->lchild, Visit);
        if(T->rchild)   //再遍历右子树
            PreOrderTraverse(T->rchild, Visit);
        return OK;
    }
    
    /**
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    中序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: InOrderTraverse(T, PrintElement);
    */
    Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        if(T->lchild)   //先遍历左子树
            InOrderTraverse(T->lchild, Visit);
        Visit(T->data); //访问根节点
        if(T->rchild)   //再遍历右子树
            InOrderTraverse(T->rchild, Visit);
        return OK;
    }
    
    /**
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    后序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: PostOrderTraverse(T, PrintElement);
    */
    Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        if(T->lchild)   //先遍历左子树
            InOrderTraverse(T->lchild, Visit);
        if(T->rchild)   //再遍历右子树
            InOrderTraverse(T->rchild, Visit);
        Visit(T->data); //访问根节点
        return OK;
    }

**示例**1：如图 6.9 所示的二叉树表示的表达式：![a + b \* (c - d) - e / f][a _ b _ _c - d_ - e _ f]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_9_color_FFFFFF_t_70_g_se_x_16][]

> <**备注**> 以二叉树表示表达式的递归定义如下：
> 
>  *  若表达式为数或者简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式的信息；
>  *  若表达式 = (第一操作数) (运算符) (第二操作数)，则相应的二叉树左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空）。

若先序遍历此二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序排序为：

- + a * b - c d / e f        (6-3)

若中序遍历此二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序排序为：

a + b * c - d - e / f         (6-4)

若后序遍历此二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序排序为：

a b c d - * + e f / -         (6-5)

从表达式来看，以上 3 个序列 (6-3)、(6-4)、(6-5) 恰好为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。

从上述二叉树遍历的定义可知，3 种遍历算法不同之处仅在于访问根结点和遍历左、右子树的先后关系。如果在算法中暂且抹去和递归无关的 Visit 语句，则 3 个遍历算法完全相同。由此，从递归执行过程的角度看先序、中序和后序遍历也是完全相同的。下图 6.10(b) 中用带箭头的虚线表示了这 3 种遍历算法的递归执行过程。其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回；虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历二叉树过程中访问结点时输出的信息。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

例如，由于中序遍历中访问当前结点是在遍历该结点的左子树之后、遍历该结点的右子树之前进行的，则带圆形的字符标在向左递归返回和向右递归调用之间。

由此，只要沿着虚线从 1 出发到 2 结束，将沿途所见的三角形（或圆形、或方形）内的字符记下，便可得到遍历二叉树的先序（或中序、或后序）序列。

例如，从图 6.10(b) 分别可得到图 6.10(a) 所示的：

前缀表示( - \* a b c)

中缀表示( a \* b - c)

后缀表示( a b \* c -)

### 2.2 遍历二叉树的非递归算法 ###

仿照递归算法执行过程中递归工作栈的状态变化，可直接写出相应的非递归算法。可以使用栈的方式实现二叉树的非递归调用算法。

**顺序栈的定义和基本操作实现**：

/*************** 用栈结构实现二叉树的非递归遍历 ***************/
    #define MAXSIZE 100
    
    //顺序栈元素类型定义
    typedef BiTree SElemType;
    
    //栈的定义(顺序栈)
    typedef struct {
        SElemType *top;      //栈顶指针
        SElemType *base;     //栈底指针
        int stacksize;    //栈的最大长度
    }SqStack;
    
    //说明: SqStack栈结构体存放的是指向二叉树结点的指针，也就是说，栈中存放的元素是指针
    
    //初始化一个栈
    Status InitStack(SqStack *S)
    {
        if(S == NULL)
            return ERROR;
        
        S->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));
        if(!S->base)           //分配失败，退出
            exit(OVERFLOW);
        S->top = S->base;        //栈顶指针初始化为栈底指针
        S->stacksize = MAXSIZE; //初始化栈的最大容量
        return OK;
    }
    
    //栈判空操作
    Status StackEmpty(SqStack S)
    {
        if(S.top == S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    //取顺序栈栈顶元素,并用e接收
    Status GetTop(SqStack S, SElemType *e)
    {
        if(S.top == S.base)
            return ERROR;
        else                    //栈非空    
            *e = *(S.top - 1);  //返回栈顶元素
        return OK;
    }
    
    //入栈操作，将元素e压入到栈顶
    Status Push(SqStack *S, SElemType e)
    {
        if(S == NULL || S->base == NULL)
            return ERROR;
        
        if (S->top - S->base == S->stacksize) //栈慢，返回错误
            return ERROR;
        
        *(S->top) = e;      //将新元素e压入栈顶
        S->top++;           //栈顶指针自增1
        
        return OK;
    }
    
    //出栈操作，将栈顶元素弹出，并用e接收
    Status Pop(SqStack *S, SElemType *e)
    {
        if(S == NULL || S->base == NULL)
            return ERROR;
        
        if (S->top == S->base)  //栈空返回错误
            return ERROR;      
        
        --S->top;              //栈顶指针先自减1
        *e = *(S->top);         //获取栈顶元素e
        
        return OK;
    }

**先序遍历（根左右）**

算法思路1：从左至右入栈

*  利用一个栈，首先从根结点开始一直入栈左子树，并不断打印访问到的结点，直到左子树为空。
 *  获取并取出栈顶元素，对获取到的栈顶元素的右子树做如上操作。
 *  直到栈中元素为空，遍历结束。

/**
    先序遍历非递归实现，从左到右入栈法则
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    先序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: PreOrderTraverse(T, PrintElement);
    */
    Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        SqStack S;
        InitStack(&S);   //创建一个栈S
        BiTree  p = T;   //指针p初始指向根结点
        
        while (p || !StackEmpty(S))
        {
            if(p)
            {
                Push(&S, p);              //进栈操作
                Visit(p->data)            //输出当前根结点的数据域信息
                p = p->lchild;            //遍历左子树
            }
            else
            {
                Pop(&S, &p);              //出栈操作
                p = p->rchild;            //遍历右子树
            }
        }
        
        return OK;
    }

算法思路2：从右到左入栈（可以联想两个点：栈的性质是先进后出+先序遍历的递归顺序）

*  将根结点入栈；
 *  获取栈顶元素并打印；
 *  栈顶元素出栈；
 *  判断获取到的栈顶元素右子树是否为空，不为空则入栈右节点；
 *  判断获取到的栈顶元素左子树是否为空，不为空则入栈左节点；

//先序遍历非递归实现算法2，从右到左入栈
    Status PreOrderTraverse_2(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        SElemType e;
        SqStack S;
        InitStack(&S);   //创建一个栈S
        Push(&S, T);     //树根指针入栈
        
        while(!StackEmpty(S)){
            GetTop(S, &e);      //获取栈顶元素，并用e接收
            Visit(e->data);     //访问根结点，打印信息
            Pop(&S, &e);        //栈顶元素出栈
            
            if(e->rchild)       //如果右子树存在，则入栈
                Push(&S, e->rchild);
            if(e->lchild)       //如果左子树存在，则入栈
                Push(&S, e->lchild);
        }
        
        return OK;
    }

**中序遍历（左根右）**

算法思路1：

*  初始化一个空栈S，指针p指向根结点。
 *  申请一个结点指针q，用来存放栈顶弹出的元素。
 *  当 p 非空或者栈S非空时，循环执行以下操作：

(1) 如果 p 非空，则将 p 进栈，p 指向该结点的左子树；

(2) 如果 p 为空，则弹出栈顶元素并访问，将 p 指向该结点的右子树。

/**
    中序遍历非递归实现，从左到右入栈法则
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    中序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: InOrderTraverse(T, PrintElement);
    */
    Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        SqStack S;
        InitStack(&S);   //创建一个栈S
        BiTree  p = T;   //指针p初始指向根结点
        BiTree  q = NULL;
        
        while (p || !StackEmpty(S))
        {
            if(p)                         //p非空
            {
                Push(&S, p);              //根指针进栈
                p = p->lchild;            //遍历左子树
            }
            else                          //p为空
            {
                Pop(&S, &q);              //出栈操作，并用q接收
                Visit(q->data)            //输出当前根结点的数据域信息
                p = q->rchild;            //遍历右子树
            }
        }
        
        return OK;
    }

算法思路2：

*  首先将指向根结点的指针入栈；
 *  获取栈顶元素，如果栈顶元素存在，则将该栈顶元素的左子树入栈，直到左子树为空。注意此时栈顶元素是NULL，所以需要加一步空指针退栈操作；
 *  栈顶元素退栈，输出当前栈顶元素指向的结点的数据域信息，并将当前栈顶元素指向的结点的右子树入栈；
 *  直到栈为空，遍历结束。

//中序遍历非递归实现-算法2
    Status InOrderTraverse_2(BiTree T, Status(Visit)(TElemType))
    {
        if(T == NULL)
            return ERROR;
    
        SqStack S;
        BiTree p = NULL;
        
        InitStack(&S);  //初始化栈S
        Push(&S, T);    //初始树根指针入栈
        
        while(!StackEmpty(S)) {
            // 向左走到尽头，最后一个结点的左孩子为空
            while(GetTop(S, &p) && p != NULL) {
                Push(&S, p->lchild);
            }
            
            Pop(&S, &p);    //空指针退栈
            
            if(!StackEmpty(S)) {
                // 访问结点
                Pop(&S, &p);
                Visit(p->data)    //输出当前结点的数据域信息
                
                // 向右一步
                Push(&S, p->rchild);
            }
        }
        
        return OK;
    }

**后序遍历（左右根）**

算法思路：因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根结点。当用堆栈来存储结点，必须分清返回根结点时，是从左子树返回的，还是从右子树返回的。所以，使用辅助指针r，其指向最近访问过的结点。也可以使用一个标记数组，记录各结点的访问标记。

/**
    后序遍历非递归实现1-使用辅助指针法
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    后序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: PostOrderTraverse(T, PrintElement);
    */
    Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
    
        SqStack S;
        BiTree p = T;   //指针p初始指向根结点
        BiTree r = NULL;
        
        InitStack(&S);  //初始化空栈S
        
        while(p || !StackEmpty(S))
        {
            if(p)                         //p非空(一直走到最左边)
            {
                Push(&S, p);              //根指针进栈
                p = p->lchild;            //遍历左子树
            }
            else                          //p为空
            {
                GetTop(S, &p);            //获取栈顶元素，并用p接收
                if(p->rchild && p->rchild != r)  //如果右子树存在，且未被访问
                    p = p->rchild;               //继续遍历右子树
                else                             //右子树为空 或者 右子树已被访问
                {
                    Pop(&S, &p);                 //栈顶元素出栈，并用p接收
                    Visit(p->data);
                    r = p;                       //记录最近访问过的结点
                    p = NULL;                    //结点访问完后，重置p指针
                }
            }
        }
        
        return OK;
    }
    
    /**
    后序遍历非递归实现2-使用标记数组法
    函数说明:采用二叉链表存储结构，Visit是对数据元素操作的应用函数
    后序遍历二叉树T的递归算法，对每个数据元素调用Visit。
    调用实例: PostOrderTraverse(T, PrintElement);
    */
    Status PostOrderTraverse_2(BiTree T, Status (*Visit)(TElemType e))
    {
        if(T == NULL)
            return ERROR;
        
        SqStack S;
        BiTree  p;
        SElemType e;
        int StackMark[MAXSIZE] = {0};  //标记栈，设置各结点访问标记（初始化为0）
        int k;
        
        InitStack(&S);
        p = T;
        k = -1;
        
        while(p || !StackEmpty(S))
        {
            if(p)                         //p非空(一直走到最左边)
            {
                Push(&S, p);              //根指针进栈
                k++;
                StackMark[k] = 1          //设置第一次访问的标记
                p = p->lchild;            //遍历左子树
            }
            else
            {
                GetTop(S, &p);            //获取栈顶元素，并用p接收
                if(StackMark[k] == 1)     //已访问过一次，当前是第二次访问
                {
                    StackMark[k] = 2;
                    p = p->rchild;
                }
                else                             //已访问过两次，当前是第三次访问
                {
                    Pop(&S, &p);                 //栈顶元素出栈，并用p接收
                    Visit(p->data);
                    StackMark[k] = 0;
                    k--;
                    p = NULL;
                }
            }
        }
        
        return OK;
    }

### 2.3 根据遍历序列确定二叉树 ###

若一棵二叉树中各结点的值均不相同，则任意一棵二叉树结点的先序序列、中序序列和后序序列都是**唯一的**。反过来，若已知二叉树遍历的任意两种序列，能否确定一棵二叉树呢？这样确定的二叉树是否是唯一的呢？

由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。

1、根据先序序列和中序序列来确定一个二叉树的步骤如下：

> （1）根据二叉树定义，二叉树的先序遍历是先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历方式遍历根结点的右子树。这就是说，在先序序列中，第一个结点一定是二叉树的根结点。
> 
> （2）另一方面，中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。
> 
> （3）根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样就确定了二叉树的三个结点。
> 
> （4）同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可得到一颗二叉树。

2、根据二叉树的后序序列和中序序列来确定一个二叉树的步骤如下：

> （1）依据后续遍历和中序遍历的定义，后序序列的最后一个结点是根结点，可根据这个根结点，将中序序列分成两个子序列，分别为这个结点左子树的中序序列和右子树的中序序列。
> 
> （2）然后再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取尽后序序列的结点时，便可得到一颗二叉树。

【**示例1**】假设一棵二叉树的先序序列为 **EBADCFHGIKJ** 和中序序列为 **ABCDEFGHIJK**，请画出这颗二叉树。

**分析如下**：

（1）由先序遍历特征，根结点是 E；

（2）由中序遍历特征，根结点必在中间，因此可以确定根结点的左子树子孙为 ABCD，其右子树子孙为 FGHIJK。

（3）继而，根据先序子串中的 BADC，可确定 B 为根结点 E 的左孩子；根据先序子串中的 FHGIKJ，可确定 F 为根结点 E 的右孩子，如此就确定了二叉树的三个结点，即分别是根结点 E，根结点的左孩子 B 和 根结点的右孩子 F。

（4）根据中序子串中的 ABCD 可知，A 为 B 的左孩子，CD 为 B 的右子树子孙。再根据先序中的 DC 子串，可知 D 为 C 的双亲结点；然后根据中序中的 CD 子串，可知 C 为 D 的左孩子。如此就确定了根结点 E 的左子树部分。

（5）根据中序子串中的 FGHIJK 可知，F 的左孩子为空，右子树子孙序列为 GHIJK。再根据先序序列中的 HGIKJ 子串，可知 H 为 F 的右子树子孙序列 GHIJK 的双亲结点，即 H 为 F 的右孩子。然后根据 中序中的 GHIJK，可知 G 为 H 的左孩子，IJK 为 H的右子树子孙。

（6）根据先序中的 IKJ 子串可知，I 为 KJ 子串的双亲结点；再根据中序中的 IJK 子串，可知 I 的左孩子为空，右子树子孙序列为 JK。

（7）根据先序中的 KJ 子串可知，K 为 J 的双亲结点；再根据中序中的 JK 子串，可知 J 为 K 的左孩子，K 的右孩子为空。如此就确定了根结点 E 的右子树部分。

至此，这颗二叉树的所有结点的位置都已唯一地确定了。这颗二叉树的结构如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_10_color_FFFFFF_t_70_g_se_x_16][]

【**示例**2】假设一颗二叉树的中序序列和后序序列分别是 **BDCEAFHG** 和 **DECBHGFA**，请画出这颗二叉树。

**分析如下**：

（1）由后序遍历特征，根结点必在后序序列尾部，即根结点是 A；

（2）由中序遍历特征，根结点必在中间，而且其左边必全是左子树子孙（BDCE），其右边必全是右子树子孙（FHG）；

（3）继而，根据后序中的 DECB 子树可确定 B 为 A 的左孩子；根据 HGF 子串可确定 F 为 A的右孩子；以此类推，可以唯一确定一颗二叉树，如下图所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_12_color_FFFFFF_t_70_g_se_x_16][]

但是，由一颗二叉树的先序序列和后序序列**不能唯一确定**一颗二叉树。

> 因为无法确定左右子树两部分。例如，如果有先序序列 AB，后序序列 BA，因为无法确定 B 为左子树还是右子树，所以可得到如下图所示的两颗不同的二叉树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_10_color_FFFFFF_t_70_g_se_x_16 1][] 两颗不同的二叉树

### 2.4 层序遍历 ###

对二叉树进行遍历的搜索路径除了上述按先序、中序和后序外，还可以从上到下，（同一层）从左到右的顺序来进行，即为 层序遍历。

二叉树的层序遍历可以利用 队列 的方式实现，每次把访问到的结点的左右子树放到队列里面去，出队的时候同样操作。

二叉树的层序遍历算法实现这里就不展开了，之后会单独写一篇博文来讲述该算法的C语言实现。

### 2.5 遍历二叉树算法——算法复杂度分析 ###

遍历二叉树的算法中的基本操作是访问结点，且无论按哪一种次序进行遍历，对含有 n 个结点的二叉树，其时间复杂度均为 **O(n)**。

所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为 n，则空间复杂度为 **O(n)**。

## 3 创建二叉树（二叉链表法） ##

为简化问题，设二叉树中结点的元素均为一个单字符。假设按先序遍历的顺序建立二叉链表，T 为指向根结点的指针，对于给定的一个字符序列，依次读入字符，从根结点开始，递归创建二叉树。

### 3.1 先序遍历顺序建立二叉链表（递归算法） ###

【算法步骤】

（1）输入一个字符 ch。

（2）如果 ch 是一个 "\#" 字符，则表明该二叉树为空树，即 T 为 NULL；否则执行以下操作：

*  申请一个结点空间 T；
 *  将 ch 赋值给 T->data；
 *  递归创建 T 的左子树；
 *  递归创建 T 的右子树。

【算法描述】C语言实现

//创建二叉树(二叉链表法)-按先序序列创建二叉树
    Status CreateBiTree(BiTree T)
    {
        scanf("%c", ch);
        if(ch == '#')
            T = NULL;       //递归结束
        else
        {
            T = (BiTNode*)malloc(sizeof(BiTNode));
            T-data = ch;               //生成根结点
            CreateBiTree(T->lchild);   //递归构造左子树
            CreateBiTree(T->rchild);   //递归构造右子树
        }
        
        return OK;
    }

## 4 复制二叉树（递归算法） ##

复制二叉树就是利用已有的一颗二叉树复制得到另一颗与其完全相同的二叉树。根据二叉树的特点，复制步骤如下：

(1) 若二叉树不为空，则首先复制根结点，这相当于二叉树先序遍历算法中访问根结点的语句；

(2) 然后分别复制二叉树根结点的左子树和右子树，这相当于先序遍历中递归遍历左子树和右子树。

因此，复制函数的实现与二叉树先序遍历的实现非常类似。

【算法步骤】

如果是空树，递归结束，否则执行以下操作：

*  申请一个新结点空间，复制根结点；
 *  递归复制左子树；
 *  递归复制右子树。

【算法描述】C语言实现

//复制一棵和T完全相同的二叉树
    void CopyBiTree(BiTree T, BiTree NewT)
    {
        if(T == NULL)        //如果是空树，递归结束
        {
            NewT = NULL;
            return;
        }
        else                //如果非空
        {
            NewT = (BiTNode*)malloc(sizeof(BiTNode));
            NewT->data = T->data;
            CopyBiTree(T->lchild, NewT->lchild);      //递归复制左子树
            CopyBiTree(T->rchild, NewT->rchild);      //递归复制右子树
        }
    }

【**拓展**】也可以利用 队列 的方式实现复制一棵二叉树的 非递归算法。这里就不再赘述了，有兴趣的话，可以尝试一下。

## 5 计算二叉树的深度（递归算法） ##

【算法步骤】

如果是空树，递归结束，深度为0，否则执行以下操作：

*  递归计算左子树的深度记为 LD；
 *  递归计算右子树的深度记为 RD；
 *  如果 LD >= RD，二叉树的深度为 LD+1，否则为 RD+1。

【算法描述】C语言实现

//计算二叉树T的深度(递归算法)
    int BiTreeDepth(BiTree T)
    {
        int LD, RD;
        
        if(T == NULL)      //如果是空树，深度为0，递归结束
            return 0;
        else
        {
            LD = DepthBiTree(T->lchild);      //递归计算左子树的深度记为LD
            RD = DepthBiTree(T->rchild);      //递归计算左子树的深度记为RD
            return (LD >= RD ? LD : RD) + 1;
        }
    }

## 6 统计二叉树中结点的个数（递归算法） ##

【算法步骤】

如果是空树，则返回结点个数为 0，否则执行以下操作：

*  递归计算左子树的结点个数；
 *  递归计算右子树的结点个数；
 *  最后返回 (左子树的结点个数+右子树的结点个数+1)。

【算法描述】C语言实现

//统计二叉树T中结点的个数（递归算法）
    int BiTreeNodeCount(BiTree T)
    {
        if(T == NULL)           //如果是空树，则结点个数为0，递归结束
            return 0;
        else
            return BiTreeNodeCount(T->lchild)+BiTreeNodeCount(T->rchild)+1;
    }

【**拓展**】我们可以模仿此算法，还可以写出：统计二叉树叶子结点（度为 0）的个数，度为 1 的结点个数 和 度为 2 的结点个数。算法实现的关键是如何表示度为 0、度为 1 或者度为 2 的结点。

### 示例：统计二叉树的叶子结点个数（递归算法） ###

【算法步骤】

如果二叉树为空，则返回结点个数为0，否则执行以下操作：

*  当二叉树不为空，且左、右子树为空（叶子结点）时，递归结束返回 1；
 *  当二叉树不为空，且左、右子树不同时为空时（非叶子结点），递归调用函数，返回左子树中叶子结点个数 + 右子树中叶子结点个数。

【算法描述】C语言实现

//统计二叉树T中叶子结点的个数
    int BiTreeLeafNode(BiTree T)
    {
        if(T == NULL)          //空树，返回0
            return 0;
        else if(T->lchild==NULL && T->rchild==NULL)  //叶子结点，返回1
            return 1;
        else
            return BiTreeLeafNode(T->lchild)+BiTreeLeafNode(T->rchild);
    }

## 参考 ##

《数据结构(严蔚敏-C语言版)》

《数据结构题集(严蔚敏-C语言版)》

[第6章 树和二叉树 - 二叉树（二叉链表存储）严蔚敏.吴伟民版][6_ _ - _.]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/3e0ec15b4044498a97f6d8b60c330650.png
[2_i-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bi-1%7D
[2_k_ - 1]: https://latex.codecogs.com/gif.latex?2%5E%7Bk%7D%20-%201
[n_0]: https://latex.codecogs.com/gif.latex?n_%7B0%7D
[n_2]: https://latex.codecogs.com/gif.latex?n_%7B2%7D
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/b064b4e6a523466d98744ac292aaf288.png
[k _ _left _lfloor _log2_n_right _rfloor _ 1]: https://latex.codecogs.com/gif.latex?k%20%3D%20%5Cleft%20%5Clfloor%20%5Clog2%5En%5Cright%20%5Crfloor%20&plus;%201
[2_k-1_ - 1 _ n _leq 2_k_ - 1]: https://latex.codecogs.com/gif.latex?2%5E%7Bk-1%7D%20-%201%20%3C%20n%20%5Cleq%202%5E%7Bk%7D%20-%201
[2_k-1_ _leq n _ 2_k]: https://latex.codecogs.com/gif.latex?2%5E%7Bk-1%7D%20%5Cleq%20n%20%3C%202%5E%7Bk%7D
[k-1 _leq _log 2_n_ _ k]: https://latex.codecogs.com/gif.latex?k-1%20%5Cleq%20%5Clog%202%5E%7Bn%7D%20%3C%20k
[left _lfloor _log2_n_right _rfloor _ 1]: https://latex.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20%5Clog2%5En%5Cright%20%5Crfloor%20&plus;%201
[1 _leq i _leq n]: https://latex.codecogs.com/gif.latex?1%20%5Cleq%20i%20%5Cleq%20n
[left _lfloor _ i_2_right _rfloor]: https://latex.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20%5C%20i/2%5Cright%20%5Crfloor
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/69c859c8d04d423aa29624596d9a9198.png
[1_leq j _leq _left _lfloor _ _log 2_n_right _rfloor]: https://latex.codecogs.com/gif.latex?1%5Cleq%20j%20%5Cleq%20%5Cleft%20%5Clfloor%20%5C%20%5Clog%202%5En%5Cright%20%5Crfloor
[i _ 2_j-1]: https://latex.codecogs.com/gif.latex?i%20%3D%202%5E%7Bj-1%7D
[2_j_ _ 2_2_j-1_ 2i]: https://latex.codecogs.com/gif.latex?2%5E%7Bj%7D%20%3D%202%282%5E%7Bj-1%7D%29%3D%202i
[2_j-1_ _leq i _ 2_j_-1]: https://latex.codecogs.com/gif.latex?2%5E%7Bj-1%7D%20%5Cleq%20i%20%3C%202%5E%7Bj%7D-1
[color_Red_ 2_k_-1]: https://latex.codecogs.com/gif.latex?%7B%5Ccolor%7BRed%7D%202%5E%7Bk%7D-1%7D
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e6ddd039453e431e967cc30c98f92a7a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_14_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/9bda5eb1d91e4294a5c5b925e8e15348.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/fea0c3f5b334446cbac6235ad9c92ffb.png
[a _ b _ _c - d_ - e _ f]: https://latex.codecogs.com/gif.latex?a%20&plus;%20b%20*%20%28c%20-%20d%29%20-%20e%20/%20f
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ae113e7d04bc44d692041841ff826d3c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/6e383f379b8a4ef8b4620d2318e5ec53.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/97760b706faf4a8b808a11fffe8a67f7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/31350927b78b41388f5600e97c47c078.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXVuZmFuMTg4_size_10_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/58d1acf8c52947cf89b4b7d3be8e3303.png
[6_ _ - _.]: https://www.cnblogs.com/kangjianwei101/p/5233781.html