《二叉树遍历所有代码》由会员分享，可在线阅读，更多相关《二叉树遍历所有代码（6页珍藏版）》请在金锄头文库上搜索。
1、#include #include #include #include #include #define SIZE 100 using namespace std; typedef struct BiTNode / 定义二叉树节点结构 char data; /数据域struct BiTNode *lchild,*rchild; /左右孩子指针域BiTNode,*BiTree; int visit(BiTree t); void CreateBiTree(BiTree / 生成一个二叉树void PreOrder(BiTree); / 递归先序遍历二叉树void InOrder(BiTree);
2、 / 递归中序遍历二叉树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(“ 本程序实现二叉树的操作。n“); printf(“ 叶子结点以空格表示。n“); printf(“ 可以进行建
3、立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。 n“); /- printf(“n“); printf(“ 请建立二叉树。 n“); printf(“ 建树将以三个空格后回车结束。n“); printf(“ 例如 :1 2 3 4 5 6 (回车 )n“); CreateBiTree(T); / 初始化队列getchar(); while(flag) printf(“n“); printf(“ 请选择 : n“); printf(“1. 递归先序遍历 n“); printf(“2. 递归中序遍历 n“); printf(“3. 递归后序遍历 n“); prin
4、tf(“4. 非递归中序遍历n“); printf(“5. 非递归先序遍历n“); printf(“6. 非递归层序遍历n“); printf(“0. 退出程序 n“); scanf(“ %c“, switch(j) case 1:if(T) printf(“ 递归先序遍历二叉树:“); PreOrder(T); printf(“n“); else printf(“ 二叉树为空 !n“); break; case 2:if(T) printf(“ 递归中序遍历二叉树:“); InOrder(T); printf(“n“); else printf(“ 二叉树为空 !n“); break; ca
5、se 3:if(T) printf(“ 递归后序遍历二叉树:“); PostOrder(T); printf(“n“); else printf(“ 二叉树为空 !n“); break; case 4:if(T) printf(“ 非递归中序遍历二叉树:“); InOrderTraverse(T); printf(“n“); else printf(“ 二叉树为空 !n“); break; case 5:if(T) printf(“ 非递归先序遍历二叉树:“); PreOrder_Nonrecursive(T); printf(“n“); else printf(“ 二叉树为空 !n“); b
6、reak; case 6:if(T) printf(“ 非递归层序遍历二叉树:“); LeverTraverse(T); printf(“n“); else printf(“ 二叉树为空 !n“); break; default:flag=0;printf(“ 程序运行结束，按任意键退出!n“); /建立二叉树void CreateBiTree(BiTree scanf(“%c“, / 读入一个字符if(ch= ) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); /生成一个新结点T-data=ch; CreateBiTree(T-lchild
7、); / 生成左子树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 PostOr
8、der(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()/ 向左走到尽头S.pop(); /空指针退栈if(!S.empty() p=S.top(); S.pop(); coutdatarchild);
9、/先序遍历的非递归void PreOrder_Nonrecursive(BiTree T) stack S; BiTree p; S.push(T);/根指针进栈while(!S.empty()/ 栈空时结束 while(p=S.top() / 向左走到尽头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;
