没有合适的资源?快使用搜索试试~ 我知道了~
数据结构中二叉树各种题型详解及程序.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 168 浏览量
2021-12-07
17:15:57
上传
评论
收藏 174KB DOCX 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/57844672/0001-d1832f2e6255c72dd407bb4ff613600c_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
14页
数据结构中二叉树各种题型详解及程序.docx
资源推荐
资源详情
资源评论
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![exe](https://img-home.csdnimg.cn/images/20210720083343.png)
![](https://csdnimg.cn/release/download_crawler_static/57844672/bg1.jpg)
1. int GetNodeNum(BinaryTreeNode * pRoot)
2. {
3. if(pRoot == NULL) // 递归出口
4. return 0;
5. return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
6. }
树是一种比较重要的数据构造,尤其是二叉树。二叉树是一种特别的树,在二叉树中每个节点最多有两个
子节点,一般称为左子节点和右子节点〔或左孩子和右孩子〕,并且二叉树的子树有左右之分,其次序不
能任意颠倒。二叉树是递归定义的,因此,与二叉树有关的题目根本都可以用递归思想解决,固然有些题
目非递归解法也应当把握,如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结,
期望对找工作的同学有所挂念。
二叉树节点定义如下:
structBinaryTreeNode
{
intm_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
相关链接:
轻松搞定面试中的链表题目
题目列表:
1. 求二叉树中的节点个数
2.
求二叉树的深度
3.
前序遍历,中序遍历,后序遍历
4.
分层遍历二叉树〔按层次从上往下,从左往右〕
5.
将二叉查找树变为有序的双向链表
6.
求二叉树第 K 层的节点个数
7.
求二叉树中叶子节点的个数
8.
推断两棵二叉树是否构造一样
9.
推断二叉树是不是平衡二叉树
10.
求二叉树的镜像
11.
求二叉树中两个节点的最低公共祖先节点
12.
求二叉树中节点的最大距离
13.
由前序遍历序列和中序遍历序列重建二叉树
14.
推断二叉树是不是完全二叉树
具体解答
1.
求二叉树中的节点个数
递归解法:
〔1〕假设二叉树为空,节点个数为 0
〔2〕假设二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
参考代码如下:
轻松搞定面试中的二叉树题目
![](https://csdnimg.cn/release/download_crawler_static/57844672/bg2.jpg)
1. int GetDepth(BinaryTreeNode * pRoot)
2. {
3. if(pRoot == NULL) // 递归出口
4. return 0;
5. int depthLeft = GetDepth(pRoot->m_pLeft);
6. int depthRight = GetDepth(pRoot->m_pRight);
7. return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
8. }
3. 前序遍历,中序遍历,后序遍历
前序遍历递归解法:
(1) 假设二叉树为空,空操作
(2) 假设二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树
参考代码如下:
1. void PreOrderTraverse(BinaryTreeNode * pRoot)
2. {
3. if(pRoot == NULL)
4. return;
5. Visit(pRoot); // 访问根节点
6. PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树
7. PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树
8. }
中序遍历递归解法
(1) 假设二叉树为空,空操作。
(2) 假设二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树
参考代码如下:
1. void InOrderTraverse(BinaryTreeNode * pRoot)
2. {
3. if(pRoot == NULL)
4. return;
5. InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树
6. Visit(pRoot); // 访问根节点
7. InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树
8. }
2. 求二叉树的深度
递归解法:
〔1〕假设
二叉树
为空,二叉树的深度为 0
〔2〕假设二叉树不为空,二叉树的深度 = max(左子树深度,右子树深度) + 1
参考代码如下:
![](https://csdnimg.cn/release/download_crawler_static/57844672/bg3.jpg)
1. void PostOrderTraverse(BinaryTreeNode * pRoot)
2. {
3. if(pRoot == NULL)
4. return;
5. PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树
6. PostOrderTraverse(pRoot->m_pRight); // 后序遍历右子树
7. Visit(pRoot); // 访问根节点
8. }
4.分层遍历二叉树〔按层次从上往下,从左往右〕
相当于广度优先搜寻,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进展如下操作:
弹出一个节点,访问,假设左子节点或右子节点不为空,将其压入队列。
1. void LevelTraverse(BinaryTreeNode * pRoot)
2. {
3. if(pRoot == NULL)
4. return;
5. queue<BinaryTreeNode *> q;
6. q.push(pRoot);
7. while(!q.empty())
8. {
9. BinaryTreeNode * pNode = q.front();
10. q.pop();
11. Visit(pNode); // 访问节点
12. if(pNode->m_pLeft != NULL)
13. q.push(pNode->m_pLeft);
14. if(pNode->m_pRight != NULL)
15. q.push(pNode->m_pRight);
16. }
17. return;
18. }
后序遍历递归解法
(1) 假设二叉树为空,空操作
(2) 假设二叉树不为空,后序遍历左子树,后序遍历右子树,访问根节点
参考代码如下:
剩余13页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/1b8528961b9a43fcbc3ccec9e4b60bc3_hc1018520482.jpg!1)
奔跑的朱亚文
- 粉丝: 0
- 资源: 4万+
![benefits](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-2.ec46750a.png)
C知道特权
![article](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![course-privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![rights](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)