怎么建立二叉树，然后先序遍历？
#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;}。
收起
