第六章 树和二叉树
int Is_Descendant_C(int uint v)//在孩子存储结构上判断u是否v的子孙是则返回否则返回
{
if(u==v) return ;
else
{
if(L[v])
if (Is_Descendant(uL[v])) return ;
if(R[v])
if (Is_Descendant(uR[v])) return ; //这是个递归算法
}
return ;
}//Is_Descendant_C
int Is_Descendant_P(int uint v)//在双亲存储结构上判断u是否v的子孙是则返回否则返回
{
for(p=u;p!=v&&p;p=T[p]);
if(p==v) return ;
else return ;
}//Is_Descendant_P
这一题根本不需要写什么算法见书后注释:两个整数的值是相等的
int Bitree_Sim(Bitree BBitree B)//判断两棵树是否相似的递归算法
{
if(!B&&!B) return ;
else if(B&&B&&Bitree_Sim(B>lchildB>lchild)&&Bitree_Sim(B>rchildB>rchild))
return ;
else return ;
}//Bitree_Sim
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
InitStack(S);
Push(ST); //根指针进栈
while(!StackEmpty(S))
{
while(Gettop(Sp)&&p)
{
visit(p>data);
push(Sp>lchild);
} //向左走到尽头
pop(Sp);
if(!StackEmpty(S))
{
pop(Sp);
push(Sp>rchild); //向右一步
}
}//while
}//PreOrder_Nonrecursive
typedef struct {
BTNode* ptr;
enum {} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法用栈
{
PMType a;
InitStack(S); //S的元素为PMType类型
Push (S{T}); //根结点入栈
while(!StackEmpty(S))
{
Pop(Sa);
switch(amark)
{
case :
Push(S{aptr}); //修改mark域
if(aptr>lchild) Push(S{aptr>lchild}); //访问左子树
break;
case :
Push(S{aptr}); //修改mark域
if(aptr>rchild) Push(S{aptr>rchild}); //访问右子树
break;
case :
visit(aptr); //访问结点返回
}
}//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式在堆栈中增加一个mark域mark=表示刚刚访问此结点mark=表示左子树处理结束返回mark=表示右子树处理结束返回每次根据栈顶元素的mark域值决定做何种动作
typedef struct {
int data;
EBTNode *lchild;
EBTNode *rchild;
EBTNode *parent;
enum {} mark;
} EBTNodeEBitree; //有mark域和双亲指针域的二叉树结点类型
void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法不用栈
{
p=T;
while(p)
switch(p>mark)
{
case :
p>mark=;
if(p>lchild) p=p>lchild; //访问左子树
break;
case :
p>mark=;
if(p>rchild) p=p>rchild; //访问右子树
break;
case :
visit(p);
p>mark=; //恢复mark值
p=p>parent; //返回双亲结点
}
}//PostOrder_Nonrecursive
分析:本题思路与上一题完全相同只不过结点的mark值是储存在结点中的而不是暂存在堆栈中所以访问完毕后要将mark域恢复为以备下一次遍历
typedef struct {
int data;
PBTNode *lchild;
PBTNode *rchild;
PBTNode *parent;
} PBTNodePBitree; //有双亲指针域的二叉树结点类型
void Inorder_Nonrecursive(PBitree T)//不设栈非递归遍历有双亲指针的二叉树
{
p=T;
while(p>lchild) p=p>lchild; //向左走到尽头
while(p)
{
visit(p);
if(p>rchild) //寻找中序后继:当有右子树时
{
p=p>rchild;
while(p>lchild) p=p>lchild; //后继就是在右子树中向左走到尽头
}
else if(p>parent>lchild==p) p=p>parent; //当自己是双亲的左孩子时后继就是双亲
else
{
p=p>parent;
while(p>parent&&p>parent>rchild==p) p=p>parent;
p=p>parent;
} //当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先
}//while
}//Inorder_Nonrecursive
int ck; //这里把k和计数器c作为全局变量处理
void Get_PreSeq(Bitree T)//求先序序列为k的结点的值
{
if(T)
{
c++; //每访问一个子树的根都会使前序序号计数器加
if(c==k)
{
printf(Value is %d\nT>data);
exit ();
}
else
{
Get_PreSeq(T>lchild); //在左子树中查找
Get_PreSeq(T>rchild); //在右子树中查找
}
}//if
}//Get_PreSeq
main()
{
scanf(%d&k);
c=; //在主函数中调用前要给计数器赋初值
Get_PreSeq(Tk);
}//main
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return ; //空树没有叶子
else if(!T>lchild&&!T>rchild) return ; //叶子结点
else return Leaf_Count(T>lchild)+Leaf_Count(T>rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree
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
int Get_Sub_Depth(Bitree Tint x)//求二叉树中以值为x的结点为根的子树深度
{
if(T>data==x)
{
printf(%d\nGet_Depth(T)); //找到了值为x的结点求其深度
exit ;
}
else
{
if(T>lchild) Get_Sub_Depth(T>lchildx);
if(T>rchild) Get_Sub_Depth(T>rchildx); //在左右子树中继续寻找
}
}//Get_Sub_Depth
int Get_Depth(Bitree T)//求子树深度的递归算法
{
if(!T) return ;
else
{
m=Get_Depth(T>lchild);
n=Get_Depth(T>rchild);
return (m>n?m:n)+;
}
}//Get_Depth
void Del_Sub_x(Bitree Tint x)//删除所有以元素x为根的子树
{
if(T>data==x) Del_Sub(T); //删除该子树
else
{
if(T>lchild) Del_Sub_x(T>lchildx);
if(T>rchild) Del_Sub_x(T>rchildx); //在左右子树中继续查找
}//else
}//Del_Sub_x
void Del_Sub(Bitree T)//删除子树T
{
if(T>lchild) Del_Sub(T>lchild);
if(T>rchild) Del_Sub(T>rchild);
free(T);
}//Del_Sub
void Bitree_Copy_Nonrecursive(Bitree TBitree &U)//非递归复制二叉树
{
InitStack(S);InitStack(S);
push(ST); //根指针进栈
U=(BTNode*)malloc(sizeof(BTNode));
U>data=T>data;
q=
