二叉樹的存儲與遍歷實現(xiàn)實驗報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗五學(xué)院軟件學(xué)院 班級13級.NET班 學(xué)號 132862 4 0 0 4 姓名劉 振 龍二叉樹的存儲與遍歷實現(xiàn)實驗報告學(xué)號1328624004姓名劉振龍時間2014.10.10專業(yè)計算機科學(xué)與技術(shù)班級.Net實驗題目：二叉樹的存儲與遍歷的實現(xiàn)一、實驗?zāi)康模? .了解二叉樹的存儲與遍歷 的運算算法的實現(xiàn)；2 .分析算法的空間復(fù)雜度和插入和刪除及遍歷的時間復(fù)雜度；3 .總結(jié)二叉樹順序存儲與遍歷的特點。4 .了解二叉樹的基本操作在順序存儲上的實現(xiàn)和遍歷上的實現(xiàn)；5 .以二叉樹的各種操作(建立、插入、刪除和遍歷等)；6 .掌握二叉樹順序存儲結(jié)構(gòu)的定義和基本操作的實現(xiàn)； 二、實驗分析

2、：(1).二叉樹的順序存儲的實現(xiàn)。O建立一個二叉樹(先中后都可)，在演示過程中必須按ENTE瞰，方可看到運行結(jié)果。 (1)本實驗建立 一個中序二叉樹；(2)進(jìn)行二叉樹的遍歷。二.概要設(shè)計1 .二叉樹的存儲：ADT Tree 數(shù)據(jù)對象D: D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R若D為空集，則稱為空樹；若D中僅含一個數(shù)據(jù)元素，則關(guān)系R為空集；否則R=H , H是如下二元關(guān)系：(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root ,它在關(guān)系H下無前驅(qū)；(2) 若 D-root ?？，則存在D-root 的一個劃分 D,D2,D3,Dm(m>0),即對于任意的 j ?k(1Wj,k Wm)有

3、DAR=?, 且對任意的i=1,2,m。惟一存在數(shù)據(jù)元素Xi6D,有<。« i> H3)對應(yīng)于D-root的以上劃分，H-<root,x i> ,<root,x 2>,<root,x m> 有惟一的一個劃分 Hi,H2,H,Hm(m>0),即對于任意的j ?k(1Wj,k Wm)有HH=,且對 任意的i(1 wi Wm),Hi是D上的二元關(guān)系，(Di, H)是一棵符合本 定義的樹，稱為根 root 的子樹。InitBiTree(&T);DestroyBiTree(&T); BiTreeEmpty(T);Create

4、BiTree(&T, definition); BiTreeDepth(T); Value(T, e); ClearBiTree(&T);DeleteChild(T, p, LR); Root(T);Assign(T, &e, value);InsertChild(T, p, LR, c);Parent(T, e); LeftChild(T, e); RightChild(T, e);LeftSibling(T, e); RightSibling(T, e);PreOrderTraverse(T, Visit();InOrderTraverse(T, Visit();P

5、ostOrderTraverse(T, Visit();LevelOrderTraverse(T, Visit();typedef struct TriTNode 結(jié)點結(jié)構(gòu)TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指針struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;2. #define MAX_TREE_SIZE 100 /二叉樹的最大結(jié)點數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE;/ 0號單元存儲根結(jié)點SqBiTree bt;void Pre

6、OrderTraverse (BiTree T, void( *visit)(TElemType e) /先序遍歷二叉樹if (T)visit(T->data); /訪問根結(jié)點PreOrderTraverse(T->lchild, visit); /先序遍歷左子樹PreOrderTraverse(T->rchild, visit);/先序遍歷右子樹void PreOrderTraverse (BiTree T, void( *visit)(TElemType e) /先序遍歷二叉樹的非遞歸算法InitStack(S); push(S,T);while (! StackEmpt

7、y(S) while(GetTop(S, P)&&P)visit(P->data); push(S, P->lchild);pop(S,P);if(! StackEmpty(S) pop(S,P);push(S,P->rchild);/if/while/ PreOrderTraversevoid InOrderTraverse (BiTree T,void( *visit)(TElemType e) /中序遍歷二叉樹if (T)InOrderTraverse(T->lchild, visit); /中序遍歷左子樹visit(T->data); /訪

8、問根結(jié)點1:InOrderTraverse(T->rchild, visit);/中序遍歷右子樹/ 2: InOrderTraversevoid LevelOrderTraverse(BiTree T, Status (*viste)(TElemType e) /按層次遍歷二叉鏈表存儲的二叉樹if(T) InitQueue(Q);/初始化一個隊列EnQueue(Q,T);/根進(jìn)隊列while(!QueueEmpty(Q) DelQueue(Q,P);viste(p->data);/訪問if(P->lchild) EnQueue(Q, P->lchild); /左孩子進(jìn)隊

9、列if(P->rchild) EnQueue(Q, P->rchild); /右孩子進(jìn)隊列/ while/ if/ LevelOrderTraverse三實驗步驟(包括主要步驟、代碼分析等)#include<stdio.h>#include<stdary.h>#define MAXSIZE 100*lchild,typedef struct BiTNode char data; struct BiTNode*rchild; BiTNode,*BiTree;BiTree CreateBiTree() BiTree T;char ch=getchar(); if

10、(ch='#') T=NULL;else T=(BiTNode *)malloc(sizeof(BiTNode);T->data=ch;T->lchild=CreateBiTree();T->rchild=CreateBiTree(); return T; 遞歸生成二叉樹，用砧表空子樹void preorder(BiTree t)if(t) printf("%c ”,t->data);preorder(t->lchild);preorder(t->rchild); / 遞歸先序遍歷 void Inorder(BiTree T)if(

11、T) Inorder(T->lchild); printf("%c ",T->data);Inorder(T->rchild); / 遞歸中序遍歷 void postorder(BiTree t) if(t) preorder(t->lchild);preorder(t->rchild);printf("%c ",t->data); / 遞歸后序遍歷 void NInorder(BiTree T) BiTree stackMAXSIZE; BiTree p=T;int top=-1;while(p|top!=-1)if

12、(p) top+; stacktop=p; p=p->lchild; else p=stacktop; top-;printf("%c ",p->data);p=p->rchild; /非遞歸中序遍歷main() BiTree T;printf("please input the tree:");T=CreateBiTree(); printf("n");getch();printf("the tree after preorder is:");preorder(T);printf("n

13、");getch();printf("the tree after ineorder is:");Inorder(T);printf("n");getch();printf("the tree after postorder is:");postorder(T);printf("n");getch()；printf("the tree after noinorder is:");NInorder(T);printf("n");getch()；鄴八爐4a的人數(shù)3;8

14、展次籍"個權(quán)值(整型)：6 4 3 7 e 11 9遍遍遍 :先程 樣歸歸歸出 It.詩通遞退進(jìn)以的示梃 更表X 埼一二艮林以三個空檔后回軍結(jié)束口2 3 4 5 6 向車，EC DE G F二立二叉樹已經(jīng)完畢！請輸入遍歷的F ：'iff：.遞歸先生遍歷.遞歸中南遍歷歸中序褊歷二叉樹:C B E G D F fl歸先序遍歷二又樹二。B C D E G F的編碼為沏1團(tuán)超停您的烹鴛.樹I為6的字符的編明為物二屋為4的字符的編明為:1網(wǎng)工 我的字例的編用為二1小 為V的生處的愈刑為:1師為8的空椅的編叫為力工8：1011T x值為11的字符的編碼為二00 便將為9的字符也編有為11 hress anu key to continue四.體驗分析：(1)本次實驗是完成二叉樹的存儲和遍歷，通過本次實驗我學(xué)會了如何建立個二叉樹的存儲及遍歷，存儲為順序遍歷分為先中后三次遍歷， 本次試驗中先完 成了建立即存儲，兒后依次完成了三次遍歷，由于本次試驗的使用性比較高因而 學(xué)好了(2)本次實驗以后在工作中也會有很大的幫助，我學(xué)到了很多關(guān)于二叉樹的相 關(guān)技術(shù)。(通過本實驗我對二叉樹的