数据结构上机实验报告二叉树.docx

数据结构上机实验报告二叉树.docx

《数据结构上机实验报告二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构上机实验报告二叉树.docx（9页珍藏版）》请在冰点文库上搜索。

数据结构上机实验报告二叉树

实现代码:

#ifndefTREE_H

#defineTREE_H

#include

#include

#include

#include

#include

usingnamespacestd;

typedefintElemType;

typedefstructtreeT

{

ElemTypekey;

structtreeT*left;

structtreeT*right;

}treeT,*pTreeT;

staticvoidvisit（pTreeTroot）

{

if（NULL!

=root）

{

printf（"%d\n",root->key）;

}

}

staticpTreeTBT_MakeNode（ElemTypetarget）

{

pTreeTpNode=（pTreeT）malloc（sizeof（treeT））;

assert（NULL!

=pNode）;

pNode->key=target;

pNode->left=NULL;

pNode->right=NULL;

returnpNode;

}

pTreeTBT_Insert（ElemTypetarget,pTreeT*ppTree）

{

pTreeTNode;

assert（NULL!

=ppTree）;

Node=*ppTree;

if（NULL==Node）

{

return*ppTree=BT_MakeNode（target）;

}

if（Node->key==target）//不允许出现相同的元素

{

returnNULL;

}

elseif（Node->key>target）//向左

{

returnBT_Insert（target,&Node->left）;

}

else

{

returnBT_Insert（target,&Node->right）;

}

}

voidBT_PreOrder（pTreeTroot）

{

if（NULL!

=root）

{

visit（root）;

BT_PreOrder（root->left）;

BT_PreOrder（root->right）;

}

}

voidBT_PreOrderNoRec（pTreeTroot）

{

stacks;

while（（NULL!

=root）||!

s.empty（））

{

if（NULL!

=root）

{

visit（root）;

s.push（root）;

root=root->left;

}

else

{

root=s.top（）;

s.pop（）;

root=root->right;

}

}

}

voidBT_InOrder（pTreeTroot）

{

if（NULL!

=root）

{

BT_InOrder（root->left）;

visit（root）;

BT_InOrder（root->right）;

}

}

voidBT_InOrderNoRec（pTreeTroot）

{

stacks;

while（（NULL!

=root）||!

s.empty（））

{

if（NULL!

=root）

{

s.push（root）;

root=root->left;

}

else

{

root=s.top（）;

visit（root）;

s.pop（）;

root=root->right;

}

}

}

voidBT_PostOrder（pTreeTroot）

{

if（NULL!

=root）

{

BT_PostOrder（root->left）;

BT_PostOrder（root->right）;

visit（root）;

}

}

voidBT_PostOrderNoRec（pTreeTroot）

{

}

voidBT_LevelOrder（pTreeTroot）

{

queueq;

treeT*treePtr;

assert（NULL!

=root）;

q.push（root）;

while（!

q.empty（））

{

treePtr=q.front（）;

q.pop（）;

visit（treePtr）;

if（NULL!

=treePtr->left）

{

q.push（treePtr->left）;

}

if（NULL!

=treePtr->right）

{

q.push（treePtr->right）;

}

}

}

#endif

#include

#include

#include

#defineMAX_CNT5

#defineBASE100

voidmain（intargc,char*argv[]）

{

inti;

chartemp;

pTreeTroot=NULL;

srand（（unsigned）time（NULL））;

printf（"请输入元素：

\nA.自动生成.\nB.手动输入.\n"）;

do{

temp=getchar（）;

}

while（!

（temp=='A'||temp=='a'||temp=='B'||temp=='b'））;

if（（temp）=='A'||（temp）=='a'）{

for（i=0;i

{

BT_Insert（rand（）%BASE,&root）;

}

}

elseif（（temp）=='B'||（temp）=='b'）{

printf（"请输入元素,元素以#结尾\n"）;

while（（temp=getchar（））!

='#'）

BT_Insert（temp,&root）;

}

//前序

printf（"PreOrder:

\n"）;

BT_PreOrder（root）;

printf（"\n"）;

printf（"PreOrdernorecursion:

\n"）;

BT_PreOrderNoRec（root）;

printf（"\n"）;

//中序

printf（"InOrder:

\n"）;

BT_InOrder（root）;

printf（"\n"）;

printf（"InOrdernorecursion:

\n"）;

BT_InOrderNoRec（root）;

printf（"\n"）;

//后序

printf（"PostOrder:

\n"）;

BT_PostOrder（root）;

printf（"\n"）;

//层序

printf（"LevelOrder:

\n"）;

BT_LevelOrder（root）;

printf（"\n"）;

}