求树和二叉树的深度题目及源程序代码Word格式文档下载.doc
- 文档编号:7006379
- 上传时间:2023-05-07
- 格式:DOC
- 页数:12
- 大小:67.50KB
求树和二叉树的深度题目及源程序代码Word格式文档下载.doc
《求树和二叉树的深度题目及源程序代码Word格式文档下载.doc》由会员分享,可在线阅读,更多相关《求树和二叉树的深度题目及源程序代码Word格式文档下载.doc(12页珍藏版)》请在冰点文库上搜索。
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
boolCreateBiTree(BiTree&
T){
//先序序列建立二叉树
charch;
scanf("
%c"
&
ch);
if(ch=='
*'
)T=NULL;
else{
if(!
(T=(BiTNode*)malloc(sizeof(BiTNode))))returnERROR;
T->
data=ch;
CreateBiTree(T->
lchild);
rchild);
}
returnOK;
}
StatusPrintElement(TElemTypee){
//访问函数
printf("
e);
StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){
//先序遍历二叉树的递归算法
if(T){
if(Visit(T->
data))
if(PreOrderTraverse(T->
lchild,Visit))
rchild,Visit))returnOK;
returnERROR;
}elsereturnOK;
StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){
//中序遍历二叉树的递归算法
if(InOrderTraverse(T->
StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){
//后序遍历二叉树的递归算法
if(PostOrderTraverse(T->
rchild,Visit))
data))returnOK;
/*栈存储结构及操作
*/
typedefstruct{
BiTree*base;
BiTree*top;
intstacksize;
}Stack;
StatusInitStack(Stack&
S){
//构造空栈
S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));
S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
StatusGetTop(StackS,BiTree&
e){
//读栈顶元素
if(S.top==S.base)returnERROR;
e=*(S.top-1);
StatusPush(Stack&
S,BiTreee){
//入栈
if(S.top-S.base>
=S.stacksize){
S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*
sizeof(BiTree));
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top++=e;
StatusPop(Stack&
S,BiTree&
//出栈
e=*--S.top;
StatusStackEmpty(StackS){
//判栈空
if(S.base==S.top)returnTRUE;
elsereturnFALSE;
StatusInOrderTraverse2(BiTreeT,Status(*Visit)(TElemType)){
//中序遍历二叉树的非递归算法
StackS;
BiTreep;
InitStack(S);
Push(S,T);
while(!
StackEmpty(S)){
while(GetTop(S,p)&
&
p)Push(S,p->
Pop(S,p);
Pop(S,p);
Visit(p->
data))returnERROR;
Push(S,p->
#defineMAXLEN100
voidLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){
//层次遍历二叉树
structnode
{
BiTreevec[MAXLEN];
intf,r;
}q;
q.f=0;
q.r=0;
if(T!
=NULL)Visit(T->
data);
q.vec[q.r]=T;
q.r=q.r+1;
while(q.f<
q.r){
T=q.vec[q.f];
q.f=q.f+1;
if(T->
lchild!
=NULL){
Visit(T->
lchild->
q.vec[q.r]=T->
lchild;
if(T->
rchild!
rchild->
rchild;
intBiTreeDepth(BiTreeT){
//求二叉树的深度
intdepthval,depthLeft,depthRight;
T)depthval=0;
depthLeft=BiTreeDepth(T->
lchild);
depthRight=BiTreeDepth(T->
rchild);
depthval=1+(depthLeft>
depthRight?
depthLeft:
depthRight);
returndepthval;
/*树的二叉链表储存结构*/
typedefstructCSNode{
structCSNode*firstchild,*nextsibling;
}CSNode,*CSTree;
/*队列存储结构及操作
typedefstructQNode{
CSTreedata;
structQNode*next;
}QNode,*QueuePtr;
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
StatusInitQueue(LinkQueue&
Q){
//构造空队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
Q.front)exit(OVERFLOW);
Q.front->
next=NULL;
StatusDestoryQueue(LinkQueue&
//销毁队列
while(Q.front){
Q.rear=Q.front->
next;
free(Q.front);
Q.front=Q.rear;
StatusEnQueue(LinkQueue&
Q,CSTreee){
//入队
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
p)exit(OVERFLOW);
p->
data=e;
p->
Q.rear->
next=p;
Q.rear=p;
StatusDeQueue(LinkQueue&
Q,CSTree&
e){
//出队
if(Q.front==Q.rear)returnERROR;
p=Q.front->
e=p->
data;
next=p->
if(Q.rear==p)Q.rear=Q.front;
free(p);
StatusGetHead(LinkQueue&
//读队头
CSTreeGetTreeNode(TElemTypee){
//建立树的孩子
//-兄弟链表结点
CSTreep;
p=(CSTree)malloc(sizeof(CSNode));
firstchild=NULL;
nextsibling=NULL;
returnp;
StatusCreatTree(CSTree&
//-兄弟链表
charfirst='
'
second='
;
intresult=0;
LinkQueueQ;
CSTreep,s,r;
InitQueue(Q);
T=NULL;
for(scanf("
%c%c"
&
first,&
second);
second!
='
#'
result=scanf("
first,
second)){
p=GetTreeNode(second);
EnQueue(Q,p);
if(first=='
)T=p;
else{
GetHead(Q,s);
while(s->
data!
=first){
DeQueue(Q,s);
GetHead(Q,s);
(s->
firstchild)){
s->
firstchild=p;
r=p;
}else{
r->
nextsibling=p;
r=p;
}
intTreeDepth(CSTreeT){
//求树的深度
inth1,h2;
T)return0;
h1=TreeDepth(T->
firstchild);
h2=TreeDepth(T->
nextsibling);
return(((h1+1)>
h2)?
(h1+1):
h2);
intmain(intargc,char*argv[])
BiTreetestT;
请输入二叉树先序序列(如AB*C***):
"
);
CreateBiTree(testT);
printf("
\n"
二叉树的深度是:
"
%d"
BiTreeDepth(testT));
先序递归遍历顺序:
PreOrderTraverse(testT,PrintElement);
中序递归遍历顺序:
InOrderTraverse(testT,PrintElement);
后序递归遍历顺序:
PostOrderTraverse(testT,PrintElement);
层次非递归遍历顺序:
LevelOrderTraverse(testT,PrintElement);
中序非递归遍历顺序:
InOrderTraverse2(testT,PrintElement);
\n\n"
while(getchar()!
\n'
//清除缓冲区字符
CSTreetestT2;
自上而下自左至右输入树的各条边(如#AABACADCECFEG##):
CreatTree(testT2);
树的深度是:
TreeDepth(testT2));
return0;
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 深度 题目 源程序 代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)