数据结构：二叉树的遍历和存储结构

数据结构：二叉树的遍历和存储结构

二叉树是一种常见的数据结构，它在计算机科学和软件工程领域有着广泛的应用。本文将详细介绍二叉树的遍历方法（前序、中序、后序和层序遍历）以及如何在内存中建立二叉树。通过本文的学习，读者将能够掌握二叉树的基本概念和实现方法。

二叉树可以这样递归地定义：

1. 就像链表有头指针一样，每个二叉树都有一个根指针（上图中的root指针）指向它。根指针可以是NULL，表示空二叉树，或者
2. 根指针可以指向一个节点，这个节点除了有数据成员之外还有两个指针域，这两个指针域又分别是另外两个二叉树（左子树和右子树）的根指针。

链表的遍历方法是显而易见的：从前到后遍历即可。二叉树是一种树状结构，如何做到把所有节点都走一遍不重不漏呢？有以下几种方法，如下图（来自《linux c 编程一站式学习》）所示：

前序（Pre-order Traversal）（深度优先搜索）、中序（In-order Traversal）、后序遍历（Post-order Traversal）、层序遍历（Level-order Traversal）（广度优先搜索）。如何分辨三种次序的遍历方法呢？《data structrue and algorithm analysis in c》中有一句:We can evaluate an expression tree, T, by applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.

个人总结就是：前序 （root->left->right) ; 中序(left->root->right); 后序（left->right->root)

举例上图来说，前序遍历，首先root是4，接着要Left，就是指左边子树，在左边子树中又先是root即2，然后是left的1，接着说right的3，现在左边子树递归完毕了，接着右边子树，同样先root即5，没有left，最后是right的6，所以最后排列是421356。

注意：已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
但已知前序和后序遍历序列，是不能确定一棵二叉树的。

如果我们要在内存中建立一个如图6-9-1左图这样的树，为了能让每个结点确认是否有左右孩子，可以对它进行扩展，如右图那样，也就是将二叉树的每个结点的空指针引出一个虚结点，其值为一特定值，比如'#'。我们称这种处理后的二叉树为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。比如图6-9-1的前序遍历序列就为AB#D##C##。

示例程序如下：（改变自《大话数据结构》）

#include<iostream>
using namespace std;
#define MAXSIZE 50
typedef char ElemType;
typedef char String[MAXSIZE + 1]; //以'\0’结尾
String str; /* 用于构造二叉树*/
ElemType NoChar = ' '; /* 字符型以空格符为空 */
/* 结点结构 */
typedef struct BTNode
{
    ElemType data;/* 结点数据 */
    struct BTNode *LChild;/* 左右孩子指针 */
    struct BTNode *RChild;
} BTNode, *BTNodePtr;
/* 构造一个字符串 */
bool StrAssign(String Dest, char *ptr)
{
    cout << "Assign Str ..." << endl;
    int i;
    for (i = 0; ptr[i] != '\0' && i < MAXSIZE; i++)
        Dest[i] = ptr[i];
    Dest[i] = '\0';
    return true;
}
/* 构造空二叉树 */
bool InitBTree(BTNodePtr *Tpp)
{
    *Tpp = NULL;
    return true;
}
/* 销毁二叉树 */
void DestroyBTree(BTNodePtr *Tpp)
{
    if (*Tpp)
    {
        if ((*Tpp)->LChild)/* 有左孩子 */
            DestroyBTree(&(*Tpp)->LChild);/* 销毁左孩子子树 */
        if ((*Tpp)->RChild)/* 有右孩子 */
            DestroyBTree(&(*Tpp)->RChild); /* 销毁右孩子子树 */
        free(*Tpp);/* 释放根结点 */
        *Tpp = NULL;/* 空指针赋0 */
    }
}
/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树。 */
void CreateBTree(BTNodePtr *Tpp)
{
    ElemType ch;
    static int i = 0;
    if (str[i] != '\0')
        ch = str[i++];
    if (ch == '#')
        *Tpp = NULL;
    else
    {
        *Tpp = (BTNodePtr)malloc(sizeof(BTNode));
        if (!*Tpp)
            exit(1);
        (*Tpp)->data = ch;/* 生成根结点 */
        CreateBTree(&(*Tpp)->LChild);/* 构造左子树 */
        CreateBTree(&(*Tpp)->RChild);/* 构造右子树 */
    }
}
bool BTreeEmpty(BTNodePtr Tp)
{
    if (Tp)
        return false;
    else
        return true;
}
/*返回二叉树的深度 */
int BTreeDepth(BTNodePtr Tp)
{
    int i, j;
    if (!Tp)
        return 0;
    if (Tp->LChild)
        i = BTreeDepth(Tp->LChild);
    else
        i = 0;
    if (Tp->RChild)
        j = BTreeDepth(Tp->RChild);
    else
        j = 0;
    return i > j ? i + 1 : j + 1;
}
/* 返回根节点的数值 */
ElemType Root(BTNodePtr Tp)
{
    if (BTreeEmpty(Tp))
        return NoChar;
    else
        return Tp->data;
}
/* 前序递归遍历*/
void PreOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    cout << Tp->data << ' ';
    PreOrderTraverse(Tp->LChild);
    PreOrderTraverse(Tp->RChild);
}
/* 中序递归遍历*/
void InOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    InOrderTraverse(Tp->LChild);
    cout << Tp->data << ' ';
    InOrderTraverse(Tp->RChild);
}
/* 后序递归遍历*/
void PostOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    PostOrderTraverse(Tp->LChild);
    PostOrderTraverse(Tp->RChild);
    cout << Tp->data << ' ';
}
int main(void)
{
    BTNodePtr Tp;
    InitBTree(&Tp);
    StrAssign(str, "ABDH#K###E##CFI###G#J##");
    cout << "输入字符序列（前序遍历）为：" << endl;
    cout << str << endl;
    CreateBTree(&Tp);
    cout << "前序遍历二叉树：" << endl;
    PreOrderTraverse(Tp);
    cout << endl;
    cout << "中序遍历二叉树：" << endl;
    InOrderTraverse(Tp);
    cout << endl;
    cout << "后序遍历二叉树：" << endl;
    PostOrderTraverse(Tp);
    cout << endl;
    cout << "二叉树的根节点为：" << Root(Tp) << endl;
    cout << "二叉树的深度为：" << BTreeDepth(Tp) << endl;
    cout << "销毁二叉树 ..." << endl;
    DestroyBTree(&Tp);
    if (BTreeEmpty(Tp))
        cout << "二叉树现已为空..." << endl << endl;
    return 0;
}

输出为：

输入字符序列（前序遍历）为：
ABDH#K###E##CFI###G#J##
前序遍历二叉树：
ABDHKECFIJG
中序遍历二叉树：
HDBKEACIFJG
后序遍历二叉树：
HDKBEJFIGCA
二叉树的根节点为：A
二叉树的深度为：4
销毁二叉树 ...
二叉树现已为空...