二叉树 数据结构

怎么建立二叉树，然后先序遍历？

#include #include #include #include #include #define SIZE 100using namespace std;typedef struct  BiTNode      //定义二叉树节点结构{ char  data;                     //数据域 struct BiTNode *lchild,*rchild; //左右孩子指针域}BiTNode,*BiTree;int visit(BiTree t);void CreateBiTree(BiTree &T);    //生成一个二叉树void PreOrder(BiT...全部

  #include #include #include #include #include #define SIZE 100using namespace std;typedef struct  BiTNode      //定义二叉树节点结构{ char  data;                     //数据域 struct BiTNode *lchild,*rchild; //左右孩子指针域}BiTNode,*BiTree;int visit(BiTree t);void CreateBiTree(BiTree &T);    //生成一个二叉树void PreOrder(BiTree);          //递归先序遍历二叉树void InOrder(BiTree);           //递归中序遍历二叉树void PostOrder(BiTree);         //递归后序遍历二叉树void InOrderTraverse(BiTree T); //非递归中序遍历二叉树void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树void LeverTraverse(BiTree T);//非递归层序遍历二叉树//主函数void main(){ BiTree T;        char j; int flag=1; //---------------------程序解说----------------------- printf("本程序实现二叉树的操作。
   "); printf("叶子结点以空格表示。 "); printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。 "); //---------------------------------------------------- printf(" "); printf("请建立二叉树。
   "); printf("建树将以三个空格后回车结束。 "); printf("例如:1 2 3 4 5 6   (回车) "); CreateBiTree(T);       //初始化队列 getchar(); while(flag)    {  printf(" ");  printf("请选择: ");  printf("1。
  递归先序遍历 ");  printf("2。递归中序遍历 ");  printf("3。递归后序遍历 ");  printf("4。非递归中序遍历 ");  printf("5。非递归先序遍历 ");  printf("6。
  非递归层序遍历 ");  printf("0。退出程序 ");  scanf(" %c",&j);  switch(j)  {   case '1':if(T)            {    printf("递归先序遍历二叉树:");    PreOrder(T);    printf(" ");             }   else printf("二叉树为空! ");   break;   case '2':if(T)            {    printf("递归中序遍历二叉树:");    InOrder(T);    printf(" ");            }   else printf("二叉树为空! ");   break;   case '3':if(T)            {    printf("递归后序遍历二叉树:");    PostOrder(T);    printf(" ");            }   else printf("二叉树为空! ");   break;   case '4':if(T)            {    printf("非递归中序遍历二叉树:");    InOrderTraverse(T);    printf(" ");            }   else printf("二叉树为空! ");   break;   case '5':if(T)            {    printf("非递归先序遍历二叉树:");    PreOrder_Nonrecursive(T);    printf(" ");            }   else printf("二叉树为空! ");   break;    case '6':if(T)            {    printf("非递归层序遍历二叉树:");    LeverTraverse(T);    printf(" ");            }   else printf("二叉树为空! ");   break;    default:flag=0;printf("程序运行结束，按任意键退出! ");  }    }}//建立二叉树void CreateBiTree(BiTree &T){ char ch; scanf("%c",&ch);    //读入一个字符    if(ch==' ') T=NULL; else  {  T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点  T->data=ch;  CreateBiTree(T->lchild);  //生成左子树  CreateBiTree(T->rchild);  //生成右子树     }}//先序遍历的递归void PreOrder(BiTree T){ if(T) {  printf("%c ",T->data);  //访问结点  PreOrder(T->lchild);   //遍历左子树  PreOrder(T->rchild);   //遍历右子树 }}//中序遍历的递归void InOrder(BiTree T){ if(T) {  InOrder(T->lchild);   //遍历左子树   printf("%c ",T->data); //访问结点  InOrder(T->rchild);   //遍历右子树 }}//后序遍历的递归void PostOrder(BiTree T){ if(T) {  PostOrder(T->lchild); //遍历左子树  PostOrder(T->rchild); //访问结点  printf("%c ",T->data); //遍历右子树 }}//非递归中序遍历   void InOrderTraverse(BiTree T){ stack S; BiTree p; S。
  push(T);//跟指针进栈 while(!S。empty()) {  p=new BiTNode;  while((p=S。top())&&p)   S。push(p->lchild);//向左走到尽头  S。
  pop(); //空指针退栈  if(!S。empty())  {   p=S。top();   S。pop();   coutrchild);  } }}//先序遍历的非递归void PreOrder_Nonrecursive(BiTree T){ stack S; BiTree p;  S。
  push(T);//根指针进栈 while(!S。empty())//栈空时结束 {  while((p=S。top())&&p)  {   coutlchild);  }//向左走到尽头  S。
  pop();//弹出堆栈  if(!S。empty())  {   p=S。top();   S。pop();   S。push(p->rchild);//向右走一步  } }}void LeverTraverse(BiTree T){//非递归层次遍历 queue Q; BiTree p; p = T; if(visit(p)==1)  Q。
  push(p); while(!Q。empty()) {  p = Q。front();  Q。pop();  if(visit(p->lchild) == 1)    Q。push(p->lchild);  if(visit(p->rchild) == 1)   Q。
  push(p->rchild); }}int visit(BiTree T){ if(T) {  printf("%c ",T->data);  return 1; } else  return 0;}。
  收起