数据结构整理(二) 树

一、前言

　　项目源码及其他声明等参见数据结构（一）线性结构篇。

二、相关概念

　　树作为一种应用广泛的一对多非线性数据结构，不仅有数据间的指向关系，还有层级关系，示例见图一。因树的结构比较复杂，为了简化操作及存储，我们一般将树转换为二叉树处理，因此本文主要讨论二叉树。

1. 二叉树
   　　二叉树是每个节点最多拥有两个子节点的树结构，若移除根节点则其余节点会被分成两个互不相交的子树，分别称为左子树和右子树。二叉树是有序树，左右子树有严格的次序，若颠倒则成为一棵不一样的二叉树。
2. 满二叉树
   　　满二叉树，顾名思义除叶子节点外所有节点都拥有两个孩子，且叶子节点在同一层的二叉树，示例见图二。
   
3. 完全二叉树
   　　完全二叉树，移除最后一层节点后是满二叉树，且最后一层的节点都连续集中在最左面，示例见图三。

三、二叉树存储结构

1. 顺序存储
   　　根据完全二叉树的特性，可以计算出任意节点n的双亲节点及左右孩子节点的序号，因此完全二叉树的节点可以按照从上到下从左到右的顺序依次存储到一维数组中。非完全二叉树存储时应先将其改造为完全二叉树，以空替代不存在的节点，比较浪费存储空间，存储示意图见图四。
   
2. 链式存储
   　　树结构链式存储类似线性结构链式存储，先定义包含数据域和引用域的节点(Node)，然后通过引用域存储节点之间的关系。根据二叉树的结构来看，节点Node至少包含数据域(Data)，引用域(左孩子LChild、右孩子RChild)，为了方便通过孩子节点查找父节点，引用域中可以考虑添加父节点引用(Parent)，存储示意图见图五。
   

四、树与二叉树的转换

1. 树转二叉树

   加线，所有兄弟结点之间加一条连线。
   抹线，对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线。
   整理，整理前两步得到的树，使之结构层次分明。

   
2. 二叉树转树
   

   加线，若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来。
   抹线，删除原二叉树中所有结点与其右孩子结点的连线。
   整理，整理前两步得到的树，使之结构层次分明。
   

五、树遍历实现

/// <summary>
/// 先序遍历（DLR）
/// </summary>
/// <![CDATA[首先访问跟节点，然后遍历左子树，最后右子树]]>
static void PreOrder(Node<char> root)
{
    if (root == null)
    {
        return;
    }

    Print(root);
    PreOrder(root.LChild);
    PreOrder(root.RChild);
}

/// <summary>
/// 中序遍历（LDR）
/// </summary>
/// <![CDATA[先遍历左子树，然后根节点，最后遍历右子树]]>
static void InOrder(Node<char> root)
{
    if (root == null)
    {
        return;
    }

    InOrder(root.LChild);
    Print(root);
    InOrder(root.RChild);
}

/// <summary>
/// 后序遍历（LRD）
/// </summary>
/// <![CDATA[先遍历左子树，然后遍历右子树，最后遍历根节点]]>
static void PostOrder(Node<char> root)
{
    if (root == null)
    {
        return;
    }

    PostOrder(root.LChild);
    PostOrder(root.RChild);
    Print(root);
}

/// <summary>
/// 层序遍历
/// </summary>
/// <![CDATA[从上向下从左到右]]>
static void LevelOrder(Node<char> root)
{
    if (root == null)
    {
        return;
    }
    CSeqQueue<Node<char>> sq = new CSeqQueue<Node<char>>(50);
    sq.In(root);
    while (!sq.IsEmpty())
    {
        Node<char> tmp = sq.Out();
        Print(tmp);

        if (tmp.LChild != null)
        {
            sq.In(tmp.LChild);
        }

        if (tmp.RChild != null)
        {
            sq.In(tmp.RChild);
        }
    }
}