遍历二叉树

---

先序遍历

所谓先序遍历二叉树，指的是从根结点出发，按照以下步骤访问二叉树的每个结点：

• 访问当前结点；

• 进入当前结点的左子树，以同样的步骤遍历左子树中的结点；

• 遍历完当前结点的左子树后，再进入它的右子树，以同样的步骤遍历右子树中的结点；

先序遍历这棵二叉树的过程是：

访问根节点 1；
进入 1 的左子树，执行同样的步骤：
    访问结点 2；
    进入 2 的左子树，执行同样的步骤：
        访问结点 4；
        结点 4 没有左子树；
        结点 4 没有右子树；
    进入 2 的右子树，执行同样的步骤：
        访问结点 5；
        结点 5 没有左子树；
        结点 5 没有右子树；
进入 1 的右子树，执行同样的步骤：
    访问结点 3；
    进入 3 的左子树，执行同样的步骤：
        访问结点 6；
        结点 6 没有左子树；
        结点 6 没有右子树；
    进入 3 的右子树，执行同样的步骤：
        访问结点 7；
        结点 7 没有左子树；
        结点 7 没有右子树； 

1 2 4 5 3 6 7

---

递归先序遍历二叉树

观察整个先序遍历二叉树的过程会发现，访问每个结点的过程都是相同的，可以用递归的方式实现二叉树的先序遍历。

对于顺序表存储的二叉树，递归实现先序遍历二叉树的 C 语言代码为：

void PreOrderTraverse(BiTree T, int p_node) {
    //根节点的值不为 0，证明二叉树存在
    if (T[p_node]) {
        printf("%d ", T[p_node]);
        //先序遍历左子树
        if ((2 * p_node + 1 < NODENUM) && (T[2 * p_node + 1] != 0)) {
            PreOrderTraverse(T, 2 * p_node + 1);
        }
        //最后先序遍历右子树
        if ((2 * p_node + 2 < NODENUM) && (T[2 * p_node + 2] != 0)) {
            PreOrderTraverse(T, 2 * p_node + 2);
        }
    }
}

对于链表存储的二叉树，递归实现先序遍历二叉树的 C 语言代码为

void PreOrderTraverse(BiTree T) {
    //如果二叉树存在，则遍历二叉树
    if (T) {
        printf("%d",T->data); //调用操作结点数据的函数方法
        PreOrderTraverse(T->lchild);//访问该结点的左孩子
        PreOrderTraverse(T->rchild);//访问该结点的右孩子
    }
}

非递归先序遍历二叉树

我们知道，递归的底层实现借助的是栈存储结构。所谓先序遍历二叉树的非递归方式，其实就是自己创建一个栈，模拟递归的过程实现二叉树的先序遍历。

对于顺序表存储的二叉树，非递归实现先序遍历二叉树的 C 语言代码为：

//全局变量，记录栈顶的位置
int top = -1;
//前序遍历使用的入栈函数
void push(BiTree a, int elem) {
    a[++top] = elem;
}
//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//拿到栈顶元素
int getTop(BiTree a) {
    return a[top];
}
//先序遍历顺序表中的完全二叉树
void PreOrderTraverse(BiTree Tree) {
    //模拟栈，记录入栈结点所在顺序表中的下标
    int ad[NODENUM] = { 0 };
    int p;
    //根节点所在的顺序表下标先入栈
    push(ad,0);
    //直到栈中为空
    while (top != -1)
    {
        //取出一个下标
        p = getTop(ad);
        pop(ad);
        //判断当前下标是否超出结点的总数
        while (p < NODENUM)
        {
            //输出 p 下标处存储的结点值
            printf("%d ", Tree[p]);
            //找到该结点的右孩子，该它的数组下标入栈
            if ((2 * p + 2 < NODENUM) && (Tree[2 * p + 2] != 0)) {
                push(ad, 2 * p + 2);
            }
            //找到 p 下标结点的左孩子，并继续遍历
            p = 2 * p + 1;
        }
    }
}

对于链表存储的二叉树，非递归实现先序遍历二叉树的 C 语言代码为：

//全局变量，记录栈顶的位置
int top = -1;
//前序遍历使用的进栈函数
void push(BiTree* a, BiTree elem) {
    a[++top] = elem;
}
//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//拿到栈顶元素
BiTNode* getTop(BiTree* a) {
    return a[top];
}
//先序遍历二叉树
void PreOrderTraverse(BiTree Tree) {
    BiTNode* a[20];//定义一个顺序栈
    BiTNode* p;//临时指针
    push(a, Tree);//根结点进栈
    while (top != -1) {
        p = getTop(a);//取栈顶元素
        pop();//弹栈
        while (p) {
            printf("%d ", p->data);//调用结点的操作函数
            //如果该结点有右孩子，右孩子进栈
            if (p->rchild) {
                push(a, p->rchild);
            }
            p = p->lchild;//一直指向根结点最后一个左孩子
        }
    }
}

---

中序遍历

二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：

• 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；

• 访问当前结点；

• 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。

中序遍历这棵二叉树的过程是：

进入结点 1 的左子树，访问左子树中的结点；
    进入结点 2 的左子树，访问左子树中的结点；
        试图进入结点 4 的左子树，但该结点没有左子树；
        访问结点 4；
        试图进入结点 4 的右子树，但该结点没有右子树；
    访问结点 2；
    进入结点 2 的右子树，访问右子树中的结点；
        试图进入结点 5 的左子树，但该结点没有左子树；
        访问结点 5；
        试图进入结点 5 的右子树，但该结点没有右子树；
访问结点 1；
进入结点 1 的右子树，访问右子树中的结点；
    进入结点 3 的左子树，访问左子树中的结点；
        试图进入结点 6 的左子树，但该结点没有左子树；
        访问结点 6；
        试图进入结点 6 的右子树，但该结点没有右子树；
    访问结点 3；
    进入结点 3 的右子树，访问右子树中的结点；
        试图进入结点 7 的左子树，但该结点没有左子树；
        访问结点 7；
        试图进入结点 7 的右子树，但该结点没有右子树；

最终，中序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 2 5 1 6 3 7

---

递归中序遍历二叉树

对于顺序表存储的二叉树，递归实现中序遍历的 C 语言程序为：

void INOrderTraverse(BiTree T, int p) {
    //递归遍历左子树
    if (((2 * p + 1) < NODENUM) && (T[2 * p + 1] != 0)) {
        INOrderTraverse(T, 2 * p + 1);
    }
    //访问当前结点
    printf("%d ", T[p]);
    //递归遍历右子树
    if (((2 * p + 2) < NODENUM) && (T[2 * p + 2] != 0)){
        INOrderTraverse(T, 2 * p + 2);
    } 
}

对于链表存储的二叉树，递归实现中序遍历的 C 语言程序为：

void INOrderTraverse(BiTree T) {
    if (T) {
        INOrderTraverse(T->lchild);//遍历当前结点的左子树
        printf("%d ",T->data);     //访问当前结点
        INOrderTraverse(T->rchild);//遍历当前结点的右子树
    }
}

非递归中序遍历二叉树

递归的底层实现借助的是栈存储结构，因此我们可以自己模拟出一个栈结构，以非递归的方式实现二叉树的中序遍历。

非递归中序遍历一棵树二叉树，具体有两种实现方案：

• 方案一：从根结点开始，不断地遍历当前结点的左子树并将该结点压入栈中，直至不再有左子树。然后从栈顶取出一个结点并访问它，然后将它的右孩子压入栈中，继续以同样的方式遍历它的右子树；

• 方案二：和方案一唯一的不同之处在于，压入栈中的只会是每个结点的左孩子，右孩子不需要入栈。

对于顺序表存储的二叉树，以上两种方案对应的 C 语言程序分别是：

//全局变量，记录栈顶的位置
int top = -1;
//前序遍历使用的入栈函数
void push(BiTree a, int elem) {
    a[++top] = elem;
}
//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//拿到栈顶元素
int getTop(BiTree a) {
    return a[top];
}
//方案1
void InOrderTraverse1(BiTree Tree) {
    //模拟栈，记录入栈结点所在顺序表中的下标
    int ad[NODENUM] = { 0 };
    int p;
    push(ad, 0);//根节点的数组下标入栈
    //直至栈为空，中序遍历才结束
    while (top != -1) {
        //不断的将各个结点的左孩子入栈
        while ((p = getTop(ad)) < NODENUM) {
            if (Tree[p] == 0) {
                break;  
            }
            push(ad, 2 * p + 1);
        }
        pop();//栈顶的下标肯定超出了 NODENUM 指定范围，直接弹出
        //不再有左子树之后，访问当前结点，并将其右子树入栈
        if (top != -1) {
            p = getTop(ad);
            pop();
            printf("%d ", Tree[p]);
            push(ad, p * 2 + 2);
        }
    }
}
//方案2
void InOrderTraverse2(BiTree Tree) {
    //模拟栈，记录入栈结点所在顺序表中的下标
    int ad[NODENUM] = { 0 };
    int p = 0;
    while (p < NODENUM || top != -1) {
        //将每个结点的左孩子入栈
        if (p < NODENUM && Tree[p] != 0) {
                push(ad, p);
                p = p * 2 + 1;
        }
        else
        {
            //如果栈空，则中序遍历结束
            if (top == -1) {
                break;
            }
            //访问该结点，并将其右孩子的下标赋值给 p，继续遍历右子树
            p = getTop(ad);
            pop();
            printf("%d ", Tree[p]);
            p = p * 2 + 2;
        }
    }
}

对于链表存储的二叉树，以上两种方案对应的 C 语言程序分别是：

//全局变量，表示栈顶
int top = -1;
//前序和中序遍历使用的进栈函数
void push(BiTNode** a, BiTNode* elem) {
    a[++top] = elem;
}
//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//查看栈顶元素
BiTNode* getTop(BiTNode** a) {
    return a[top];
}
//方案1
void InOrderTraverse1(BiTree Tree) {
    BiTNode* a[20];//定义一个顺序栈
    BiTNode* p;//临时指针
    push(a, Tree);//根结点进栈
    while (top != -1) {//top!=-1说明栈内不为空，程序继续运行
        while ((p = getTop(a)) && p) {//取栈顶元素，且不能为NULL
            push(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
        }
        pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
        if (top != -1) {
            p = getTop(a);//取栈顶元素
            pop();//栈顶元素弹栈
            printf("%d ", p->data);
            push(a, p->rchild);//将p指向的结点的右孩子进栈
        }
    }
}
//方案2
void InOrderTraverse2(BiTree Tree) {
    BiTNode* a[20];//定义一个顺序栈
    BiTNode* p;//临时指针
    p = Tree;
    //当p为NULL或者栈为空时，表明树遍历完成
    while (p || top != -1) {
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p) {
            push(a, p);
            p = p->lchild;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
        else {
            p = getTop(a);
            pop();
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
}

---

后序遍历

后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：

• 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；

• 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；

• 直到当前结点的左子树和右子树都遍历完后，才访问该结点。

后序遍历这棵二叉树的过程是：

从根节点 1 出发，进入该结点的左子树；
    进入结点 2 的左子树，遍历左子树中的结点：
        进入结点 4 的左子树，但该结点没有左孩子；
        进入结点 4 的右子树，但该结点没有右子树；
        访问结点 4；
    进入结点 2 的右子树，遍历右子树中的结点：
        进入结点 5 的左子树，但该结点没有左孩子；
        进入结点 5 的右子树，但该结点没有右孩子；
        访问结点 5；
    访问结点 2；
进入结点 1 的右子树，遍历右子树中的结点：
    进入结点 3 的左子树，遍历左子树中的结点：
        进入结点 6 的左子树，但该结点没有左孩子；
        进入结点 6 的右子树，但该结点没有右子树；
        访问结点 6；
    进入结点 3 的右子树，遍历右子树中的结点：
        进入结点 7 的左子树，但该结点没有左孩子；
        进入结点 7 的右子树，但该结点没有右孩子；
        访问结点 7；
    访问结点 3；
访问结点 1。

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 5 2 6 7 3 1

---

递归后序遍历二叉树

后序遍历二叉树，最常用的实现方式就是递归。

对于顺序表存储的二叉树，递归实现后序遍历的 C 语言程序为：

void PostOrderTraverse(BiTree T, int p) {
    if ((p * 2 + 1 < NODENUM) && (T[p * 2 + 1] != 0)) {
        PostOrderTraverse(T, 2 * p + 1);
    }
    if ((p * 2 + 2 < NODENUM) && (T[p * 2 + 2] != 0)) {
        PostOrderTraverse(T, 2 * p + 2);
    }
    printf("%d ", T[p]);
}

对于链表存储的二叉树，递归实现后序遍历的 C 语言程序为：

void PostOrderTraverse(BiTree T) {
    if (T) {
        PostOrderTraverse(T->lchild);//遍历左孩子
        PostOrderTraverse(T->rchild);//遍历右孩子
        printf("%d ", T->data);
    }
}

---

非递归后序遍历二叉树

递归的底层实现过程是借助栈存储结构完成的，因此我们可以手动模拟一个栈结构，实现二叉树的后序遍历。

后序遍历是在遍历完当前结点的左右孩子之后才访问该结点，所以需要在当前结点进栈时为其配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。

这样当遍历完该结点的左右子树并将其弹栈时，查看该结点标志位的值：如果是 0，表示该结点的右孩子还没有遍历；如果是 1，说明该结点的左右孩子都遍历完成，可以访问此结点。

对于顺序表存储的二叉树，非递归实现后序遍历的 C 语言程序为：

#include <stdio.h>
#define NODENUM 7
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];
int top = -1;//表示栈顶
typedef struct SNode {
    int p;   //结点所在顺序表的下标
    int tag; //标记值
}SNode;
//存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}
// 弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//入栈
void push(SNode* a, SNode sdata) {
    a[++top] = sdata;
}
void PostOrderTraverse(BiTree Tree) {
    SNode a[20] = {0};//定义一个顺序栈
    int tag; //记录结点的标记位
    SNode sdata;
    int p = 0;
    while (p < NODENUM || top != -1) {
        //压入结点的左子树
        while (p < NODENUM && Tree[p] != 0) {
            sdata.p = p;
            sdata.tag = 0;
            push(a, sdata);
            p = p * 2 + 1;//继续遍历左孩子
        }
        //取栈顶元素
        sdata = a[top];
        pop();
        p = sdata.p;
        tag = sdata.tag;
        //如果tag==0，说明该结点还没有遍历它的右孩子
        if (tag == 0) {
            sdata.p = p;
            sdata.tag = 1;
            push(a,sdata);
            p = p * 2 + 2;//继续遍历右子树
        }
        //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以访问该结点了
        else
        {
            printf("%d ", Tree[p]);
            p = NODENUM;//重置 p 的值，防止下次进入第一个循环
        }
    }
}
int main() {
    BiTree T = { 0 };
    InitBiTree(T);
    PostOrderTraverse(T);
    return 0;
}

运行结果为：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
4 5 2 6 7 3 1

对于链表存储的二叉树，非递归实现后序遍历的 C 语言程序为：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
int top = -1;//表示栈顶
typedef struct BiTNode {
    TElemType data;//数据域
    struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;
//后序遍历非递归算法
typedef struct SNode {
    BiTree p;
    int tag;
}SNode;
void CreateBiTree(BiTree* T) {
    int num;
    scanf("%d", &num);
    //如果输入的值为 0，表示无此结点
    if (num == 0) {
        *T = NULL;
    }
    else
    {
        //创建新结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = num;
        CreateBiTree(&((*T)->lchild));//创建该结点的左孩子
        CreateBiTree(&((*T)->rchild));//创建该结点的右孩子
    }
}
//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//入栈
void push(SNode* a, SNode sdata) {
    a[++top] = sdata;
}
//后序遍历二叉树
void PostOrderTraverse(BiTree Tree) {
    SNode a[20];//定义一个顺序栈
    BiTNode* p = NULL;//临时指针
    int tag; //记录结点的标记位
    SNode sdata;
    p = Tree;
    while (p || (top != -1)) {
        while (p) {
            //为该结点入栈做准备
            sdata.p = p;
            sdata.tag = 0;//由于遍历是左孩子，设置标志位为0
            push(a, sdata);//压栈
            p = p->lchild;//以该结点为根结点，遍历左孩子
        }
        sdata = a[top];//取栈顶元素
        pop();//栈顶元素弹栈
        p = sdata.p;
        tag = sdata.tag;
        //如果tag==0，说明该结点还没有遍历它的右孩子
        if (tag == 0) {
            sdata.p = p;
            sdata.tag = 1;
            push(a, sdata);//更改该结点的标志位，重新压栈
            p = p->rchild;//以该结点的右孩子为根结点，重复循环
        }
        //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以访问该结点了
        else {
            printf("%d ", p->data);
            p = NULL;
        }
    }
}
//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    PostOrderTraverse(Tree);
    DestroyBiTree(Tree);
    return 0;
}

---

层次遍历

---

线索二叉树

我们知道，树是有层次的，比如：

上面这棵树一共有 3 层，根结点位于第一层，以此类推。

所谓层次遍历二叉树，就是从树的根结点开始，一层一层按照从左往右的次序依次访问树中的结点。

二叉树的存储方式有两种，分别是顺序表和链表。对于顺序表存储的二叉树，层次遍历是很容易实现的，因为二叉树中的结点本就是一层一层存储到顺序表中的。唯一需要注意的是，顺序表存储的只能是完全二叉树，普通二叉树必须先转换成完全二叉树后才能存储到顺序表中，因此在实现层次遍历的时候，需要逐个对顺序表中存储的结点进行甄别。

层次遍历用链表存储的二叉树，可以借助队列存储结构实现，具体方案是：

• 将根结点入队；

• 从队列的头部提取一个结点并访问它，将该结点的左孩子和右孩子依次入队；

• 重复执行第 2 步，直至队列为空；

假设将图 1 中的二叉树存储到链表中，那么层次遍历的过程是：

根结点 1 入队（1）；
根结点 1 出队并访问它，然后将 1 的左孩子 2 和右孩子 3 依次入队（3, 2）；
将结点 2 出队并访问它，然后将 2 的左孩子 4 和右孩子 5 依次入队（5,4,3）；
将结点 3 出队并访问它，然后将 3 的左孩子 6 和右孩子 7 依次入队（7,6,5,4）；
根结点 4 出队并访问它，然后将 4 的左孩子（无）和右孩子（无）依次入队（7,6,5）；
将结点 5 出队并访问它，然后将 5 的左孩子（无）和右孩子（无）依次入队（7,6）；
将结点 6 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（7）；  
将结点 7 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（）；
队列为空，层次遍历结束。

---

层次遍历顺序二叉树

#include <stdio.h>
#define NODENUM 7 //二叉树中结点的个数
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];
//顺序表存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}
//层次遍历二叉树
void LevelOrderTraverse(BiTree T) {
    int j;
    //从根结点起,层次遍历二叉树
    for (j = 0; j < NODENUM; j++) {
        //只访问非空结点
        if (T[j] != 0) {
            printf("%d ", T[j]);
        }
    }
}
int main() {
    int res;
    BiTree T = { 0 };
    InitBiTree(T);
    LevelOrderTraverse(T);
    return 0;
}

运行结果为：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
1 2 3 4 5 6 7

---

层次遍历链式二叉树

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
#define NODENUM 7
//初始化队头和队尾指针开始时都为0
int front = 0, rear = 0;
typedef struct BiTNode {
    TElemType data;//数据域
    struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;
//以先序遍历的方式存储二叉树到链表中
void CreateBiTree(BiTree* T) {
    int num;
    scanf("%d", &num);
    //如果输入的值为 0，表示无此结点
    if (num == 0) {
        *T = NULL;
    }
    else
    {
        //创建新结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = num;
        CreateBiTree(&((*T)->lchild));//创建该结点的左孩子
        CreateBiTree(&((*T)->rchild));//创建该结点的右孩子
    }
}
//入队函数
void EnQueue(BiTree* a, BiTree node) {
    if (rear == NODENUM) {
        printf("队列已满，入队失败\n");
        exit(0);
    }
    a[rear++] = node;
}
//出队函数
BiTNode* DeQueue(BiTNode** a) {
    if (front == rear) {
        printf("队列为空，出队失败\n");
        exit(0);
    }
    return a[front++];
}
//层次遍历二叉树
void LevelOrderTraverse(BiTree T) {
    //如果二叉树存在，才进行层次遍历
    if (T) {
        BiTree a[20] = { 0 };
        BiTree p = NULL;
        p = T;
        //根结点入队
        EnQueue(a, p);
        //重复执行，直至队列为空
        while (front < rear)
        {
            //从队列取出一个结点
            p = DeQueue(a);
            //访问当前结点
            printf("%d ", p->data);
            //将当前结点的左右孩子依次入队
            if (p->lchild) {
                EnQueue(a, p->lchild);
            }
            if (p->rchild) {
                EnQueue(a, p->rchild);
            }
        }
    } 
}
//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    LevelOrderTraverse(Tree);
    DestroyBiTree(Tree);
    return 0;
}

运行结果：

1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
1 2 3 4 5 6 7

---