数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

#include <iostream>
 #include<cstring>
 #include<queue>
 using namespace std;
 struct biTnode
 {
     string data;
     biTnode *lChild,*rChild;
 };
  biTnode* T=NULL;
 void CreatebiTree(biTnode* &T)
 {
     string a,b,c;
     biTnode *node,*p;
     queue<biTnode*>q;
     cin>>a>>b>>c;
     if(a=="NULL" && b!="NULL")//创建根结点
     {
         node=new biTnode;
         node->data=b;
         node->lChild=node->rChild=NULL;
         T=node;
         q.push(T);
     }
     cin>>a>>b>>c;
     while(!q.empty()&&a!="NULL"&&b!="NULL")
     {
         p=q.front();
         q.pop();
         while(a==p->data)
         {
             node=new biTnode;
             node->data=b;
             node->lChild=node->rChild=NULL;
             if(c=="L")
             {
                 p->lChild=node;
                 cout<<p->data<<"'s lChild is "<<node->data<<endl;
             }
             else
             {
                 p->rChild=node;
                 cout<<p->data<<"'s rChild is "<<node->data<<endl;
             }
             q.push(node);
             cin>>a>>b>>c;
         }
     }
 }




 void preorder(biTnode* &T)
 {
     if(T)
     {
        cout<<T->data<<"  ";
        preorder(T->lChild);
        preorder(T->rChild);
     }
 }


 void inorder(biTnode* &T)
 {
     if(T)
     {
        inorder(T->lChild);
        cout<<T->data<<"  ";
        inorder(T->rChild);
     }
 }


 void posorder(biTnode* &T)
 {
     if(T)
     {
        posorder(T->lChild);
        posorder(T->rChild);
        cout<<T->data<<"  ";
     }
 }
 int main()
 {
     cout << "输入结点数据a,b,c(a为父亲，b为结点字符，c为‘L’左孩子或‘R’右孩子)" << endl;
     CreatebiTree(T);
     cout << "创建树成功!" << endl;
     cout << "先序遍历：" << endl;
     preorder(T);
     cout<<endl<< "中序遍历：" << endl;
     inorder(T);
     cout<<endl<< "后序遍历：" << endl;
     posorder(T);
     return 0;
 }