这是我见过的最全的介绍二叉树的文章

这是我见过的最全的介绍二叉树的文章二叉树的种类 4 种 满二叉树 完全二叉树 二叉搜索树 平衡二叉搜索树 1 满二叉树如果一棵二叉树只有度为 0 的节点和度为 2 的节点 并且度为 0 的节点在同一层上 则这棵二叉树为满二叉树 这棵二叉树的深度为 k 从 1 开始计算 有 2k 1 个节点

欢迎大家来到IT世界,在知识的湖畔探索吧!

二叉树的种类

(4种:满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树

1.满二叉树

如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。

这是我见过的最全的介绍二叉树的文章

这棵二叉树的深度为k(从1开始计算),有2k-1个节点。

2.完全二叉树

完全二叉树:除了底层节点可能没填满,其余每层的节点数都达到最大值,并且底层的节点都集中在该层最左边的若干位置。若底层为第h层,则该层包含1~2h-1个节点。

一个典型的完全二叉树的例子如下图所示。

这是我见过的最全的介绍二叉树的文章

注意,最后一棵二叉树不是完全二叉树。

3.二叉搜索树

前面介绍的二叉树中的节点都没有数值,而二叉搜索树是有数值的。二叉搜索树是一个有序树,满足如下规则:

  • 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值。
  • 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值。
  • 它的左、右子树也分别为二叉排序树。

下面这两棵树都是二叉搜索树。

这是我见过的最全的介绍二叉树的文章

4.平衡二叉搜索树

平衡二叉搜索树又称为AVL(Adelson-Velsky and Landis)树,它是一棵空树,或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

这是我见过的最全的介绍二叉树的文章

最后一棵二叉树不是平衡二叉树,因为它的左右两个子树的高度差的绝对值超过了1。

C++中map、set、multimap、multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作的时间复杂度是O(logn),而unordered_map、unordered_set、unordered_map、unordered_map的底层实现是哈希表。

在使用自己熟悉的编程语言实现算法时,一定要知道常用的容器底层都是如何实现的,最基本的就是map、set等,否则很难分析自己写的代码的性能。

遍历方式

二叉树主要有两种遍历方式:

(1)深度优先遍历:先往深处遍历,遇到叶子节点时再往回遍历。

(2)广度优先遍历:一层一层地遍历。

以上是图论中最基本的两种遍历方式,将深度优先遍历和广度优先遍历进一步拓展,有如下遍历方式:

  • 深度优先遍历

— 前序遍历(递归法、迭代法)。

— 中序遍历(递归法、迭代法)。

— 后序遍历(递归法、迭代法)。

  • 广度优先遍历

— 层次遍历(迭代法)。

在深度优先遍历中,前、中、后指的就是中间节点的遍历顺序,只要记住前序、中序、后序指的是中间节点的位置即可。

通过如下中间节点的顺序就可以发现,中间节点的顺序就是所谓的遍历方式:

  • 前序遍历:中→左→右。
  • 中序遍历:左→中→右。
  • 后序遍历:左→右→中。

下面看一下自己理解的前序、中序、后序有没有问题。

这是我见过的最全的介绍二叉树的文章

下面确定递归算法的三个要素。每次写递归算法时都基于下面的“三部曲”,可以写出正确的递归算法。

(1)确定递归函数的参数和返回值。

确定哪些参数在递归过程中需要处理就在递归函数中加上这些参数,并且明确每次递归的返回值是什么,进而确定递归函数的返回类型。

(2)确定终止条件。

写完递归算法,程序运行的时候经常会遇到栈溢出的错误,原因是没写终止条件或者终止条件写得不对。操作系统也是用一个栈的结构保存每一层递归的信息的,如果递归没有终止,那么操作系统的内存栈必然会溢出。

(3)确定单层递归的逻辑。

确定每一层递归需要处理的信息。在这里会重复调用函数本身来实现递归的过程。

下面以前序遍历为例。

(1)确定递归函数的参数和返回值。

因为要打印出前序遍历节点的数值,所以参数中需要传入数组(C++中使用vector)来存放节点的数值,除了这一点,就不需要再处理其他数据了,也不需要有返回值,所以递归函数的返回类型就是void,代码如下:

void traversal(TreeNode* cur, vector<int>& vec)

欢迎大家来到IT世界,在知识的湖畔探索吧!

(2)确定终止条件。

在递归的过程中,如何确定递归结束了呢?当当前遍历到的节点为空时,说明本层递归就要结束了。如果当前遍历的这个节点为空,则直接返回,代码如下:

欢迎大家来到IT世界,在知识的湖畔探索吧!if (cur == NULL) return;

(3)确定单层递归的逻辑。

前序遍历是中→左→右的顺序,所以单层递归的逻辑就是先取中节点的数值,再处理左子树和右子树,代码如下:

vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右

完整代码如下:

欢迎大家来到IT世界,在知识的湖畔探索吧!class Solution { public: void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; traversal(root, result); return result; } };

中序和后序遍历的代码如下:

// 中序遍历 void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; traversal(cur->left, vec); // 左 vec.push_back(cur->val); // 中 traversal(cur->right, vec); // 右 } // 后序遍历 void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 vec.push_back(cur->val); // 中 }

好啦,二叉树暂时就学到这里了。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/89009.html

(0)
上一篇 2024年 11月 19日 下午12:00
下一篇 2024年 11月 19日 下午12:45

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信