树——C语言

树是n个结点的有限集。树的节点包括一个数据元素及若干指向其子树的分支-如图

而一般我们使用二叉树。二叉树是另一种树型结构，它的特点是每个节点至多只有两棵子树（也就是说，二叉树不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。如图

二叉树根据使用的需要，其储存结构也不相同。但大体来说，二叉数的储存结构由一个数据元素和分别指向其左右的两个分支构成。在特定需要的情况下，还会在此基础上加上可以回溯的双亲节点。

二叉树的遍历分为：先序遍历，中序遍历，后序遍历。三者都可以采用递归的方式进行实现。

先序遍历先访问节点，再访问左分支，最后到右分支；中序遍历先访问左分支，再访问节点，最后到右分支；后序遍历先访问左分支，再访问右分支，最后到节点。

代码实现：

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define Max 50

typedef struct node
{
    char data;
    struct node *lchild;//左孩子
    struct node *rchild;//右孩子
}BitNode,*Bitree;
/**创建二叉树**/
void creatT(Bitree &T)//使用先序遍历序列来创建二叉树
{
    char a;
    scanf("%c",&a);
    if (a=='0')//0表示这条分支结束
    {
        T=NULL;
    }
    else
    {
        if(!(T=(Bitree)malloc(sizeof(BitNode))))
            exit(0);

        T->data=a;//节点数据
        creatT(T->lchild);//左分支
        creatT(T->rchild);//右分支
    }
}
/**先序遍历**/
void preOrder(Bitree T)
{
    if(T==NULL)
        return ;//先序遍历使用递归的方式
    printf("%c",T->data);//先访问节点，再访问左分支，最后到右分支
    preOrder(T->lchild);
    preOrder(T->rchild);
}
/**中序遍历**/
void InOrder(Bitree T)
{
    if(T==NULL)
        return ;
    InOrder(T->lchild);//先访问左分支，再访问节点，最后到右分支
    printf("%c",T->data);
    InOrder(T->rchild);
}
/**后序遍历**/
void postOrder(Bitree T)
{
    if(T==NULL)
        return ;
    postOrder(T->lchild);//先访问左分支，再访问右分支，最后到节点
    postOrder(T->rchild);
    printf("%c",T->data);
}
/**查找**/
void find(Bitree T,char b,Bitree &q)
{
    if(T!=NULL)
    {
        if(T->data==b)
        {
            q=T;
        }
        else
        {
            find(T->lchild,b,q);//查找也同样是使用递归的方式，先查找左子树，再查找右子树
            find(T->rchild,b,q);
        }
    }

}
int main (void)
{
    Bitree T,q;
    char b;
    creatT(T);
    getchar();

    printf("先序遍历 :");
    preOrder(T);
    printf("\n");

    printf("中序遍历 :");
    InOrder(T);
    printf("\n");

    printf("中序遍历 :");
    postOrder(T);
    printf("\n");

    printf("请输入想要查找的字符：\n");
    scanf("%c",&b);
    find(T,b,q);
    if(q!=NULL)
    {
        printf("\nYES!\n");
    }

    else if(q==NULL)
    {
        printf("\nNO!\n");
    }
    return 0;
}
运行结果显示：