6.33③ 假定用两个一维数组L[1..n]和R[1..n]作为
有n个结点的二叉树的存储结构， L[i]和R[i]分别指
示结点i的左孩子和右孩子，0表示空。试写一个算法
判别结点u是否为结点v的子孙。
要求实现以下函数：
Status Dencendant(Array1D L,Array1D R,int n,int u,int v);
/* If node ‘u’ is the dencendant of node ‘v’, */
/* then return ‘TRUE’ else return ‘FALSE’. */
/* L[i] is the left child of the i_th node, */
/* R[i] is the right child of the i_th node */
/* in the Binary Tree which has n nodes. */
一维数组类型Array1D的定义：
typedef int Array1D[MAXSIZE];
/* If node 'u' is the dencendant of node 'v', */
/* then return 'TRUE' else return 'FALSE'. */
/* L[i] is the left child of the i_th node, */
/* R[i] is the right child of the i_th node */
/* in the Binary Tree which has n nodes. */
{
int flag=0;
if(!v){
return FALSE;
}
else{
if(L[v]==u){
return TRUE;
}
else{
flag+=Dencendant(L,R,n,u,L[v]);
}
if(R[v]==u){
return TRUE;
}
else{
flag+=Dencendant(L,R,n,u,R[v]);
}
if(flag){
return TRUE;
}
return FALSE;
}
}
6.34③ 假定用两个一维数组L[1..n]和R[1..n]作为
有n个结点的二叉树的存储结构， L[i]和R[i]分别指
示结点i的左孩子和右孩子，0表示空。试写一个算法,
先由L和R建立一维数组T[1..n]，使T中第i(i=1,2,…,
n)个分量指示结点i的双亲，然后判别结点u是否为结
点v的子孙。
要求实现以下函数：
Status Dencend(Array1D L, Array1D R, int n, int u, int v, Array1D T);
/******************************************************************/
一维数组类型Array1D的定义：
typedef int Array1D[MAXSIZE];
/******************************************************************/
{
int i,val;
for(i=1;i<=n;++i){//初始化数组T
T[i]=0;
}
for(i=1;i<=n;++i){//建立数组T
T[L[i]]=i;
T[R[i]]=i;
}
val=T[u];
while(val!=0){
if(val==v){
return TRUE;
}
val=T[val];
}
return FALSE;
}
6.36③ 若已知两棵二叉树B1和B2皆为空，或者皆
不空且B1的左、右子树和B2的左、右子树分别相似，
则称二叉树B1和B2相似。试编写算法，判别给定两
棵二叉树是否相似。
要求实现下列函数：
Status Similar(BiTree t1, BiTree t2);
/* 判断两棵二叉树是否相似的递归算法 */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* 判断两棵二叉树是否相似的递归算法 */
{
if(!t1&&!t2){//如果两棵树同为空
return TRUE;
}
else if(t1&&t2){//如果两棵树同为非空,则返回各个子树的比较结果
return Similar(t1->lchild,t2->lchild)&&Similar(t1->rchild,t2->rchild);
}
else{//当两棵树存在不相似的时候时，即一棵为空，一棵非空
return FALSE;
}
}
6.37③ 试直接利用栈的基本操作写出先序遍历的非递归
形式的算法(提示:不必按3.3.2节介绍的从递归到非递归
的方法而直接写出非递归算法)。
要求实现下列函数：
void PreOrder(BiTree bt, void (*visit)(TElemType));
/* 使用栈，非递归先序遍历二叉树bt， */
/* 对每个结点的元素域data调用函数visit */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef BiTree SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
/* 使用栈，非递归先序遍历二叉树bt， */
/* 对每个结点的元素域data调用函数visit */
{
//基本思路：根据工作栈原理，模拟递归的效果~
if(bt){//判断树空
SElemType p=bt;
Stack S;
InitStack(S);
while(!StackEmpty(S)||p){
while(p){//先序访问根节点、遍历左节点
visit(p->data);
Push(S,p);
p=p->lchild;
}
if(!StackEmpty(S)){//遍历右节点，不小心写成while，错了几次~~
Pop(S,p);
p=p->rchild;
}
}
}
}
6.38④ 同6.37题条件，写出后序遍历的非递归算法
(提示：为分辨后序遍历时两次进栈的不同返回点，
需在指针进栈时同时将一个标志进栈）。
要求实现下列函数：
void PostOrder(BiTree bt, void (*visit)(TElemType));
/* 使用栈，非递归后序遍历二叉树bt， */
/* 对每个结点的元素域data调用函数visit */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef struct {
BiTNode *ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
/* 使用栈，非递归后序遍历二叉树bt， */
/* 对每个结点的元素域data调用函数visit */
{
Stack S;
InitStack(S);
SElemType e;
BiTree p=bt;
int tag=0;
if(bt){
e.tag=0;
while(!StackEmpty(S)||p==bt){
while(p&&!tag){
e.ptr=p;
if(p->lchild){//如果存在左子树
p=p->lchild;
e.tag=0;
}
else{//否则为右子树
p=p->rchild;
e.tag=1;
}
Push(S,e);
}//while
GetTop(S,e);
if(!StackEmpty(S)&&e.tag){
Pop(S,e); //叶子结点出栈
p=e.ptr;
visit(p->data);//输出该结点
}
if(!StackEmpty(S)){
Pop(S,e); //得到上一层结点
p=e.ptr;
if(e.tag){//右子树已经入栈
visit(p->data);
p=NULL;
}
else{//右子树没入过栈
if(p->rchild){
p=p->rchild;
tag=0;
e.tag=1;
Push(S,e);
}
else {//没有右子树
visit(p->data);
p=NULL;
}
}
}
else{//栈空则，p为NULL
p=NULL;
}
}//while
}//if
}
6.41③ 编写递归算法，在二叉树中求位于先序序列中
第k个位置的结点的值。
要求实现下列函数：
TElemType PreOrder(BiTree bt, int k);
/* bt is the root node of a binary linked list, */
/* Preorder travel it and find the node whose */
/* position number is k, and return its value. */
/* if can’t found it, then return ‘#’. */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
if(bt){
if(1==count){
e=bt->data;
return 0;
}
else{
if(bt->lchild){
--count;
Get(bt->lchild,count,e);
}
if(bt->rchild){
--count;
Get(bt->rchild,count,e);
}
}
}
}
//没想到可以自己添加函数~~方便很多
TElemType PreOrder(BiTree bt, int k)
/* bt is the root node of a binary linked list, */
/* Preorder travel it and find the node whose */
/* position number is k, and return its value. */
/* if can't found it, then return '#'. */
{
TElemType e;
e='#';
Get(bt,k,e);
return e;
}
6.42③ 编写递归算法，计算二叉树中叶子结点的数目。
要求实现下列函数：
void Leaves(BiTree bt, int &x);
/* Count the leaf node of the BiTree */
/* whose root node is bt to x. */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* Count the leaf node of the BiTree */
/* whose root node is bt to x. */
//题目并没有说x初始化为0，害人不浅啊~~
{
int l1,l2;
if(bt){
if(!bt->lchild&&!bt->rchild){
++x;
}
else{
Leaves(bt->lchild,x);
Leaves(bt->rchild,x);
}
}
}
6.43③ 编写递归算法，将二叉树中所有结点的
左、右子树相互交换。
要求实现下列函数：
void Exchange(BiTree &bt);
/* Exchange the left and right leaves of */
/* bitree whose root node is bt */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* Exchange the left and right leaves of */
/* bitree whose root node is bt */
{
BiTree temp;
if(bt){
Exchange(bt->lchild);
Exchange(bt->rchild);
temp=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=temp;
}
}
6.44④ 编写递归算法：求二叉树中以元素值
为x的结点为根的子树的深度。
要求实现下列函数：
int Depthx(BiTree T, TElemType x);
/* 求二叉树中以值为x的结点为根的子树深度 */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
int l1,l2;
if(!T){
return 0;
}
else{
l1=Depth(T->lchild)+1;
l2=Depth(T->rchild)+1;
return (l1>l2)?l1:l2;
}
}
int Findx(BiTree T,BiTree &p,TElemType x){
if(T){
if(T->data==x){
p=T;
return 0;
}
else{
Findx(T->lchild,p,x);
Findx(T->rchild,p,x);
}
}
}
int Depthx(BiTree T, TElemType x)
/* 求二叉树中以值为x的结点为根的子树深度 */
{
BiTree p=NULL;
Findx(T,p,x);
return Depth(p);
}
6.46③ 编写复制一棵二叉树的非递归算法。
要求实现下列函数：
void CopyBiTree(BiTree T, BiTree &TT);
/* 基于层次遍历的非递归复制二叉链表 */
二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);
/* 基于层次遍历的非递归复制二叉链表 */
//基本思想：用两个队列来同步操作！
{
BiTree p,p2;
Queue Q,Q2;
if(!T){
TT=NULL;
return;
}
TT=(BiTree)malloc(sizeof(BiTNode));
InitQueue(Q);
InitQueue(Q2);
EnQueue(Q,T);
EnQueue(Q2,TT);
while(!QueueEmpty(Q)){
DeQueue(Q,p);
DeQueue(Q2,p2);
p2->data=p->data;
if(p->lchild){
EnQueue(Q,p->lchild);
p2->lchild=(BiTree)malloc(sizeof(BiTNode));
if(!p2->lchild){
exit(OVERFLOW);
}
EnQueue(Q2,p2->lchild);
}
else{
p2->lchild=NULL;
}
if(p->rchild){
EnQueue(Q,p->rchild);
p2->rchild=(BiTree)malloc(sizeof(BiTNode));
if(!p2->rchild){
exit(OVERFLOW);
}
EnQueue(Q2,p2->rchild);
}
else{
p2->rchild=NULL;
}
}
}
6.47④ 编写按层次顺序(同一层自左至右)遍历二叉树的算法。
要求实现下列函数：
void LevelOrder(BiTree bt, char *ss);
/* travel BiTree bt by level, Return result by ss. */
二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);
提示：可将遍历元素的值（字符）依次置入ss，并最后以’\0′结尾。
也可以用下列字符串函数产生ss：
int sprintf(char *buffer, char *format [, argument, ...]);
char *strcat(char *dest, char *src);
/* travel BiTree bt by level, Return result by ss. */
{
int i=0;
Queue Q;
BiTree p;
InitQueue(Q);
if(bt){
EnQueue(Q,bt);
while(!QueueEmpty(Q)){
DeQueue(Q,p);
ss[i++]=p->data;
if(p->lchild){
EnQueue(Q,p->lchild);
}
if(p->rchild){
EnQueue(Q,p->rchild);
}
}
ss[i]='\0';
}
}
6.49④ 编写算法判别给定二叉树是否为完全二叉树。
要求实现下列函数：
Status CompleteBiTree(BiTree bt);
/* judge if the binary tree whose root is bt */
/* is a complete tree. */
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);
/* judge if the binary tree whose root is bt */
/* is a complete tree. */
/*基本思路
使用一个栈记录按层次遍历结果，当该结点非NULL时，左右子树入栈
因此，如果该树为完全二叉树时栈内容为XXXX＃＃(X表示非空)，##之间不可能有非空结点
如果非完全二叉树则内容可能为XXX＃XX＃＃也就是在NULL结点间仍有非空结点
只要非空结点与空结点分布情况即可求解
*/
{
int flag=0,top=0;
BiTree stack[100];
Queue Q;
BiTree p;
InitQueue(Q);
if(bt){
EnQueue(Q,bt);
while(!QueueEmpty(Q)){
DeQueue(Q,p);
if(p){
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
stack[top++]=p->lchild;
stack[top++]=p->rchild;
}
}//while
while(top){
if(flag){
if(stack[--top]==NULL){//在非NULL结点前仍有NULL结点
return FALSE;
}
}
else{
if(stack[--top]!=NULL){//遇到第一个非NULL结点
flag=1;
}
}
}
}//if
return TRUE;
}
6.65④ 已知一棵二叉树的前序序列和中序序列分别
存于两个一维数组中，试编写算法建立该二叉树的二
叉链表。
要求实现以下函数：
void BuildBiTree(BiTree &bt, int ps, char *pre,
int is, char *ino, int n);
/* 当前要建立的子树bt的元素总数为n，*/
/* 元素在前序序列pre的起始位置为ps，*/
/* 元素在中序序列ino的起始位置为is */
二叉链表类型定义：
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
int is, char *ino, int n)
/* 当前要建立的子树bt的元素总数为n，*/
/* 元素在前序序列pre的起始位置为ps，*/
/* 元素在中序序列ino的起始位置为is */
{
//估计此题比较繁琐，待更新
}