二叉树的创建、遍历及应用

如图所示的二叉树：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXNODE 10

struct node
{
    char data;
    struct node *lchild;
    struct node *rchild;
};


struct node *CreatBTree()  //采用递归法，创建二叉树
{
    struct node *topNode;  //定义1个指向结构体的指针

    char ch;
    ch=getchar();  //getchar函数是从输入缓冲区里读出最开头的那个字符的，然后把最先的那个字符删掉

    if(ch=='0')
        topNode=NULL;
    else
    {
        topNode=(struct node *)malloc(sizeof(struct node));
        topNode->data=ch;
        topNode->lchild=CreatBTree();//创建左子树
        topNode->rchild=CreatBTree();//创建右子树
    }
    return(topNode);
}

void printListBTree(struct node *topNode)  //广义表示法输出二叉树
{
    if(topNode!=NULL)
    {
        printf("%c",topNode->data);
        if((topNode->lchild!=NULL)||(topNode->rchild!=NULL))
        {
            printf("（");
            printListBTree(topNode->lchild);
            if(topNode->rchild!=NULL)
                printf("，");
            printListBTree(topNode->rchild);
            printf("）");
        }
    }
}

void preorder(struct node *topNode)  //前序遍历
{
    if(topNode!=NULL)
    {
        printf("%3c",topNode->data);
        preorder(topNode->lchild);
        preorder(topNode->rchild);
    }
}

void Inorder(struct node *topNode)  //中序遍历
{
    if(topNode!=NULL)
    {
        Inorder(topNode->lchild);
        printf("%3c",topNode->data);
        Inorder(topNode->rchild);
    }
}

void postorder(struct node *topNode)  //后序遍历
{
    if(topNode!=NULL)
    {
        postorder(topNode->lchild);
        postorder(topNode->rchild);
        printf("%3c",topNode->data);
    }
}

//层次遍历时，设置一个队列，遍历从根节点开始
//首先将根节点指针入队列，然后从队列取出一个元素，每取出一个元素进行如下操作：
//(1)访问该元素所指节点 
//(2)若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。不断进行该过程，当队列为空时，遍历结束！

void levelorder(struct node *topNode)  //层次遍历
{
    struct node *queue[MAXNODE];
    int front,rear;
    if(topNode==NULL)
        return;
    front=-1;
    rear=0;
    queue[rear]=topNode;
    while(front!=rear)
    {
        front++;
        printf("%3c",queue[front]->data);  //访问队首节点
        if(queue[front]->lchild!=NULL)     //将队首节点的左孩子节点入队
        {
            rear++;
            queue[rear]=queue[front]->lchild;
        }
        if(queue[front]->rchild!=NULL)    //将队首节点的右孩子节点入队
        {
            rear++;
            queue[rear]=queue[front]->rchild;
        }
    }
}

//在知道根节点的二叉树中查找数据元素x；查找成功返回该节点的指针，查找失败返回空指针

struct node *Search(struct node *topNode,char x) //在二叉树中查找给定数据
{
    struct node *p;
    if(topNode==NULL)
        return NULL;
    else
    {
        if(topNode->data==x)
            return topNode;
        else
        {
            if(p=Search(topNode->lchild,x))
                return p;
            if(p=Search(topNode->rchild,x))
                return p;
        }        
    }
    return NULL;
}

int TreeDepth(struct node *topNode) //计算二叉树的深度
{
    int depleft,depright;
    
    if(topNode==NULL)
    {
        return 0;
    }
    else
    {
        depleft=TreeDepth(topNode->lchild);
        depright=TreeDepth(topNode->rchild);
        if(depleft>depright)
        {
            return depleft+1;
        }
        else
        {
            return depright+1;
        }
    }
}

int countNode(struct node *topNode) //计算二叉树节点个数
{
    int count;
    int lnode_num,rnode_num;

    if(topNode==NULL)
        count=0;
    else
    {
        
        lnode_num=countNode(topNode->lchild);
        rnode_num=countNode(topNode->rchild);
        count=lnode_num+rnode_num+1;
    }
    return count;
}

void main()
{
    char xx;
    struct node *topNode=NULL;
    struct node *BNode;
    int tree_depth; //变量定义为二叉树的深度
    int sum_node;   //变量定义为二叉树节点个数

    printf("输入先序序列，虚结点用0表示：
");
    topNode=CreatBTree();

    printf("用广义法表示的二叉树的输出如下：
");
    printListBTree(topNode);

    printf("
二叉树的前序遍历的结果为：
");
    preorder(topNode);

    printf("
二叉树的中序遍历的结果为：
");
    Inorder(topNode);

    printf("
二叉树的后序遍历的结果为：
");
    postorder(topNode);

    printf("
二叉树的层次遍历的结果为：
");
    levelorder(topNode);

    printf("
该二叉树的深度为：");
    tree_depth=TreeDepth(topNode);
    printf("%d
",tree_depth);

    printf("
该二叉树节点个数为：");
    sum_node=countNode(topNode);
    printf("%d
",sum_node);

    printf("
");
    printf("输入一个待查找的数据：");
    fflush(stdin); //清空输入缓冲区
    scanf("%c",&xx);
    BNode=Search(topNode,xx);
    if(BNode)
        printf("查找成功：%c
",*BNode);
    else
        printf("查找失败！
");

    printf("
");
    system("pause");
}

结果显示：