二叉树数据结构及建立

二叉树数据结构：

typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

假设要建立一颗如下的二叉树，输入为：124##5##36##7##

我们采用两种方法递归和非递归

1、二叉树的先序递归建立过程（递归就是调用栈进行的操作）

直接上代码：

void CreateBiTree(BiTree &root) 
{  
    char ch; //要插入的数据  
    cin>>ch;  
    if(ch=='#')  
        root = NULL;  
    else  
    {  
        root = (BiTree)malloc(sizeof(BiTNode)); 
        if(root==NULL)
            return ; 
        root->data = ch;  
        printf("请输入%c的左孩子：",ch);  
        CreateBiTree1(root->lchild);  
        printf("请输入%c的右孩子：",ch);  
        CreateBiTree1(root->rchild);  
    }  
} 

建立过程截图（体现了栈。。）：

2、二叉树的非递归建立

while(top != 0)
{
    while(ch != '#')
    {
        scanf("%c",&ch);
        if(ch != '#')
        {
            p = (link)malloc(sizeof(node));
            p->data = ch;
            s[top-1]->lch = p;
            s[top++] = p;       
        }
        else
            s[top-1]->lch = NULL;
    } 
    q = s[--top];
    scanf("%c",&ch);
    if(ch != '#')
    {
        p = (link)malloc(sizeof(node));
        p->data = ch;
        q->rch = p;
        s[top++] = p;
    }
    else
        q->rch = NULL;
}

也可采用STL中的栈stack实现。。