树和二叉树

数据结构题集

第六章 树和二叉树

1. 请写出利用栈对二叉树进行先根次序遍历的非递归算法。

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法

{

InitStack(S);

Push(S,T); //根指针进栈

while(!StackEmpty(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); //向右一步

}

}//while

}//PreOrder_Nonrecursive

2.编写递归算法，在二叉树中求位于先序序列中第K个位置的结点的值。

int c,k; //这里把k和计数器c作为全局变量处理

void Get_PreSeq(Bitree T)//求先序序列为k的结点的值

{

if(T)

{

c++; //每访问一个子树的根都会使前序序号计数器加1

if(c==k)

{

printf("Value is %d\n",T->data);

exit (1);

}

else

{

Get_PreSeq(T->lchild); //在左子树中查找

Get_PreSeq(T->rchild); //在右子树中查找

}

}//if

}//Get_PreSeq

数据结构题集

main()

{

...

scanf("%d",&k);

c=0; //在主函数中调用前,要给计数器赋初值0

Get_PreSeq(T,k);

...

}//main

3.编写递归算法，计算二叉树中叶子结点的数目。

Int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目

{

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数

}//LeafCount_BiTree

4. 编写递归算法，将二叉树中所有结点的左、右子树相互交换。

Void Bitree_Revolute(Bitree T)//交换所有结点的左右子树

{

T->lchild<->T->rchild; //交换左右子树

if(T->lchild) Bitree_Revolute(T->lchild);

if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树

}//Bitree_Revolute

5. 编写递归算法，求二叉树中以元素值为X的结点为根的子树的深度。

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度

{

if(T->data==x)

{

printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度

exit 1;

}

else

{

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找

}

}//Get_Sub_Depth

数据结构题集

int Get_Depth(Bitree T)//求子树深度的递归算法

{

if(!T) return 0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}//Get_Depth

6. 编写复制一棵二叉树的非递归算法。

void Bitree_Copy_Nonrecursive(Bitree T,Bitree &U)//非递归复制二叉树

{

InitStack(S1);InitStack(S2);

push(S1,T); //根指针进栈

U=(BTNode*)malloc(sizeof(BTNode));

U->data=T->data;

q=U;push(S2,U);

while(!StackEmpty(S))

{

while(Gettop(S1,p)&&p)

{

q->lchild=(BTNode*)malloc(sizeof(BTNode));

q=q->lchild;q->data=p->data;

push(S1,p->lchild);

push(S2,q);

} //向左走到尽头

pop(S1,p);

pop(S2,q);

if(!StackEmpty(S1))

{

pop(S1,p);pop(S2,q);

q->rchild=(BTNode*)malloc(sizeof(BTNode));

q=q->rchild;q->data=p->data;

push(S1,p->rchild); //向右一步

push(S2,q);

}

}//while

}//BiTree_Copy_Nonrecursive

7. 编写算法判别给定二叉树是否为完全二叉树。

数据结构题集

int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0

{

InitQueue(Q);

flag=0;

EnQueue(Q,T); //建立工作队列

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

if(!p) flag=1;

else if(flag) return 0;

else

{

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列

}

}//while

return 1;

}//IsFull_Bitree

分析:该问题可以通过层序遍历的方法来解决.不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.

8. 对以孩子-兄弟链表表示的树编写计算树的深度的算法。

int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度

{

if(!T) return 0; //空树

else

{

for(maxd=0,p=T->firstchild;p;p=p->nextsib)

if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度

return maxd+1;

}

}//GetDepth_CSTree

9. 对以孩子链表表示的树编写计算树的深度的算法。

int GetDepth_CTree(CTree A)//求孩子链表表示的树A的深度

{

return SubDepth(A.r);

}//GetDepth_CTree

int SubDepth(int T)//求子树T的深度

{

if(!A.nodes[T].firstchild) return 1;

数据结构题集

for(sd=1,p=A.nodes[T].firstchild;p;p=p->next)

if((d=SubDepth(p->child))>sd) sd=d;

return sd+1;

}//SubDepth

10. 已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

char Pred,Ind; //假设前序序列和中序序列已经分别储存在数组Pre和In中

Bitree Build_Sub(int Pre_Start,int Pre_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表

{

sroot=(BTNode*)malloc(sizeof(BTNode)); //建根

sroot->data=Pre[Pre_Start];

for(i=In_Start;In[i]!=sroot->data;i++); //在中序序列中查找子树根

leftlen=i-In_Start;

rightlen=In_End-i; //计算左右子树的大小

if(leftlen)

{

lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1);

sroot->lchild=lroot;

} //建左子树,注意参数表的计算

if(rightlen)

{

rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End);

sroot->rchild=rroot;

} //建右子树,注意参数表的计算

return sroot; //返回子树根

}//Build_Sub

main()

{

...

Build_Sub(1,n,1,n); //初始调用参数,n为树结点总数

...

}

分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.

本文来源：https://www.bwwdw.com/article/lk2i.html