二叉树的简单实现即递归遍历

#include<iostream>
#include<stdio.h>
#include<malloc.h>
using namespace std;
#define ElemType char
#define MaxSize 100

typedef struct node
{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;

void CreateBTree1(BTNode *&b,char *str)//由数组直接建立二叉树
{
    BTNode *St[MaxSize];//St作为顺序栈
    BTNode *p;
    int top = -1;//top为栈顶指针
    int j = 0;
    int k ;
    char ch;
    ch = str[j];
    b = NULL;//初始二叉链为空
    while(ch != '')//循环str
    {
        switch(ch)
        {
            case '(': 
                top++;  
                St[top] = p;
                k = 1;
                break;//开始处理左孩子结点，
            case ')':
                top--;
                break;//栈顶结点的子树处理完毕
            case ',':
                k = 2;  
                break;//开始处理右孩子结点
            default://创立一个结点，p指向它
                p = (BTNode*)malloc(sizeof(BTNode));
                p->data = ch;//存放结点值
                p->lchild = p->rchild = NULL;//左右孩子为空 
                if(b == NULL)//若尚未建立头结点
                {
                    b = p;//p所指即为根结点
                }
                else
                {
                    switch(k)
                    {
                        case 1:
                            St[top]->lchild = p;
                            break;//新建结点为根结点左孩子
                        case 2:
                            St[top]->rchild = p;
                            break;//新建结点为根结点右孩子
                    }
                
                }
        }
        j++;
        ch = str[j];
    }
}

void CreateBTree2(BTNode *&b)//手动输入二叉树
{
    b = NULL;
    char ch;
    ch = getchar();
    if(ch == '#')
    {
        b = NULL;
    }
    else
    {
        b = (BTNode *)malloc(sizeof(BTNode));
        b->data = ch;
        CreateBTree2(b->lchild);
        CreateBTree2(b->rchild);
    }
}

void  DispLeaf(BTNode *b)//Print All Leaf
{
    if(b != NULL)
    {
        if(b->lchild == NULL && b->rchild == NULL)
        {
            cout<<b->data;
        }
        DispLeaf(b->lchild);//lchild leaf
        DispLeaf(b->rchild);//rhcild leaf 
        
    }
}

BTNode* FindNode(BTNode *b,ElemType x)//return a Node
{
    BTNode *p;
    if(b == NULL)
    {
        return NULL;
    }
    else if(b->data == x)
    {
        return b;
    }
    else
    {
        p = FindNode(b->lchild,x);
        if(p != NULL)
        {
            return p;
        }
        else
        {
            return FindNode(b->rchild,x);
        }
    }
}

BTNode* LchildNode(BTNode *p)//return p lchild
{
    return p->lchild;
}

BTNode* RchildNode(BTNode *p)//return p rchild
{
    return p->rchild;
}

int BTHeight(BTNode *b)//return BTheigh
{
    int lchildh,rchildh;
    if(b == NULL)
    {
        return (0);
    }
    else
    {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh >rchildh) ? (lchildh + 1): (rchildh + 1);
    }
}

int Level(BTNode *b,ElemType x,int h)//return Level
{
   
    int level;
    if(b == NULL)
    {
        return (0);
    }
    else if(b->data == x)
    {
        return h;
    }
    else
    {
        level = Level(b->lchild,x,h+1);
        if(level != 0)
        {
            return level;
        }
        else
        {
            return (Level(b->rchild,x,h+1));
        }
    }
}

void DispBTree(BTNode *b)
{
    if(b != NULL)
    {
        cout<<" "<<b->data;
        if(b->lchild != NULL || b->rchild !=  NULL)
        {
            cout<<"(";//有孩子结点才输出（
            DispBTree(b->lchild);//扫描左子树
            if(b->rchild != NULL)//有右子树才输出，
            {
                cout<<",";
            }
            DispBTree(b->rchild);//递归处理右子树
            cout<<")";//有孩子结点才输出
        }
    }
}

void PreOrder(BTNode *b)
{
    if(b != NULL)
    {
        cout<<" "<<b->data;
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }
}

void InOrder(BTNode *b)
{
    if(b != NULL)
    {
        InOrder(b->lchild);
        cout<<" "<<b->data;
        InOrder(b->rchild);
    }
}

void PostOrder(BTNode *b)
{
    if(b != NULL)
    {
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        cout<<" "<<b->data;
    }
}

void DestoryBTree(BTNode *&b)
{
    if(b != NULL)
    {
        DestoryBTree(b->lchild);
        DestoryBTree(b->rchild);
        free(b);
    }
}

int main()
{
    //～～～～～～～～～～～～～～Create1
    BTNode *b,*p,*lp,*rp;
    cout<<"BTree"<<endl;
    cout<<"create BTree"<<endl;
    char str[] ="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    CreateBTree1(b,str);
    cout<<"PrintL: ";
    DispBTree(b);
    cout<<endl;
    cout<<"H Node"<<endl;
    p = FindNode(b,'H');
    if(p!=NULL)
    {
        lp = LchildNode(p);
        if(lp!=NULL)
        {
            cout<<" lchild is "<<lp->data;
        }
        else
        {
            cout<<"No lchild !"<<endl;
        }
        rp = RchildNode(p);
        if(rp!=NULL)
        {
            cout<<" rchild is "<<rp->data;
        }
        else
        {
            cout<<"NO rchild !"<<endl;
        }
    }
    cout<<endl;
    cout<<"BTree Height is "<< BTHeight(b)<<endl;
    //~~~~Order!~~~
    cout<<"PreOrder ->  ";
    PreOrder(b);
    cout<<endl;
    cout<<"InOrder ->  ";
    InOrder(b);
    cout<<endl;
    cout<<"PostOrder ->  ";
    PostOrder(b);
    cout<<endl;
    cout<<"Leaf Node-> ";
    DispLeaf(b);
    cout<<endl;

    cout<<"H level is:"<<Level(b,'H',1)<<endl;
    cout<<"Free"<<endl;
    DestoryBTree(b);

//～～～～～～～～～～～～～Create2
    BTNode *b2;
    cout<<"Create 2"<<endl;
    CreateBTree2(b2); 
    cout<<"PreOrder ->  ";
    PreOrder(b2);
    cout<<endl;
    
    cout<<"InOrder ->  ";
    InOrder(b2);
    cout<<endl;
    cout<<"PostOrder ->  ";
    PostOrder(b2);
    cout<<endl;
    cout<<"Leaf Node-> "<<endl;
    DispLeaf(b2);
    cout<<endl;
    cout<<"Free"<<endl;
    DestoryBTree(b2);
    return 1;
}   

　　

这是运行后的结果，注意Create1 和Create2 创建二叉树的区别。。