阅读:0       作者:严长生

二叉树遍历算法(源码+解析)

建立一棵二叉树,并分别按先序、中序和后序遍历这棵二叉树,要求以二叉链表作为存储结构。

技术要点

创建二叉树的二叉链表,其基本思想为:首先对一般的二叉树添加若干个虚结点,使其每一个结点均有左右孩子,然后按先序遍历的顺序依次输入结点信息。

若输入的结点不是虚结点,则建立一个新结点,然后依次建立该结点的左孩子和右孩子;否则,新结点为空。

例如,建立如上图(a)所示的二叉树,其扩充二叉树如上图(b)所示,输入序列应为:A B D @ @ @ C E @ G @ @ F @ @ ,其中 @ 为虚结点。

构建好二叉树之后,在按照先序、中序和后序的遍历方式遍历二叉链表。

有关三种遍历方式的详细介绍,请阅读《二叉树的三种遍历方式》一文,本节不再过多讲述。

实现代码(附有详细注释)

#include <stdio.h>
#include <stdlib.h>
//结点结构体
typedef struct BiTNode{
    char data;//数据
    struct BiTNode * lchild,*rchild;//左右孩子指针
}BiTNode ,*BiTree;
//初始化二叉树的二叉链表T
void Create_BiTree(BiTree * T){
    char ch;
    ch = getchar();
    //@ 表示此处无结点,为虚结点
    if(ch == '@'){
        *T = NULL;
    }
    //# 表示构造结束
    else if(ch == '#'){
        return ;
    }
    //排除以上两种情况,则为有数据的结点,对其进行构造
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        //继续构造其左右孩子结点
        Create_BiTree(&(*T)->lchild);
        Create_BiTree(&(*T)->rchild);
    }
}
//先序遍历二叉树
void PreOrder(BiTree T){
    if(T){
        //遇到结点先输出其结点信息,然后按照先左后右的方式进行遍历
        printf("%3c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
//中序遍历二叉树
void InOrder(BiTree T){
    if(T){
        //中序遍历,即先遍历左孩子,然后输出结点数据,在遍历右孩子
        InOrder(T->lchild);
        printf("%3c",T->data);
        InOrder(T->rchild);
    }
}
//后序遍历二叉树
void PostOrder(BiTree T){
    if(T){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%3c",T->data);
    }
}
int main(){
    BiTree T;
    printf("input PreOrder str:");
    //构造二叉树
    Create_BiTree(&T);
    printf("\n");
    //分别按照先序、中序、后序的方式遍历二叉树
    printf("preorder list of  T :");
    PreOrder(T);
    printf("\nInOrder list of T :");
    InOrder(T);
    printf("\nPostOrder list of T:");
    PostOrder(T);
}
运行结果为:
input PreOrder str:ABD@@@CE@G@@F@@#

preorder list of  T :  A  B  D  C  E  G  F
InOrder list of T :  D  B  A  E  G  C  F
PostOrder list of T:  D  B  G  E  F  C  A