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

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

建立二叉樹(shù)。2、二叉樹(shù)的三種遍歷。實(shí)驗(yàn)步驟及程序清單#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)二叉樹(shù)的操作。\n");printf("葉子結(jié)點(diǎn)以空格表示。\n");printf("可以進(jìn)行建立二叉樹(shù)，遞歸先序、中序、后序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n");printf("\n");printf("請(qǐng)建立二叉樹(shù)。\n");printf("建樹(shù)將以三個(gè)空格后回車(chē)結(jié)束。\n");printf("例如:123456(回車(chē))\n");CreateBiTree(T);getchar();while(flag){printf("\n");printf("請(qǐng)選擇:\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("遞歸先序遍歷二叉樹(shù):");PreOrder(T);printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;case'2':if(T){printf("遞歸中序遍歷二叉樹(shù):");InOrder(T);printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;case'3':if(T){printf("遞歸后序遍歷二叉樹(shù):");PostOrder(T);printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;case'4':if(T){printf("非遞歸中序遍歷二叉樹(shù):");InOrderTraverse(T);printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;case'5':if(T){printf("非遞歸先序遍歷二叉樹(shù):");PreOrder_Nonrecursive(T);printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;case'6':if(T){printf("非遞歸層序遍歷二叉樹(shù):");LeverTraverse(T);printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;default:flag=0;printf("程序運(yùn)行結(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)