网站开发进程报告,品牌网站建设四川,代理公司注册手续,文字图片制作器理解树的结构-算法通关村 1.树的结构
树是一个有n个有限节点组成一个具有层次关系的集合#xff0c;每个节点有0个或者多个子节点#xff0c;没有父节点的节点称为根节点#xff0c;也就是说除了根节点以外每个节点都有父节点#xff0c;并且有且只有一个。树的种类比较多…理解树的结构-算法通关村 1.树的结构
树是一个有n个有限节点组成一个具有层次关系的集合每个节点有0个或者多个子节点没有父节点的节点称为根节点也就是说除了根节点以外每个节点都有父节点并且有且只有一个。树的种类比较多最常见的是二又树基本结构如下参考上面的结构可以很方便的理解树的如下概念 节点的度一个节点含有的子节点的个数称为该节点的度树的度一棵树中最大的节点的度称为树的度注意与节点度的区别叶节点或终端节点度为0的节点称为叶节点非终端节点或分支节点度不为0的节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点兄弟节点具有相同父节点的节点互称为兄弟节点节点的祖先从根到该节点所经分支上的所有节点子孙以某节点为根的子树中任一节点都称为该节点的子孙。森林由mm0棵互不相交的树的集合称为森林无序树树中任意节点的子节点之间没有顺序关系这种树称为无序树也称为自由树有序树树中任意节点的子节点之间有顺序关系这种树称为有序树二叉树每个节点最多含有两个子树的树称为二叉树 2 树的性质
性质1在二叉树的第i层上至多有2^i-1个结点i0 性质2深度为k的二叉树至多有2^k -1个结点k0 性质3对于任意一棵二叉树如果其叶结点数为N0而度数为2的结点总数为N2则N0N21 性质4具有n个结点的完全二叉树的深度必为 log2n1 性质5对完全二叉树若从上至下、从左至右编号则编号为i的结点其左孩子编号必为2i其右孩子编号必为2i1其双亲的编号必为i/2i1 时为根除外满二叉树就是如果一棵二叉树只有度为0的节点和度为2的节点并且度为0的节点在同一层上则这棵二叉树为满二叉树。这棵二又树为满二叉树也可以说深度为k4有2^k-115个节点的二又树。完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大 值并且最下面一层的节点都集中在该层最左边的若干位置。 3 树的定义 定义二叉树 public class TreeNode {int val;TreeNode left;TreeNode right;}定义N叉树 public class Node {public int val;public ListNode children;}4树的遍历方式
二叉树的遍历方式有层次遍历和深度优先遍历两种 • 深度优先遍历先往深走遇到叶子节点再往回走。 •广度优先遍历一层一层的去遍历一层访问完再访问下一层。 这两种遍历方式不仅仅是二叉树N树叉也有这两种方式的图结构也有只不过我们更习惯叫广度优先和深度优先本质是一回事。 深度优先又有前中后序三种记住一点前指的是中间的父节点在遍历中的顺序只要大家记住前中后序指的就是父节点在访问中的顺序就可以了。 前序遍历中左右 中序遍历左中右 后序遍历左右中 5 通过序列构造二叉树
前面我们已经介绍了前中后序遍历的基本过程现在我们看一下如何通过给出的序列来恢复原始二叉树看三个序列 1前序1 2 3 4 5 6 8 7 9 10 11 12 13 15 14 2中序3 4 8 6 7 5 2 1 10 9 11 15 13 14 12 3 后序8 7 6 5 4 3 2 10 15 14 13 12 11 9 1
5.1前中序列复原二叉树 先看如何通过前中序列复原二叉树 1前序1 2 3 4 5 6 8 7 9 10 11 12 13 15 14 2中序3 4 8 6 7 5 2 1 10 9 11 15 13 14 12 第一轮 我们知道前序第一个访问的就是根节点所以根节点就是1。 中序遍历的特点是根节点的左子树的元素都在根节点的左侧右子树的元素都在根节点的右侧从中序遍历序列我们可以划分成如下结构 前序中序划分中序序列划分[3 4 8 6 7 5 2 ] 1 [10 9 11 15 13 14 12]前序序列划分1 [2 3 4 5 6 8 7] [9 10 11 12 13 15 14] 上面前序序列第一个括号里的都是左子树的元素第二个括号一定都是右子树的元素。参照中序的两个数组划分的。我们看到前序中7之前的元素都在中序第一个数组中9之后的所有元素就在第二个数组种所以我们从7和9之间划分。 由此画图表示一下此时知道的树的结构为 第二轮 我们先看两个序列的第一个数组 前序2 3 4 5 6 8 7 中序3 4 8 6 7 5 2 此时又可以利用上面的结论划分了根节点是2然后根据2在中序中的位置可以划分为 序列前序 2 [3 4 5 6 8 7]中序[3 4 8 6 7 5 ] 2 此时树的结构为 第三轮 对 3 4 5 6 8 7 继续划分 前序3 [4 5 6 8 7] 中序3 [ 4 8 6 7 5 ] 此时结构为 第四轮 对 4 5 6 8 7 继续划分前序 4 [5 6 8 7 ] 中序4 [8 6 7 5 ] 第五轮 对 5 6 8 7 继续划分前序5 [6 8 7 ] 中序[8 6 7] 5 同理对序列 [10 9 11 15 13 14 12]进行划分 5.2 通过中序和后序序列恢复二叉树
通过中序和后序也能恢复原始序列的唯一的不同是后序序列的最后一个是根节点中序的处理也是上面一样的过程 前序12345687910 1112 1315 14 中序 3486752110911 15 13 14 12 后序876543210 15 14 13 12 1191 可以自行试一试不再赘述。 问题为什么前序和后序不能恢复二叉树 既然上面两种都行那为什么前序和后序不行呢我们看上面的例子 1 前序 123456879 10 1112 13 15 14 2 后序87654321015 141312 1191 后序876543210 15 14 13 12 1191 可以自行试一试不再赘述。 问题为什么前序和后序不能恢复二叉树 既然上面两种都行那为什么前序和后序不行呢我们看上面的例子 1 前序 123456879 10 1112 13 15 14 2 后序87654321015 141312 1191根据上面的说明我们通过前序可以知道根节点是1通过后序也能知道根节点是1但是中间是怎么划分的呢其他元素哪些属于左子树哪些属于右子树呢很明显通过两个序列都不知道所以前序和后序序列不能恢复二叉树。
