37.2° Blog

1.孩子-兄弟表示法

一棵树的父亲结点可以有任意个孩子，为了让其像二叉树一样进行遍历，将其转化为二叉树形态。

树转化为二叉树：

• 将每个结点的第一个孩子置为树中的左孩子；
• 将同层级中相邻的第一个兄弟值为树中的右孩子

这种表示方法称之为孩子-兄弟表示法，又称树的二叉链表表示。

1.1树 → 二叉树

1.2二叉树 → 树

1.3 数据结构

typedef int ElemType;
typedef struct CSNode
{
    ElemType data;              // 数据域
    struct CSNode* firstchild;  // 第一个孩子
    struct CSNode* nextsibling; // 第一个孩子的右兄弟
}CSNode, *CSTree;

2.树的遍历

在树中一个父亲节点可以有多个孩子节点，无左右子树的概念，也无法确定同意层级结点遍历的顺序，即不存在中根遍历方式。

2.1 先根遍历

算法思想

先访问根结点，然后依次先根遍历每棵子树；

上图中，获得先根遍历序列：{1,2,4,5,6,3,7}

孩子兄弟链表表示的二叉树的先序遍历等价于树的先根遍历。

代码

void preOrderTree(CSTree T)
{
    // 树为空，退出
    if (T == NULL)
        return;
    // 访问根结点
    printf("%d ", T->data);
    CSNode* pCurChild = T->firstChild;
    // 访问T的每一棵子树根结点
    while (pCurChild != NULL)
    {
        // 先根遍历子树
        preOrderTree(pCurChild);
        // 指向T的下一棵子树根
        pCurChild = pCurChild->nextSibling;
    }
}

2.2 后根遍历

算法思想

先依次后根遍历每棵子树，最后访问根结点；

上图中，获得后根遍历的序列：{4,5,6,2,6,3}

孩子兄弟链表表示的二叉树中的根结点不存在右子树，二叉树的左子树包含了树中所有子树的结点。因此，中序遍历二叉树的左子树等价于遍历树中根结点的所有子树。当中序遍历完所有子树后，最后访问根结点，这与树的后跟遍历相同。

代码

void postOrderTree(CSTree T)
{
    // 树为空，退出
    if (T == NULL)
        return;
    CSNode* pCurChild = T->firstChild;
    // 访问T的每一棵子树根结点
    while (pCurChild != NULL)
    {
        // 后根遍历子树
        postOrderTree(pCurChild);
        // 指向T的下一棵子树根
        pCurChild = pCurChild->nextSibling;
    }
    // 访问根结点
    printf("%d ", T->data);
}

3.森林的遍历

森林也可以看成一颗树，每棵树的根结点都可以看作一个虚拟结点，只不过该虚拟结点不出现在转换后的二叉树中。

3.1 森林 < - > 二叉树

3.2 先序遍历森林

• 先访问森林的第一棵树的根结点，
• 然后访问该树的每一棵子树，
• 最后先序遍历森林中待访问的树。

效果等同于依次对各树的先根遍历

3.3 中序遍历森林

• 中序遍历森林中的第一棵树的所有子树；
• 然后再访问第一棵树的根结点；
• 最后中序遍历森林中其余带访问的树。

效果等同于依次对各树的后根遍历