树的概念
在计算机科学中，树是⽤来模拟具有树状结构性质的数据集合。它是由n（n>=0）个有限节点组成⼀个具有层次关系的集合。把它叫 做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。(n = 0 时称为空树)
中国统计年鉴2008树的结构特点
树的结构图:
特点有:
每个节点有零个或多个⼦节点；
没有⽗节点的节点称为根节点；
每⼀个⾮根节点有且只有⼀个⽗节点；
除了根节点外，每个⼦节点可以分为多个不相交的⼦树；
树的分类
⼆叉树：每个节点最多含有两个⼦树的树称为⼆叉树；
阿米什人
完全⼆叉树：对于⼀颗⼆叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数⽬均已达最⼤值，且第d层所有节点从左向右连续地紧密排列，这样的⼆叉树被称为完全⼆叉树；
满⼆叉树：所有叶节点都在最底层的完全⼆叉树；
平衡⼆叉树（AVL树）：当且仅当任何节点的两棵⼦树的⾼度差不⼤于1的⼆叉树；
红⿊树: 是⼀种⾃平衡⼆叉查树，它是在1972年由鲁道夫·贝尔发明的，他称之为”对称⼆叉B树”
排序⼆叉树(⼆叉查树)：也称⼆叉搜索树、有序⼆叉树；
霍夫曼树：带权路径最短的⼆叉树称为哈夫曼树或最优⼆叉树；
B树：⼀种对读写操作进⾏优化的⾃平衡的⼆叉查树，能够保持数据有序，拥有多于两个⼦树。
具体树的详解
⼀. ⼆叉树
1.1 ⼆叉树的储存
假设为链式储存, 结点类声明为:
public class TreeNode {
public int val;
石英玻璃public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}工业奈
遍历⽅式分为
递归遍历
⾮递归遍历
遍历顺序分为:
1.3 ⼆叉树的性质
⼆叉树的第层⾄多拥有个节点数, >=1)
深度为 的⼆叉树⾄多总共有 个节点数,(>=1)
对任何⼀棵⾮空的⼆叉树，如果其叶⽚(终端节点)数为 ，分⽀度为的节点数为 ，则第三点推导过程:
: 总度数
: 总结点数
:
度为0的结点
: 度为1的结点(只有⼀个孩⼦的结点)商业地产运营模式
: 度为2的结点(有左右两个孩⼦)
推出
1.4 ⼆叉树其他考点
已知前序中序遍历结果, 求后序遍历结果
已知后序中序遍历结果, 求前序遍历结果
步骤:
1. 得到每棵⼦树的根节点(前序: 第⼀个数; 后序: 最后⼀个数)
2. 根据该根节点在中序遍历中的位置, 划分根节点的左右⼦树
3. 重复步骤1, 直到全部划分完毕
注意:
前序或后序遍历结果决定每⼀棵⼦树根节点
中序遍历结果决定⼦节点是属于左⼦树还是右⼦树
⼆. 完全⼆叉树
2.1 结构及特点
结构图
特点
你问我答2
⽽在⼀棵⼆叉树中，除最后⼀层外，若其余层都是满的，并且最后⼀层或者是满的，或者是在右边缺少连续若⼲节点，则此⼆叉树为完全⼆叉树（Complete Binary Tree）。具有个节点的完全⼆叉树的深度为 。深度为的完全⼆叉树，⾄少有个节点，⾄多有 个节点。
2.2 完全⼆叉树应⽤
堆结构
堆排序
2.3 堆的应⽤
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议