树

树（Tree）: n（n≥0）个结点构成的有限集合。 当n=0时，称为空树； 对于任一棵非空树（n> 0），它具备以下性质：

  • 树中有一个称为“根（Root）”的特殊结点，用 r 表示；
  • 其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其 中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”

树的一些基本术语

  1. 结点的度（Degree）：结点的子树个数
  2. 树的度：树的所有结点中最大的度数
  3. 叶结点（Leaf）：度为的结点
  4. 父结点（Parent）：有子树的结点是其子树 的根结点的父结点
  5. 子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也 称孩子结点。
  6. 兄弟结点（Sibling）：具有同一父结点的各 结点彼此是兄弟结点。
  7. 路径和路径长度：从结点n1到nk的路径为一 个结点序列n1 , n2 ,… , nk , ni是 ni+1的父结 点。路径所包含边的个数为路径的长度。
  8. 祖先结点(Ancestor)：沿树根到某一结点路 径上的所有结点都是这个结点的祖先结点。
  9. 子孙结点(Descendant)：某一结点的子树 中的所有结点是这个结点的子孙。
  10. 结点的层次（Level）：规定根结点在1层， 其它任一结点的层数是其父结点的层数加1。
  11. 树的深度（Depth）：树中所有结点中的最 大层次是这棵树的深度。

树的表示

数组？

--- 树的分枝是不确定的，因此用数组表示不太方便链表？

  • 常规表示

    劣势：此种链表表示方法由于子结点的个数不确定，因此需要多个结构来实现。

    如是直接选取子结点最多的结构来代替所有结构，简化了结构，但会造成资源浪费。

  • 儿子兄弟表示法

    链表结构固定，两个指针，第一个指针指向他的第一个儿子，第二个指针指向他旁边的兄弟，如不存在，则指针为空。如下图所示：

二叉树

  • 定义：一个有穷的结点集合，由根结点和称为其左子树T_L和右子树T_R的两个不相交的二叉树组成（非空集合）。也可以说是特殊度为2的树，有左右之分。

相关概念：

  1. 叶结点：没有子节点的结点，个数表示为n_0
  2. 只有一个子节点的结点，个数表示为n_1
  3. 有两个子节点的结点，个数表示为n_2

  • 由左至右分别为：空树

  • 特殊二叉树：

  • 斜二叉树：只有一边的结点

  • 完美二叉树：所有根节点都由两个子结点

  • 完全二叉树：相对于完美二叉树而言，最后一层的子节点可以缺项，但是从上至下从左往右编号时，前面的编号和完美二叉树完全一致

性质：

​ 1. 一个二叉树第i层的最大结点数为：2^(i-1) , i >= 1 ​ 2. 深度为k的二叉树有最大的结点总数为：2^k-1 , k >= 1 ​ 3. 对于任何非空二叉树，若 n_0 表示叶节点个数，n_2是度为2的非叶节点个数，那么两者之间满足关系 n_0 = n_2 +1

证明：一个二叉树的两个结点之间的连线可以看作一条边，由下往上看，每一个结点都有一条边，除去根节点，所以，节点数 = 边数 + 1

由上往下看，则可以得到如下等式：n_0 + n_1 + n_2 - 1（节点数）= 0 * n_0 + 1 * n_1 + 2 * n_2（边数，由上往下看，结点拥有子节点的个数等于其边数），化简即可证得。

二叉树的存储结构

### 顺序存储结构：

完全二叉树：从上至下、从左到右的方式进行顺序存储

Q：储存后相关操作是否方便？
A ：方便，相关操作是有规律的

  • 非根节点 (序号 i > 1) 的父节点序号是 [i/2]

  • 结点（序号为 i ）的左孩子结点是 2i （若 2i <= n , 否则没有左孩子）

  • 结点（序号为 i ）的右孩子结点是 2i+1 （若 2i+1 <= n , 否则没有右孩子）

一般二叉树：存储方式同完全二叉树，如结点有缺，则在数组中留出空位

缺点：会造成空间浪费。

链表存储

儿子兄弟表示法

二叉树的遍历

先序遍历：void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树；

中序遍历：void InOrderTraversal( BinTree BT )： 中序---左子树、根、右子树；

后序遍历：void PostOrderTraversal( BinTree BT )：后序---左子树、右子树、根

层次遍历：void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右

先序遍历

遍历过程为：

​ 1. 访问根节点 ​ 2. 先序遍历左子树 ​ 3. 先序遍历右子树

1
2
3
4
5
6
7
void PreOrderTraversal ( BinTree BT){     // 先序遍历           
    if  ( BT ){            
        printf ("%d", BT->Data);      // 输出节点            
        PreOrderTraversal ( BT->Left );     //对左边进行递归
        PreOrderTraversal ( BT->Right );    // 对右边进行递归      
    }
}

输出顺序如图所示：

中序遍历

遍历过程为： 1. 中序遍历其左子树； 2. 访问根结点； 3. 中序遍历其右子树。

1
2
3
4
5
6
7
void  InOrderTraversal ( BinTree BT ){    // 中序遍历          
    if  ( BT ){            
        InOrderTreversal ( BT->Left );            
        printf  ( "%d" , BT->Data );           
        InOrderTreversal ( BT->Right );      
    }
}

输出顺序如图所示：后序遍历遍历过程为： 1. 后序遍历其左子树； 2. 后序遍历其右子树； 3. 访问根结点。

1
2
3
4
5
6
7
void PostOrderTraversal ( BinTree BT ){     // 后序遍历          
    if  ( BT ){            
        PreOrderTraversal ( BT->Left );     //对左边进行递归            
        PreOrderTraversal ( BT->Right );    // 对右边进行递归            
        printf ("%d", BT->Data);      // 输出节点      
    }
}

输出顺序如图所示：

以上三种遍历均属于递归遍历

我们可以发现，上述三种遍历，经过节点的路线都是一样的，之时访问节点的时机不同，也就是输出顺序不同。

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

基本思路：使用堆栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void  InOrderTraversal ( BinTree  BT ){      
    BinTree  T = BT ;       //  简化树的变量名      
    Stack S = CreatStack ( MaxSize );   // 创建并初始化堆栈     
    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 ;    // 转向右子树           
        }     
    }
}

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

递归实际也是一种用堆栈实现的算法，所以两种方式实现是相同的，只不过不用递归，直接采用建立堆栈，用压栈弹栈进行操作而已。

层序遍历

使用队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
void  LevelOrderTraversal  ( BinTree  BT ){
      Queue  Q ;  // 创建队列
      BinTree  T ;      // 创建临时二叉树
      if  ( !BT )       return ;   // 是空树则直接返回
      AddQ ( Q , BT ) ;
      while ( !IsEmptyQ (Q) ){      // 循环 直至队列为空
            T = DelateQ ( Q );
            printf ( "%d\n" , T->Data ) ;       // 访问取出队列的结点  
            if ( T->Left )    AddQ( Q , T->Left ) ;
            if ( T->Right )   AddQ( Q , T->Right ) ;
      }
}

遍历二叉树的应用

输出二叉树中的叶节点

由题意可知，输出叶节点，也就是输出没有没有左右子树的结点，那么我们使用前序便历，在输出之时，检测其是否有左右子树。代码如下：

1
2
3
4
5
6
7
8
void PreOrderPrintLeaves( BinTree BT ){
    if( BT ){
        if ( !BT-Left && !BT->Right )
            printf(“%d”, BT->Data );
        PreOrderPrintLeaves ( BT->Left );
        PreOrderPrintLeaves ( BT->Right );
    }
}

求二叉树的高度

二叉树的高度等于左右子树最高的高度，所以遍历之时添加计数功能。

1
2
3
4
5
6
7
8
9
10
int PostOrderGetHeight( BinTree BT ) {
      int HL, HR, MaxH;
      if( BT ) {
            HL = PostOrderGetHeight(BT->Left);  //求左子树的深度
            HR = PostOrderGetHeight(BT->Right);       // 求右子树的深度
            MaxH = （HL > HR）? HL : HR;    // 取左右子树较大的深度
            return ( MaxH + 1 );   // 返回树的深度
      }
      else return 0;    // 空树深度为0
}

二元运算表达树及其遍历

三种遍历得到不同的访问结果

  • 先序遍历得到前缀表达式

  • 中序遍历得到中缀表达式：但是中缀表达式可能由于优先级不同，出现问题

    ---- 如何解决？ 输出左子树之前加左括号，输出右子树之后加右括号

  • 后序遍历得到后续表达式

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

Q：可以是任意两种吗？ A：不可以，确定之时必须要有中序遍历，仅仅依靠前序和后序无法确定出一个唯一的树

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