【数据结构与算法】之树的概念与使用

什么是树？

一、概念

• 树：n（n>=0）个结点的有限集。

二、特点

• n=0时，称为空树；
• 在任意一颗非空树中：
  ① 有且仅有一个根结点
  ② 当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。

三、结点分类

• 结点拥有的子树数称为结点的度（Degree）；
• 度为0的结点称为叶结点（Leaf） 或 终端结点；度不为0的结点称为非终端结点 或 分支结点；
• 除根节点之外，分支结点也称为内部结点；
• 树的度是树内结点的度的最大值。

四、结点间关系

• 结点的子树的根称为该节点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）；
• 同一个双亲的孩子之间互称兄弟（Sibling）；
• 结点的祖先是从根结点到该节点所经分支上的所有结点（包括根结点）；
• 以某结点为根的子树中任一结点都称为该结点的子孙。

五、树的其他概念

• 结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。
• 双亲在同一层的结点互称为堂兄弟。
• 树中结点的最大层次称为书的深度（Depth）或高度。
• 如果左右子树是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
• 森林（Forest）是m（m >= 0）课互不相交的树的集合。

六、线性结构 VS 树结构

七、树的抽象数据类型

ADT 树（tree）
    树是由一个根结点和若干课子树构成。树中结点具有相同数据类型及层次关系。
Operation
    root：返回根结点。
    nodes：树的结点数
    depth：树的深度
    ...
EndADT

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

二叉树

一、概念

• n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者为由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
• 每个结点最多有两颗子树；左子树和右子树是有顺序的；一个结点如果只有一颗子树，也要区分左右；
• • 左斜树如下：

• • 右斜树如下：

• 斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
• 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树的特点有：
• • 叶子只能出现在最下一层。出现在其它层就不可能达成平衡；
• • 非叶子结点的度一定是2；
• • 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

• 完全二叉树：对一颗具有n个结点的二叉树按层编号，编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点：
• • 叶子结点只能出现在最下层和次下层；
• • 最下层的叶子结点集中在树的左部；
• • 倒数第二层若存在叶子结点，一定在右部连续位置；
• • 如果结点度为1，则该结点只有左孩子，即没有右子树；
• • 同样结点数目的二叉树，完全二叉树深度最小。

• 注意：满二叉树一定是完全二叉树，但反过来不一定成立。

二、二叉树的基本形态

• 空二叉树（没有结点，包括根结点）
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根结点有左右子树

三、二叉树的特点

• 在二叉树的第i层最多有2^(i-1)的结点（i>=1）。(最多结点的二叉树是满二叉树，除了叶结点，所有结点的度都为2，所以，第i层最多有2^(i-1)个结点)
• 深度为k的二叉树至多有2^k-1个结点（k>=1）。(由性质1可以每层的结点数，则k（k>=1）层二叉树总共节点数为：n = 2⁰ + 2¹ + … 2^(k-1)=1*(1-2^k)/(1-2) = 2^k - 1)
• 对任何一颗二叉树T，如果其终端结点数为n₀ ，度为2的结点数为n₂，则n₀ = n₂+1。(二叉树的总结点数为：n = n₀ + n₁ + n₂（n₀为叶结点，n₁为度为1的结点数，n₂为度为2的结点数）；那么结点数为n的二叉树有多少条连接线呢？很明显每个结点，除了根结点都有指向连接线，所以，结点数为n的二叉树的总连接线为n-1；从一个结点的度来算，度为1的结点会有1条连接线，连接子结点；度为2的结点会有2连接线，连接子结点；根结点没有双亲结点，所以没有连向根结点的连接线，那么有：n-1 = 1n₀ + 2n₂；和第一条方程式联合可得：n₀=n₂+1)
• 具有n个结点的完全二叉树的深度为⎣log2(n)⎦ + 1（⎣x⎦表示不大于x的最大整数）。
• 如果对一颗有n个结点的完全二叉树（其深度为|log2(n)| + 1）的结点按层编号（从第1层到第|log2(n) + 1|层，每层从左到右），对任一结点i（1 <= i <= n）有：
  如果i=1，则结点i是二叉树的根结点，无双亲；如果i>1，则其双亲是结点|i/2|。
  如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
  如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

四、二叉树的存储结构

• 二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引，一棵完全二叉树采用顺序存储方式，如下所示：

• 当二叉树为完全二叉树时，结点数刚好填满数组，如下所示：

• 那么当二叉树不为完全二叉树时，采用顺序存储形式如何呢？例如：如下描述的二叉树，浅色结点表示结点不存在：

• 如果二叉树的顺序存储结构如下所示，其中，∧表示数组中此位置没有存储结点，此时可以发现，顺序存储结构中已经出现了空间浪费的情况：

• 如下所示的右斜树极端情况对应的顺序存储结构，对于这种右斜树极端情况，采用顺序存储的方式是十分浪费空间的，因此顺序存储一般适用于完全二叉树：

五、二叉链表

• 既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域，如下所示：

• 定义结点代码：

	typedef struct BiTNode{
	    TElemType data;                  // 数据
	    struct BiTNode *lchild, *rchild; // 左右孩子指针
	} BiTNode, *BiTree;

  

 

  
1
  
2
  
3
  
4
 

• 上面顺序存储结构的二叉树可以表示为如下形式的二叉链表：

六、二叉树遍历

• 二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问有且仅有一次。

class BinTNode<T>: NSObject{
    var data: T
    var lChild: BinTNode<T>?
    var rChild: BinTNode<T>?
    init(_ data: T) {
        self.data = data
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

• 前序遍历：若二叉树为空，则返回；否则，先遍历根结点，然后遍历左子树，再遍历右子树。

// 前序遍历
func preOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    
    print(tNode.data)
    preOrderTraverse(t: tNode.lChild)
    preOrderTraverse(t: tNode.rChild)
}
// 前序遍历结果：ABDHIEJCFG => A->(B->(D->H->I)->(E->J))->(C->F->G)

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

• 中序遍历：如果二叉树为空，则返回；否则，从根结点开始，先遍历左子树，然后是根结点，左后是右子树。

// 中序遍历
func inOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    inOrderTraverse(t: tNode.lChild)
    print(tNode.data)
    inOrderTraverse(t: tNode.rChild)
}
// 中序遍历结果：HDIBJEAFCG => ((H<-D->I)<-B->(J<-E))<-A->(F<-C->G)


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

• 后续遍历：如果二叉树为空，则返回；否则，从根结点开始，先遍历左子树，然后遍历右子树。

// 后序遍历
func postOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    postOrderTraverse(t: tNode.lChild)
    postOrderTraverse(t: tNode.rChild)
    print(tNode.data)
}
// 后序遍历结果：HIDJEBFGCA => ((H->I->D)->(J->E)->B)->(F->G->C)->A

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

• 层序遍历：如果二叉树为空，则返回；否则，从树的第一层，根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序逐个结点访问。

// 层叙遍历
func layerOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    
    var array: [BinTNode<String>] = [tNode]
    while !array.isEmpty {
        let count = array.count
        for i in 0...count-1 {
            let node = array[i]
            print(node.data)
            if let lNode = node.lChild {
                array.append(lNode)
            }
            if let rNode = node.rChild {
                array.append(rNode)
            }
        }
        array.removeSubrange(Range.init(NSRange(location: 0, length: count))!)
    }
}
// 层序遍历结果：ABCDEFGHIJ => A->(B->C)->(D->E->F->G)->(H->I->J)

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/Forever_wj/article/details/107560730