二叉树构造

佚名 6年前 (2019-04-11) 随笔 1697人围观抢沙发百度已收录

#include<iostream>
#include<stack>
using namespace std;
struct BiTNode
{
    char date;
    BiTNode *lchild,*rchild;
    
    BiTNode(char ch,BiTNode *left,BiTNode *right)
    {
        date=ch;
        lchild=left;
        rchild=right;
    }
    BiTNode(){}
};

//先序遍历
void PreOrder(BiTNode *T)//递归调用 
{
    if(T) 
    {
        cout<<T->date;
    PreOrder(T->lchild);
    PreOrder(T->rchild);
    }
 } 
//中序遍历
void InOrder(BiTNode *T)
{
    if(T)
    {
        InOrder(T->lchild);
        cout<<T->date;
        InOrder(T->rchild);
    }
 } 
 
 //后序遍历
void PostOrder(BiTNode *T)
{
    if(T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->date;
    }
 } 
//非递归实现中序遍历
void InOrder1(BiTNode *T)
{
    BiTNode *p=T;
    stack <BiTNode*> S;
    while(p!=NULL||!S.empty())
    {
        if(p!=NULL)
        {
            S.push(p);
            p=p->lchild;
        }
        else
        {
            p=S.top();
            S.pop();
            cout<<p->date;
            p=p->rchild;
        }
    }
 } 

int main()
{
    BiTNode *root1= new BiTNode('A',NULL,NULL);
    cout<<root1->date<<endl;
    
    BiTNode *root2=new BiTNode();
    root2->lchild=NULL;
    root2->rchild=NULL; 
    cout<<root2->date<<endl;
}