数据结构(四) 2018-12-21

本篇，我们来讨论一种一对多的数据结构 —— 树。

树(Tree)

---

概述

树是 n(n >= 0) 个节点的有限集。当 n = 0 时，称为空树。在任意一棵非空树中:

1. 有且仅有一个特定的称为根(root)的节点
2. 当 n >= 1 时，其余节点可分为 m(m > 0)个互不相交的有限集 T₁、T₂、…、T_m，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)

对于树，还需要注意两点:

1. n > 0 时根节点是唯一的，不可能存在多个根节点
2. m > 0 时，子树的个数没有限制，但他们一定互不相交

节点分类

树的节点包含一个数据元素以及若干个指向其子树的分支。节点拥有的子树的个数称为节点的度(Degree)。
度为 0 的节点成为叶节点(Leaf)。度不为 0 的节点称为分支节点。
除了根节点之外的分支节点又称为内部节点。

节点间的关系

节点的子树的根成为该节点的孩子(Child)，相应的该节点称为孩子的双亲(Parent)。同一双亲的孩子之间互称为兄弟(Sibling)。

树的其他概念

节点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。树中节点的最大层次称为树的深度(Depth)。
如果将树中节点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林(Forest)是 m(m >= 0)棵互不相交的树的集合。

二叉树

---

二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合，该集合或为空集(空二叉树)，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点

• 每个节点最多有两棵子树，所以二叉树中不存在度大于 2 的节点。注意不是只有而是最多有，没有或者有一棵子树也是可以的
• 左子树和右子树是有顺序的
• 即使树中某节点只有一棵子树，也要区分他是左子树还是右子树

二叉树具有五种基本形态:

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点既有左子树又有右子树

特殊二叉树

斜树

所有节点都只有左子树的二叉树叫做左斜树。所有节点都只有右子树的二叉树叫做右斜树。二者统称为斜树。
线性表结构就可以理解为是树的一种极其特殊的表现形式。

满二叉树

在一棵二叉树中，如果所有的分支节点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点:

1. 叶子只能出现在最下层
2. 非叶子节点的度一定是 2
3. 在同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多

完全二叉树

对一棵具有 n(n >= 0)个节点的二叉树按层序编号，如果编号为 i(1 <= i <= n)的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
注意: 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

完全二叉树的特点:

1. 叶子节点只能出现在最下两层
2. 最下层的叶子一定集中在左部连续位置
3. 倒数第二层，若有叶子节点，一定都在右部连续位置
4. 如果节点度为 1，则该节点只有左孩子
5. 同样节点数的二叉树，完全二叉树的深度最小

二叉树的性质

1. 在二叉树的第 i 层上最多有 2^i-1 个节点(i >= 1)
2. 深度为 k 的二叉树最多有 2^k - 1 个节点
3. 对任何一棵二叉树 T，如果其叶节点个数为 n₀，度为 2 的节点数为 n₂，则 n₀ = n₂ + 1

二叉树的存储结构

对于二叉树使用顺序存储适用性不强，一般使用链式存储结构。二叉树每个节点最多有两个孩子所以为他设计一个数据域和两个指针域，我们称这样的链表为二叉链表。

class BiTNode<T>
{
    public T Element;
    public BiTNode<T> LChild;
    public BiTNode<T> RChild;
    
    public BiTNode(T t)
    {
        Element = t;
    }
}

遍历二叉树(Traveing Binary Tree)

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

这里有两个关键词: 访问和次序

二叉树遍历方法

主要分为四种:

1. 前序遍历: 规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树(根-左-右)
2. 中序遍历: 规则是若二叉树为空，则空操作返回，否则从根节点开始(注意并不是先访问根节点)，中序遍历根节点左子树，然后访问根节点，最后中序遍历右子树(左-根-右)
3. 后序遍历: 则是若二叉树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点(左-右-根)
4. 层序遍历: 则是若二叉树为空，则空操作返回，否则从树的第一层开始，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对节点逐个访问

注意: 前、中、后代表的是根节点位置。

public void PreOrderTraverse(BiTNode<T> node)
{
    if (node != null)
    {
        Console.WriteLine(node.Element);
        PreOrderTraverse(node.LChild);
        PreOrderTraverse(node.RChild);
    }
    return Data;
}

public void InOrderTraverse(BiTNode<T> node)
{
    if (node != null)
    {
        InOrderTraverse(node.LChild);
        Console.WriteLine(node.Element);
        InOrderTraverse(node.RChild);
    }
    return Data;
}

public void PostOrderTraverse(BiTNode<T> node)
{
    if (node != null)
    {
        PostOrderTraverse(node.LChild);
        PostOrderTraverse(node.RChild);
        Console.WriteLine(node.Element);
    }
    return Data;
}

二叉树遍历的性质:

1. 已知前序遍历和中序遍历，可以唯一确定一棵二叉树
2. 已知后序遍历和中序遍历，可以唯一确定一棵二叉树
3. 已知前序遍历和后序遍历，是不可以唯一确定一棵二叉树