数据结构第5章课后习题答案(下)

简介: 数据结构第5章课后习题答案(下)

3.算法设计

以二叉链表作为二叉树的存储结构,编写以下算法:

(1)统计二叉树的叶结点个数。

[题目分析]如果二叉树为空,返回0,如果二叉树不为空且左右子树为空,返回1,如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数。

[算法描述]

int LeafNodeCount(BiTree T)

{

if(T==NULL)

   return 0; //如果是空树,则叶子结点个数为0

else if(T->lchild==NULL&&T->rchild==NULL)

   return 1; //判断结点是否是叶子结点(左孩子右孩子都为空),若是则返回1

else

   return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);

}

(2)判别两棵树是否相等。

[题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的左右孩子是否相等。

[算法描述]

int compareTree(TreeNode* tree1, TreeNode* tree2)

//用分治的方法做,比较当前根,然后比较左子树和右子树

{bool tree1IsNull = (tree1==NULL);

bool tree2IsNull = (tree2==NULL);

if(tree1IsNull != tree2IsNull)

{

return 1;

}

if(tree1IsNull && tree2IsNull)

{//如果两个都是NULL,则相等

return 0;

}//如果根节点不相等,直接返回不相等,否则的话,看看他们孩子相等不相等

if(tree1->c != tree2->c)

{

 return 1;

}

return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))

(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left));

}//算法结束

3交换二叉树每个结点的左孩子和右孩子。

[题目分析]如果某结点左右子树为空,返回,否则交换该结点左右孩子,然后递归交换左右子树。

[算法描述]

void ChangeLR(BiTree &T)

{

BiTree temp;

if(T->lchild==NULL&&T->rchild==NULL)

        return;

else

{

        temp = T->lchild;

        T->lchild = T->rchild;

        T->rchild = temp;

}//交换左右孩子

ChangeLR(T->lchild);  //递归交换左子树

ChangeLR(T->rchild);  //递归交换右子树

}

4设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。

[题目分析]若树为空,返回;若某结点为叶子结点,则仅输出该结点;否则先输出该结点,递归遍历其左子树,再输出该结点,递归遍历其右子树。

[算法描述]

void DoubleTraverse(BiTree T)

{

if(T == NULL)

   return;

else if(T->lchild==NULL&&T->rchild==NULL)

   cout<<T->data;     //叶子结点输出

else

{

   cout<<T->data;

   DoubleTraverse(T->lchild);   //递归遍历左子树

   cout<<T->data;

   DoubleTraverse(T->rchild);   //递归遍历右子树

}

}

5计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。

[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。

[算法描述]

int Width(BiTree bt)//求二叉树bt的最大宽度

{if (bt==null) return (0);  //空二叉树宽度为0

else

{BiTree Q[];//Q是队列,元素为二叉树结点指针,容量足够大

front=1;rear=1;last=1;

//front队头指针,rear队尾指针,last同层最右结点在队列中的位置

temp=0; maxw=0;       //temp记局部宽度, maxw记最大宽度

Q[rear]=bt;           //根结点入队列

while(front<=last)

   {p=Q[front++]; temp++; //同层元素数加1

if (p->lchild!=null)  Q[++rear]=p->lchild;   //左子女入队

if (p->rchild!=null)  Q[++rear]=p->rchild;   //右子女入队

if (front>last)      //一层结束,

       {last=rear;

if(temp>maxw) maxw=temp;

//last指向下层最右元素, 更新当前最大宽度

        temp=0;

}//if  

}//while

return (maxw);

}//结束width

6用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。

[题目分析]

若某个结点左子树空右子树非空或者右子树空左子树非空,则该结点为度为1的结点

[算法描述]

int Level(BiTree bt) //层次遍历二叉树,并统计度为1的结点的个数

{int num=0; //num统计度为1的结点的个数

if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q); cout<<p->data;     //出队,访问结点

if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;

//度为1的结点

if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队

if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队

} // while(!QueueEmpty(Q))

}//if(bt)        

return(num);

}//返回度为1的结点的个数

7求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。

[题目分析]因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。

[算法描述]

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=bt,l[],s[];

//l, s是栈,元素是二叉树结点指针,l中保留当前最长路径中的结点

int i,top=0,tag[],longest=0;

while(p || top>0)

{while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向下

if(tag[top]==1)    //当前结点的右分枝已遍历

{if(!s[top]->Lc && !s[top]->Rc)  //只有到叶子结点时,才查看路径长度

if(top>longest)

{for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈,记住最高栈顶指针,退栈

}

else if(top>0) {tag[top]=1; p=s[top].Rc;}   //沿右子分枝向下

}//while(p!=null||top>0)

}//结束LongestPath

8输出二叉树中从每个叶子结点到根结点的路径。

[题目分析]采用先序遍历的递归方法,当找到叶子结点*b时,由于*b叶子结点尚未添加到path中,因此在输出路径时还需输出b->data值。

[算法描述]

void AllPath(BTNode *b,ElemType path[],int pathlen)

{int i;

if (b!=NULL)

{if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点

{cout << " " << b->data << "到根结点路径:" << b->data;

     for (i=pathlen-1;i>=0;i--)

     cout << endl;

}

   else

    {path[pathlen]=b->data;           //将当前结点放入路径中

     pathlen++;                     //路径长度增1

     AllPath(b->lchild,path,pathlen);   //递归扫描左子树

     AllPath(b->rchild,path,pathlen);   //递归扫描右子树

     pathlen--;                     //恢复环境

    }

 }// if (b!=NULL)

}//算法结束

目录
相关文章
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
43 2
|
6月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
79 1
|
6月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
48 1
|
6月前
|
机器学习/深度学习
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
数据结构学习记录——堆的小习题(对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的)
42 1
|
6月前
|
算法
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
39 0
|
6月前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
38 0
|
6月前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
38 0
|
6月前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
36 0