摘要:目录树形结构概念了解概念重要树的表示形式树的应用二叉树重点概念二叉树的种基本形态两种特殊的二叉树斜树满二叉树完全二叉树二叉树的性质第层结点个数树的所有最大点个数叶子结点和非叶子结点数量关系根据结点求树深度父子结点编号关系小
树不再是顺序表, 链表, 栈, 队列那样一对一的线性结构. 而树则是一种一对多的数据结构, 由n(n>=0)个互不相交有限节点组层有层次关系的集合.
特点如下:
正确的树:
用的是上图中正确的二叉树来解释概念
节点的度: 一个节点含有的子树的个数称为该节点的度[A的度就是2]
非终端节点或分支节点:度不为0的节点[A, B, C, D, E]
树的度: 一棵树中,最大的节点的度称为树的度; 如上图:树的度为3
叶子节点或终端节点: 度为0的节点称为叶节点; 如上图:G、H、I、J节点为叶节点
双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
兄弟节点: 具有相同父节点的节点互称为兄弟节点[B和C, E和F, G, H和I]
堂兄弟节点: 双亲在同一层的节点互称为堂兄弟节点[D和E, D和F]
节点的祖先: 从根到该节点的所有分支经历所有节点[A]
根结点: 一棵树中,没有双亲结点的结点;如上图:A
森林: 由m(m>=0)棵互不相交的树的集合称为森林
节点的层次: 从根开始定义起,根为第1层,根的子节点为第2层,以此类推
树的高度或深度: 树中节点的最大层次; 如上图:树的高度为4
线性结构 | 树结构 |
---|---|
第一个元素: 无前驱 | 根节点: 无双亲 |
最后一个元素: 无后继 | 叶节点: 无后继, 可多个 |
中间元素: 一个前驱一个后继 | 中间节点: 一个双亲, 多个孩子 |
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法、孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法【在线OJ常考的就是这种表示形式】
class Node { int value;// 树中存储的数据 Node child;// 第一个孩子引用 Node brother;// 下一个兄弟引用}
文件系统管理(目录和文件)
我们从经典的猜数字游戏开始, 由浅入深介绍二叉树.
在100以内猜数字, 最多几次可以猜对呢?答案是:7
下面是根据每次猜的大小来构建二叉树
我们发现利用这个大小关系来查找指定范围内某个数字, 效率不是高的一丁半点. 因此对于这种具有对立关系的情况: 0和1, 真与假, 上与下, 正与反, 对与错都适合用树来建模. 这种特殊的树状结构称为二叉树
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
特点:
- 每个节点最多有2颗子树, 即不存在度大于2的节点
- 二叉树有左右子树之分, 次序不能颠倒, 因此二叉树也是一颗有序树
顾名思义, 斜树一定要是斜的, 往哪儿斜也是有讲究的.所有的节点都只有左子树叫做左斜树; 所有的节点都只有右子树叫做右斜树
左斜树:
右斜树:
斜树有明显特点: 每一层都只有一个节点, 结点个数和树的深度相同.
有些同学就奇怪了: 这也能叫树吗, 这不是我们熟悉的线性表吗?
解释: 对的, 线性表结构可以理解为树的一种极其特殊的表现形式
在一棵二叉树中, 如果所有分支结点都存在左子树和右子树, 并且所有叶子节点都在同一层上, 这样的二叉树称为满二叉树
它的样子看得很美, 很匀称
满二叉树特点:
- 叶子结点只能出现在最下一层, 出现在其它层就不可能达到平衡
- 非叶子结点的度一定是2, 否贼就是"缺胳膊少腿"
- 在同样深度的二叉树中, 满二叉树结点个数最多, 叶子结点最多
把一颗具有 n 个节点的二叉树按层序编号, 编号i(<1=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中所在位置完全相同
这是一种有些难以理解的特殊二叉树
首先从字面上理解区分, "满"和"完全"的差异: 满二叉树一定是一颗完全二叉树, 但是完全二叉树不一定是一颗满二叉树
什么是按层序编号?
上图中就是按照从上到下, 从左到右一次按照1, 2, 3, …, n的序号
完全二叉树特点:
- 叶子结点只能出现在最下两层
- 最下层的叶子结点一定集中在左部连续位置
- 倒数第二层, 如果有叶子结点, 一定都在右部连续位置
- 如果结点的度为1, 则该节点只有左孩子, 即不存在只有右子树的情况
- 同样结点数的二叉树, 完全二叉树的深度最小
从上面的列子中, 也给了我们一个判断某二叉树是否为完全二叉树的办法: 看着二叉树的示意图, 心中默默给每个节点按照满二叉树的结构逐层顺序编号, 如果编号出现了空档, 就说明不是完全二叉树否则就是完全二叉树
若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i-1)(i>0)个结点
若规定根节点的层数为1,则深度为K的二叉树最大节点数是 2^k-1(k>0)个结点
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1[最下一层的叶子结点个数=上面的所有非叶子结点个数+1]
具有n个节点的二叉树的深度K为log2^(n+1)向上取整
对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i 的结点有:
设一棵完全二叉树中总共有1000个节点, 则该二叉树中 500 个叶子节点, 500个非叶子节点, 1个节点只有左孩子, 0个只有右孩子.
500个叶子结点计算步骤
有了这个理解后再做进一步的计算
现在我们还差第9层的叶子结点个数
最后的问题就是求第10层父节点个数
将一颗有 100 个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根节点编号为 1 ,则编号为 98 的节点的父节点编号为: (98-1)/2 = 48
设非空二叉树的所有子树中,其左子树上的结点值均小于根结点值,而右子树上的结点值均不小于根结点值,则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是: 中序遍历
将一棵二叉树的根结点放入队列,然后递归的执行如下操作,将出队结点所有子结点加入队。以上操作可以实现层序遍历.
n个节点的完全二叉树,最多可以有多少层: log(n+1)上取整
二叉树的顺序存储就使用一维数组存储二叉树中的节点并且存储的位置应该要能体现节点之间的逻辑关系, 比如孩子双亲, 左右兄弟节点
将这颗二叉树存储数组中, 相应的下标对应其相等的位置
这下看出完全二叉树的优越性了吧, 由于它定义的严格, 所以顺序结构也能表现出二叉树的结构来
对于一般二叉树而言, 层序编号不能反映逻辑关系, 但是可以按照完全二叉树编号, 只不过把不存在的结点设施为 ‘^’ 而已.浅色节点代表不存在
考虑一下极端情况: 又斜树【左斜树】
一颗深度为 k 的右斜树, 只有 k 个节点, 却需要分配 2^k-1 个存储单元, 这显然是对存储空间的浪费. 所以顺序存储只适用于完全二叉树
既然顺序存储适应性不强, 我们就要考虑链式存储结构. 二叉树每个节点最多有两个孩子, 所以设计一个数据域和两个指针域比较理想. 这就是二叉链表
孩子表示法
class Node { int val;// 数据域 Node left;// 左孩子的引用,常常代表左孩子为根的整棵左子树 Node right;// 右孩子的引用,常常代表右孩子为根的整棵右子树}
孩子双亲表示法主要用在在平衡树,本文采用孩子表示法来构建二叉树, 大多数的在线OJ题目也都采用的这种方法来构建二叉树.
导言: 假设有20张100元的和2000张1元的奖券, 同时撒向了空中, 大家比赛看谁最中间的最多.
相信同学都会说: 先捡100元的. 道理非常简单, 因为捡1张100元的等于捡100张1元的, 效率好的不是一点点?.
所以得出这样的结论: 同样是捡奖券, 在有限时间内, 要达到最高效率, 次序非常重要. 对于二叉树的遍历来讲, 次序同样显得也很重要.
二叉树的遍历(traversing binary tree): 是指从根结点出发, 按照某种次序依次访问二叉树中的所有节点, 使得每一个节点被访问一次且仅仅被访问一次
这里有两个关键词: 依次和访问. 不同于线性结构, 最多也就是从头至尾, 循环, 双向等简单的遍历方式. 树的节点之间不存在唯一的前驱和后继关系, 在访问一个节点后, 下一个被访问的节点面临着不同的选择. 就像你人生的道路上, 高考填报志愿要面临哪个城市, 哪所大学, 具体专业等. 选择方式不同, 遍历的次序就完全不同
假设我们有以下一颗二叉树T, 用链表结构存储
OJ题目链接
递归前序遍历
private static void preOrderTraversal(BinaryTreeNode root) { if (root == null) { return; } else { System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); }}private static List<String> preOrderTraversal(BinaryTreeNode root) { List<String> result = new ArrayList<>(); if (root == null) { return result; } else { result.add(root.val); result.addAll(preOrderTraversal(root.left)); result.addAll(preOrderTraversal(root.right)); return result; }}A B D H K E C F I G J
演示递归前序遍历步骤
preOrderTraversal(BinaryTreeNode root)
, root 根节点不为空, 所以执行 System.out.print(root.val + " ");
打印字母 ApreOrderTraversal(root.left)
, 访问了A 节点的左孩子, 不为 null, 执行 System.out.print(root.val + " ");
打印字母 BpreOrderTraversal(root.left)
, 访问了B 节点的左孩子, 不为 null, 执行 System.out.print(root.val + " ");
打印字母 DpreOrderTraversal(root.left)
, 访问了D 节点的左孩子, 不为 null, 执行 System.out.print(root.val + " ");
打印字母 HpreOrderTraversal(root.left)
, 访问H 节点的左孩子, 此时因为 H 节点无左孩子, 所以 root == null
返回此函, 此时递归调用 preOrderTraversal(root.right);
访问了 H 节点的右孩子, 执行 System.out.print(root.val + " ");
打印字母 KpreOrderTraversal(root.left)
, 访问 K 节点的左孩子, 返回preOrderTraversal(root.right)
, 访问了 K 节点的右孩子, 也是 null, 返回.于是函数执行完毕.preOrderTraversal(root.ri ght)
访问 D 节点的右孩子, 不存在preOrderTraversal(root.right)
, 访问 B 节点的右孩子, 打印字母 EpreOrderTraversal(root)
, 调用 preOrderTraversal(root.right)
, 访问 A 节点的右孩子, 打印字母 C知道了递归的代码如何运行, 那我们再看看非递归实现前序遍历
/*非递归1.先创建一个栈2.根节点放进栈里3.循环取栈顶元素4.出栈并访问这个元素值域5.把当前元素的右子树入栈, 再左子树入栈【因为先打印左子树后打印右子树所以对于栈而言应该先入右子树再入左子树】*/private static void preOrderTraversalNo(BinaryTreeNode root) { if (root == null) { return; } else { Stack<BinaryTreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()) { BinaryTreeNode top = stack.pop(); System.out.print(top.val + " "); if (top.right != null) { stack.push(top.right); } if (top.left != null) { stack.push(top.left); } } }}A B D H K E C F I G J
演示迭代前序遍历步骤
非递归思路很巧妙的利用了栈的先进后出特性进行前序遍历
OJ题目链接
递归中序遍历
private static void inOrderTraversal(BinaryTreeNode root) { if (root == null) { return; } else { preOrder(root.left); System.out.print(root.val + " "); preOrder(root.right); }}H K D B E A I F C G J
演示递归中序遍历步骤
inOrderTraversal(BinaryTreeNode root)
, root 的根节点 A 不为 null, 于是调用 inOrderTraversal(root.left)
, 访问节点 B; B 不为空, 继续调用inOrderTraversal(root.left)
, 访问节点 D; D 不为空, 继续调用inOrderTraversal(root.left)
, 访问节点 H; H 不为空, 继续调用 inOrderTraversal(root.left)
, 访问节点 H的左孩子; 为空, 返回. 打印当前节点 HinOrderTraversal(root.right)
, 访问 H 节点的右节点 K.因为 K 无左孩子, 所以打印 KinOrderTraversal(root.right)
, 访问 B 节点的右节点 E, 因为 E 没有左孩子, 所以打印 EinOrderTraversal(root)
的地方, 打印字母 AinOrderTraversal(root.right)
, 访问 A 节点的右孩子C,再递归访问 C 的左孩子 F, F 的左孩子 I, 因为 I 无右孩子, 所以打印 I. 之后分别打印 F, C, G, J迭代中序遍历
/*1.先创建一个栈2.根节点入栈3.循环取栈顶元素4.左子树 集体入栈后再入右子树5.最外层 while 循环判断需要留意.因为 cur= cur.right 会导致 cur == nulll, 因此在加入一个 !stack.empty() 的判断*/private static void inOrderTraversalNo(BinaryTreeNode root) { if (root == null) { return; } else { Stack<BinaryTreeNode> stack = new Stack<>(); BinaryTreeNode cur = root; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); System.out.print(cur.val + " "); cur = cur.right; } }}H K D B E A I F C G J
演示迭代中序遍历步骤
OJ题目链接
递归后序遍历
/*OJ: 通过*/class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { if(root == null){ return list; }else{ postorderTraversal(root.left); postorderTraversal(root.right); list.add(root.val); return list; } }}
private static void postOrderTraversal(BinaryTreeNode root) { if (root == null) { return; } else { postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.print(root.val + " "); }}
演示递归后序遍历步骤
System.out.print(root.val + " ");
, 打印 H 节点迭代后序遍历
/*和中序遍历类似1.外层循环依旧需要加上 !stack.empty()来带动循环2.被打印完的节点置为 null, 并且判断该节点是否被打印过3.判断超时*/private static void postOrderTraversalNo(BinaryTreeNode root) { if (root == null) { return; } else { Stack<BinaryTreeNode> stack = new Stack<>(
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/124467.html
摘要:并且,我们的底层都是红黑树来实现的。红黑树是一种平衡二叉树因此它没有节点。 前言 声明,本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合: Collection总览 List集合就这么简单【源码剖析】 原本我是打算继续将Collection下的Set集合的,结果看了源码发现:Set集合实际上就是HashMap来构建的! showImg(https:/...
前言 只有光头才能变强。 文本已收录至我的GitHub仓库,欢迎Star:https://github.com/ZhongFuCheng3y/3y 一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习).... 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于线性的数据结构(链表、数组)而言,树的平均运行时间更短(往往与树相关的排序时间复杂度都...
前言 声明,本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树的基础了: Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍 本篇主要讲解HashMap,以及涉及到一些与hashtable的比较~ 看这篇文章之前最好是有点数据结构的基础: Java实现单向链表 栈和队列就是这么简单 二叉树就...
摘要:源码剖析由于红黑树的操作我这里不说了,所以这里基本上也就没什么源码可以讲了,因为这里面重要的算法都是,这里的是指,他们是算法导论的作者,也就是说里面算法都是参照算法导论的伪代码。因为红黑树是平衡的二叉搜索树,所以其包含操作的时间复杂度都为。 本文章首发于个人博客,鉴于sf博客样式具有赏心悦目的美感,遂发表于此,供大家学习、批评。本文还在不断更新中,最新版可移至个人博客。? 继上篇文章...
摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
阅读 1614·2021-11-23 09:51
阅读 2890·2021-09-24 10:26
阅读 2704·2021-09-23 11:54
阅读 2832·2021-09-23 11:21
阅读 4131·2021-09-22 15:33
阅读 2115·2021-09-09 09:33
阅读 1438·2021-09-07 10:10
阅读 793·2019-08-30 11:09