數(shù)據(jù)結(jié)構(gòu)實驗報告6二叉樹的操作

1/7數(shù)據(jù)結(jié)構(gòu)實驗報告（6）學(xué)院：專業(yè)：班級：姓名學(xué)號實驗組實驗時間2011-12-9指導(dǎo)教師成績實驗項目名稱二叉樹的操作實驗?zāi)康?．掌握二叉樹的存儲實現(xiàn)。2．掌握二叉樹的遍歷思想。3．掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實驗要求和原理根據(jù)實驗內(nèi)容編程，上機調(diào)試、得出正確的運行程序。2.編譯運行程序，觀察運行情況和輸出結(jié)果。3.寫出實驗報告（包括源程序和運行結(jié)果）。運行環(huán)境運行Visualc++的微機一臺實驗內(nèi)容1.

建立二叉樹。2、二叉樹的三種遍歷。實驗步驟及程序清單#include<stdio.h>#include<iostream>#include<queue>#include<stack>#include<malloc.h>#defineSIZE100usingnamespacestd;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intvisit(BiTreet);voidCreateBiTree(BiTree&T);voidPreOrder(BiTree);voidInOrder(BiTree);voidPostOrder(BiTree);voidInOrderTraverse(BiTreeT);voidPreOrder_Nonrecursive(BiTreeT);voidLeverTraverse(BiTreeT);voidmain(){BiTreeT;charj;intflag=1;printf("本程序?qū)崿F(xiàn)二叉樹的操作。\n");printf("葉子結(jié)點以空格表示。\n");printf("可以進行建立二叉樹，遞歸先序、中序、后序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n");printf("\n");printf("請建立二叉樹。\n");printf("建樹將以三個空格后回車結(jié)束。\n");printf("例如:123456(回車)\n");CreateBiTree(T);getchar();while(flag){printf("\n");printf("請選擇:\n");printf("1.遞歸先序遍歷\n");printf("2.遞歸中序遍歷\n");printf("3.遞歸后序遍歷\n");printf("4.非遞歸中序遍歷\n");printf("5.非遞歸先序遍歷\n");printf("6.非遞歸層序遍歷\n");printf("0.退出程序\n");scanf("%c",&j);switch(j){case'1':if(T){printf("遞歸先序遍歷二叉樹:");PreOrder(T);printf("\n");}elseprintf("二叉樹為空!\n");break;case'2':if(T){printf("遞歸中序遍歷二叉樹:");InOrder(T);printf("\n");}elseprintf("二叉樹為空!\n");break;case'3':if(T){printf("遞歸后序遍歷二叉樹:");PostOrder(T);printf("\n");}elseprintf("二叉樹為空!\n");break;case'4':if(T){printf("非遞歸中序遍歷二叉樹:");InOrderTraverse(T);printf("\n");}elseprintf("二叉樹為空!\n");break;case'5':if(T){printf("非遞歸先序遍歷二叉樹:");PreOrder_Nonrecursive(T);printf("\n");}elseprintf("二叉樹為空!\n");break;case'6':if(T){printf("非遞歸層序遍歷二叉樹:");LeverTraverse(T);printf("\n");}elseprintf("二叉樹為空!\n");break;default:flag=0;printf("程序運行結(jié)束，按任意鍵退出!\n");}}}voidCreateBiTree(BiTree&T){charch;scanf("%c",&ch);if(ch=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}voidPreOrder(BiTreeT){if(T){printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}voidInOrder(BiTreeT){if(T){InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}voidPostOrder(BiTreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);printf("%c",T->data);}}voidInOrderTraverse(BiTreeT){stack<BiTree>S;BiTreep;S.push(T);while(!S.empty()){p=newBiTNode;while((p=S.top())&&p)S.push(p->lchild);S.pop();if(!S.empty()){p=S.top();S.pop();cout<<p->data<<"";S.push(p->rchild);}}}voidPreOrder_Nonrecursive(BiTreeT){stack<BiTree>S;BiTreep;S.push(T);while(!S.empty()){while((p=S.top())&&p){cout<<p->data<<"";S.push(p->lchild);}S.pop();if(!S.empty()){p=S.top();S.pop();S.push(p->rchild);}}}voidLeverTraverse(BiTreeT){queue<BiTree>Q;BiTreep;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)