什么是树

  • 是一种层次结构 (家谱 / 社会组织 / 图书馆 / 电脑的文件树)
  • 层次结构效率更高 (数据管理的基本操作 : 查找)

查找 Search

  • 根据某个给定关键字 K , 从集合R中找出关键字与K相同的记录
  • 分为静态查找(集合中记录固定) : 没有插入和删除操作
    和动态查找(集合中记录是变化的) : 除了查找还可能发生插入和删除
  • 静态查找 例子 : 查字典
  • 动态查找 例子 : - -

静态查找

方法1 顺序查找

用数组
哨兵的目的
image.png
时间复杂度为 三 : 树(上) - 二叉树及其遍历 - 图2

方法2 二分查找

数据结构 : 二叉查找树 二叉查找树有两个属性 : 1. 所有结点都比左子树中的结点大 2. 所有结点都比其右子树的结点小
根据属性有如下性质 : 二叉查找树最小结点位于最顶端结点最左边的子树的末尾
最大结点位于最顶端结点最右边的子树的末尾

二叉树

定义

由根节点和左子树、右子树组成
image.png

特殊二叉树

  • 斜二叉树 (相当于链表)
  • 完美二叉树 / 满二叉树
  • 完全二叉树 (相对于完美二叉树而言 允许缺少叶子结点)

image.png

重要性质

(1) 一个二叉树第 i 层的最大结点数为 : 三 : 树(上) - 二叉树及其遍历 - 图5
(例如第三层最大节点数是 2 = 4 , i = 3)
(2) 深度为 k 的二叉树由最大结点总数为 : 三 : 树(上) - 二叉树及其遍历 - 图6 (满二叉树时)
(例如第三层最大节点总数为 1+2+4 = 7 )
(3) 对任何非空二叉树T , 若 n 表示叶结点的个数 , n 是度为2的非叶结点个数 , 那么两者满足关系 三 : 树(上) - 二叉树及其遍历 - 图7
(度 : 结点的分支数)

image.png 三 : 树(上) - 二叉树及其遍历 - 图9

操作集

  1. 判别二叉树是否为空 : Boolean IsEmpty(BinTree BT)
  2. 遍历 , 按顺序访问每个结点 : void Traversal(BinTree BT)
  3. 创建二叉树 : BinTree CreateBinTree()

存储结构

  1. 顺序存储结构 (用数组实现)
    **完全二叉树 : 从上至下、从左至右顺序存储
    image.png

**性质(1) : 非根结点 (序号i>1)的父节点的序号是 i/2 例如 B C
性质(2) : 结点 i 的左孩子结点的序号是 **2i**** , 有孩子序号是 2i+1
( 2i<=n , 否则没有左孩子 / 2i+1<=n , 否则没有右孩子 )

**对于一般二叉树 , 也可以采用这种结构 , 方法是补齐空结点 , 但这样会造成空间浪费
image.png

  1. 链表存储结构定义结构为 :
    image.png
    数据 + 左指针 + 右指针 = 一个元素 ( ^ 表示空指针)

image.png

二叉树的遍历

(这里使用链式存储结构的遍历 , 主要有如下四种形式)

常用的遍历方法

  1. 先序遍历 : 根 -> 左子树 -> 右子树 PreOrderTraversal
  2. 中序遍历 : 左子树 -> 根 -> 右子树 InOrderTraversal
  3. 后序遍历 : 左子树 -> 右子树 -> 根 PostOrderTraversal
  4. 层次遍历 : 从上到下、从左到右 LevelOrderTraversal

先序遍历

过程为 :

  • 访问根节点
  • 先序遍历其左子树 (递归地)

  • 先序遍历其右子树 (递归地)

    1. void PreOrderTraversal( BinTree BT )
    2. {
    3.   if(BT){        /*判断是否为空,不为空则继续,空则直接结束*/
    4.       printf("%d", BT->Data);
    5.       PreOrderTraversal(BT->Left);
    6.       PreOrderTraversal(BT->Right);
    7.   }
    8. }

    访问顺序 :
    image.png
    起始时指针指向 A 的位置 ; 对左子树递归 (B D F E) 然后回到A ; 对右子树递归 (C G H I )
    先序遍历 : A B D F E C G H I
    **

    中序遍历

    过程为 :

  • 中序遍历其左子树 (递归地)

  • 访问根节点
  • 中序遍历其右子树 (递归地)
    void InOrderTraversal( BinTree BT )
{
  if(BT){        /*判断是否为空,不为空则继续,空则直接结束*/
      InOrderTraversal(BT->Left);
      printf("%d", BT->Data);
      InOrderTraversal(BT->Right);
  }
}
    先遍历左边 , 所以从最左边的子节点 D 开始遍历 , 左 根 右的顺序
    中序遍历 ：(D B E F) A (G H C I)

后序遍历

过程为 :

  • 后序遍历其左子树 (递归地)
  • 后序遍历其右子树 (递归地)

  • 访问根节点

    void PostOrderTraversal( BinTree BT )
{
  if(BT){        /*判断是否为空,不为空则继续,空则直接结束*/
      PostOrderTraversal(BT->Left);
      POstOrderTraversal(BT->Right);
      printf("%d", BT->Data);
  }
}

    左 右 根 , 所以对于左子树来说从D开始然后右边最后到 B
    后序遍历 : (D E F B) (H G I C) A
    **

    重点

  • 先序、中序和后序遍历 : 遍历过程中经过结点的路线一样 , 只是访问各结点的时机不同
    (路线会经过同一条结点2次 , 打印次序的不同决定是哪种遍历)

image.png

备注

实际上是用堆栈实现递归 , 下面讲解如何把递归变成非递归

二叉树的非递归遍历

有没有可能直接用堆栈实现遍历而非递归 ?

中序遍历的非递归遍历算法

image.png
五角星代表中序 , 顺序为(D B E F) A (G H C I)
从入口进经过 A 时不print , 先把 A 存进堆栈 ;
经过 B 时不print , 把 B 存进堆栈 ;
经过 C 时存入并且取出 , 直接print ;
以此类推

  • 遇到结点 , 把它压栈 , 并去遍历左子树
  • 左子树遍历结束后 , 从栈顶弹出这个结点并访问
  • 然后按其有指针再去中序遍历该结点的右子树
    void InOrderTraversal(BinTree BT)
{
  BinTree T = BT;        /*把BT赋给临时变量T*/
  Stack S = CreateStack(MaxSize);        /*创建并初始化堆栈S*/
  while(T || !IsEmpty(s) ){
      while(T){    /*一直向左并将沿途结点压入堆栈*/
          Push(S , T);
          T = T->Left;
      }
      if(!IsEmpty(S)){
          T = Pop(S);        /*结点弹出堆栈*/
          printf("%5d", T->Data);        /*访问结点(打印结点)*/
          T = T->Right;        /*转向右子树*/
      }
  }
}

中序遍历的非递归遍历算法

电路符号代表先序 , 顺序为 A (B D F E) (C G H I)
**
image.png

按中序遍历的代码修改 :
image.png

后序遍历的非递归遍历算法

课后题

1 后序遍历实在第三次访问结点（最后一次访问结点）时，将结点的数据打印出来。但在老师给的框架中，只出现前两次的访问经过。我的解决办法是，对于能够出现第三次访问的结点（即存在左右儿子的结点），在第二次访问时，再压栈，当其右儿子访问过之后，再出栈，打印数据。具体代码如下，大家可以用递归的算法验证一下，我目前只验证了老师例子的情况。可能会有错误

2 我认为不能，因为在前序和中序遍历中，只须分别在入栈、出栈时打印出值就可以了，分别对应二叉树遍历中的第一次经历、第二次经历。而后序遍历是第三次经历时才能打印出值，而此时数据早已出栈， 我们无法获得相关信息，自然无法打印出值。
所以我的思路是出栈时先获取T->right中的地址信息，然后push一个right指针信息为空的结点入栈，这样就可以存储值的信息了。以下是我的代码，望各位批评指正。

void PostOrderTraversal(BinTree BT)
{
    Bintree Q;
    BinTree T = BT;
    stack S = CreatStack(Maxsize);

    while( T || !Empty(S)){
        while(T){
            Push(S, T);
            T = T->left;    
        }
        if(!Empty(S)){
            T = Pop(S);
            if(T->right){
                Q = (BinTree *)malloc(sizeof BinTree);
                Q->Data = T->Data;
                Q->right = NULL;
                Push(S,Q);
            }else{
                printf("%d", T->Data);
            }
            T = T->right;
        }
    }
}

二叉树的层序遍历

二叉树遍历的核心问题是 : 二维结构的线性化 (怎么样把二维结构变成一维线性的结构 的过程 )
(因此使用不同的方法遍历 产生的一维线性序列不同)

二维 → 一维 的问题点 :

  • 从结点访问其左右儿子结点
  • 访问左儿子后 , 右儿子结点怎么半 ?
    -> 需要一个存储结构保存暂时不访问的结点
    -> 存储结构 : 堆栈(访问左儿子保存自己)、队列(访问自己把右儿子存在队列里)

**

队列实现

遍历从根节点开始 , 首先将根节点入队 , 然后开始执行循环 : 结点出队、访问该结点、其左右儿子入队

每次循环 : 抛出根节点 , 把其左右儿子放进去
image.png (抛出A放进B C)
image.png(抛出B 放进 D F)

image.png(抛出 C 放进G I)
image.png(抛出 D )
image.png(抛出F 放进 E)
(抛出G 放入 H) -> (抛出I) -> (抛出E) -> (抛出H)

层序遍历 : A B C D F G I E H (按层次从上至下 顺序从左至右访问)
**

基本过程

  1. 根节点入队
  2. 从队列中取出一个元素
  3. 访问该元素所指结点
  4. 若该元素所指结点的左右孩子结点非空 , 则将其左右孩子的指针顺序入队

实现

void LevelOrderTraversal(BinTree BT)
{
    Queue Q; BinTree T;
    if(!BT) return;        /*若是空树则直接返回*/
    Q = CreateQueue(MaxSize);        /*创建并初始化队列Q*/
    AddQ(Q, BT);
    while(!IsEmptyQ(Q)){
        T = DeleteQ(Q);
        printf("%d\n",T->Data);        /*访问取出队列的结点*/
        if(T->Left)    AddQ(Q, T->Left);
        if(T->Right)    AddQ(Q, T->Right);
    }
}

堆栈实现

前序遍历：直接改为堆栈，其中将入栈顺序改为先右儿子后左儿子，即为前序遍历。
中序遍历：结点出栈时，如果是第一次出栈，则按照右儿子、当前结点、左儿子顺序入栈，然后如果是第二次出栈，则输出。即为中序遍历。
后序遍历：把中序遍历中的第一次出栈后的入栈顺序改为当前结点、右儿子、左儿子。即可得到后序遍历。

也是一种树的遍历。如果直接将队列改成堆栈，那么得到的遍历结果就是根节点>右子树>左子树的顺序。
如果节点出栈时是先压入右节点再压入左节点，那么得到的就是前序遍历。
如果节点出栈时按照右节点>自身>左节点的顺序压入（第二次出栈时才打印出来），可以实现中序遍历。
如果节点出栈时按照自身>右节点>左节点的顺序压入，可以实现后序遍历。

遍历的应用

输出叶子结点

例1 : 已知一颗二叉树 , 输出二叉树中的叶子结点

思路 : 在二叉树遍历算法中增加检测结点的 “左右子树是否都为空”
(改造先序遍历)

void PreOrderTraversal( BinTree BT )
{
    if(BT){        /*判断是否为空,不为空则继续,空则直接结束*/
        if(!BT->Left && !BT->Right)            /*此行为新增条件,本题答案*/
            printf("%d", BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

求二叉树的高度

(能不能用递归来算 ?)
image.png
(改造后序遍历)

int PostOrderGetHeight(BinTree BT)
{
    int HL, HL, MaxH;
    if(BT){
        HL = PostOrderGetHeight(BT->Left);    /*求左子树的深度*/
        HR = PostOrderGetHeight(BT->Right); /*求右子树的深度*/
        MaxH = (HL>HR) ? HL ; HR;    /*取左右子树较大的深度*/
        return (MaxH +1);
    }
    else return 0;    /*空树深度为0*/
}

二元运算表达式树及其遍历

表达式树 : 叶子结点是运算数 , 非叶子结点是运算符
image.png
表示表达式 : 三 : 树(上) - 二叉树及其遍历 - 图26

三种遍历可以得到不同的访问结果 :
image.png
中缀表达式不准确 , 会受到运算优先级的影响
如何解决 ? - 遍历时每到左子树的时候加左括号

由两种遍历序列确定二叉树

已知三种遍历中的任意两种遍历序列 , 能否唯一确定一颗二叉树呢 ?
**不行 , 必须有中序才能唯一确定 (不然没法区分哪边是左和右)
image.png

先序和中序确定一颗二叉树

分析 :

  • 根据先序遍历序列第一个结点确定根结点
  • 根据根结点在中序遍历序列中分割出左右两个子序列
  • 对左子树和右子树分别递归使用相同的方法继续分解

image.png

image.png

小测验

image.png

课件

3.3 二叉树的遍历(1).pdf

C语言实现 : 四种遍历

void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此处假设对BT结点的访问就是打印数据 */
        printf("%d ", BT->Data); /* 假设数据为整型 */
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; /* 若是空树则直接返回 */

    Q = CreatQueue(); /* 创建空队列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 访问取出队列的结点 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}