大家好，今天来为大家分享深入浅出：数据结构与算法之树篇（第五部分）的一些知识点，和的问题解析，大家要是都明白，那么可以忽略，如果不太清楚的话可以看看本篇文章，相信很大概率可以解决您的问题，接下来我们就一起来看看吧！
普通树 斜树（左斜树、右斜树）
树1 二叉树（BinaryTree） 满二叉树：树深度log(n+1)
完全二叉树（重要）：树深度[logn]+1
.
森林树2
.
本质：是一对多的数据结构
(1)结点分类
结点的度：一个节点拥有的子树数量称为该节点的度。
度数为叶结点：的节点称为叶节点。
分支结点（非终端节点、内部节点） :个度不为0的节点
树的度：是指树中每个节点的度的最大值，称为树的度。
(2)结点的关系
子节点：节点的子树的根称为该节点的子节点。
父节点：该节点称为其子节点的父节点。
(3)结点的层次（这个层次的概念是针对结点而言的）
从根的定义开始，根为第一级，根的子级为第二级。
(4)树的深度(高度)
树中节点的最大层数称为树的深度。显然，这个节点一定是树的根节点。
注意：树的深度和树的度是不同的概念
(5)有序树和无序树
如果树中节点的子树从左到右（或从右到左）排序并且不能互换，则该树称为有序树，否则为无序树。
(6)森林
是一组m(m=0)个不相交的树
2.树的存储结构
不再可以简单地使用以前的顺序存储和链式存储。介绍了三种存储方式：父表示、子表示、子兄弟表示。
(1)双亲表示法(以父结点的角度)
使用一组连续的空间来存储树的节点，同时为每个节点附加一个指示器，以指示父节点在数组中的位置。
数据 父级
"节点描述"
公共类PNode{
公共int 父级； //父节点的位置
公共T 数据； //数据字段
}
(2)孩子表示法(以孩子结点的角度)
对每个节点的子节点进行排列，使用单向链表作为存储结构。那么n个节点有n个子链表。如果是叶子节点，则单向链表为空，然后n个头指针组成线性表，线性表采用顺序存储结构，存储在一维数组中。
1 A -1 -2
2B-3
3 -4 -5
4 维-6 -7 -8
5E-9
6 F 为此使用两个节点结构：
(1) 头节点
数据第一个孩子
(2) 子节点
儿童下一个
优点：查找某个节点的兄弟很方便，遍历相关节点的子链表即可。遍历整棵树也很方便。只需循环并输出整个头节点数组即可。
#######(3)子兄弟表示（以节点的兄弟为角度）
优点是它把复杂树变成了二叉树
数据firstchildrightchild
‘代码说明’
(1)树的节点描述
公共类树节点{
公共TreeNodelChild; //左孩子
公共TreeNodeChild; //右孩子
私有T数据； //数据字段
//节点初始化
公共树节点（）{
数据=空；
lChild=null；
rChild=null;
}
公共TreeNode(T x) {
数据=x；
lChild=null；
rChild=null;
}
}"树的数据类型定义"
公共类树{
//其他一些操作
.
}
3.二叉树(Binary Tree)
是一种特殊的树。 （普通树可以与二叉树相互转换）
定义：它是n（n=0）个节点的有限集合。该集合要么是空集（称为空二叉树），要么具有一个根节点和两个不相交的左树，每个树都是根节点。由子树和右子树组成的二叉树。
(1)二叉树的特点
1) 由于每个节点最多有两个子树，因此二叉树中不存在度大于2的节点；也从侧面证明二叉树的度=2
2）左子树和右子树是有序的，不能颠倒。
3）即使二叉树中的一个节点只有一颗子树，也需要区分它是左子树还是右子树。
(2)特殊的二叉树
斜树：所有节点都只有左子树或只有右子树。它们分别称为左偏树和右偏树。
满二叉树(有2个条件)：所有分支节点都有左子树和右子树，所有叶子节点都在同一级。
**满二叉树：的特点**
叶节点只能出现在最低层。非叶子节点的度均为2。在相同深度的二叉树中，满二叉树的节点数最多，叶子节点的最大数量为完全二叉树：。如果编号为i(1=i=如果节点n)在二叉树中的位置与相同深度的满二叉树中编号为i的节点完全相同，则称为完全二叉树。
完全二叉树的特点：1) 树号为连续
2）叶子节点只能出现在最下两层3）最低的叶子节点必须集中在左边连续的位置
(3)二叉树的性质(理解记忆)
1) 二叉树第i 层最多有2^(i-1) 个节点
2) 深度为k 的二叉树最多有2^k-1 个节点(k=1)
注：当为满二叉树的时候，结点个数为：2^k-13) 对于任意二叉树T，若终端节点（即叶子节点）个数为n0，度为2的节点个数为n2，则n0=n2+1；
4）n个节点的满二叉树的深度为： ** log(n+1)**
5）n个节点的完全二叉树的深度为： ** [logn]+1**
注意：这是完全二叉树，而不是完全二叉树
推导过程：
由于深度为k的满二叉树的节点数：n=2^k-1
因此，深度为k的完全二叉树的节点数满足：
2^(k-1)-1 n=2^k-1
由于n 是整数，因此
——2^(k-1) - 1 n 2^k
——2^(k-1)=n 2^k
—— k-1 logn=k
由于k是整数——k=[logn]+16）如果有一棵有n个节点的完全二叉树（很容易知道它的深度为[logn]+1），它的节点是按层编号的（从第1层开始）到[ logn]+1) 层，从左到右），对于任意节点i (i=i=n)：
) i=1，则i为根节点，没有父节点。若为i1，则其父节点编号为：[i/2]
）如果为2in，则节点i没有左子节点（并且i是叶子节点）；否则其左孩子编号：2i
) 如果2i+1n，则没有右孩子；否则右孩子的数量：2i+1
(4)二叉树的存储
的存储方式和普通树的存储方式还是有很大区别的，尤其是可以实现顺序存储。
1)顺序存储结构
使用一维数组来存储二叉树中的节点，节点的存储位置可以体现每个节点之间的逻辑关系。 （这与普通树木不同）
对于“完全二叉树”：
A B C D E F G
对于‘普通二叉树’，可以存储为完全二叉树，只需设置没有节点的位置。对于“^”
A B C ^ E ^ G
对于‘倾斜二叉树’来说，有点浪费空间。因此，这种顺序存储结构比较适合‘完全二叉树’
2)链式存储结构
由于二叉树的每个节点最多有2个子节点，因此其节点可以设计为以下形式：
lChild 数据 rChild
"代码说明"
公共类BinTreNode{
T数据； //数据字段
BinTreNodelChild; //左子节点指针
BinTreNodeChild; //右子节点指针
公共BinTreNode() {
this.data=null;
this.lChild=null;
this.rChild=null;
}
公共BinTreNode(T x) {
这个.data=x;
this.lChild=null;
this.rChild=null;
}
}注意：如果想方便地找到某个节点的父节点，只需像普通树中一样添加一个指向其父节点parent的指针字段即可：
lChild数据rChild父
(5)遍历二叉树(Traversing binary Tree)
含义：表示从根节点开始，按照一定的“顺序”进行“访问” 全部二叉树的节点仅被访问一次。
二叉树的遍历不同于线性数据结构：由于线性数据结构中的节点具有唯一的前驱或后继节点，这使得遍历结果唯一确定；
然而，在二叉树中（普通树也是如此），每个节点的后继节点不是唯一的，有多种选择，所以选择
不同，遍历的结果也会不同。
二叉树：
一个
公元前
DEF
G H I
二叉树常见的遍历方式：
1)前序遍历： ABDGHCEIF规则：如果二叉树为空，则遍历结果返回空。否则请先访问根结点、左子树、右子树。
2)中序遍历： GDHBAEICF规则：如果二叉树为空，则遍历结果返回空。否则，先从根节点开始（不访问根节点），按中序遍历根节点左子树、根结点、右子树3)后序遍历： GHDBIEFCA规则：如果二叉树为空，则遍历结果返回空。否则，先从根节点开始（不访问根节点），后序遍历根节点的左子树、右子树、根结点。
4)层序遍历(层次遍历)：ABCDEFGHI规则：如果二叉树为空，则遍历结果返回空。否则，从树的根节点开始遍历，从上到下，逐层遍历访问。
**注： **
1、前、中、后遍历方式都是针对‘根节点’
2.为什么要研究遍历？由于计算机只能处理线性序列，因此我们需要研究如何将树等非线性序列转换为线性序列。
3、知道前序遍历序列和中序遍历序列，就可以唯一确定一棵二叉树
给定后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
然而，给定前序和后序遍历序列，无法唯一确定二叉树。
“遍历代码描述”：使用递归轻松完成
/**
* 二叉树遍历方法
*/
//先序遍历
公共无效预订单（BinaTreNodenode）{
if (节点==null) {
返回；
}
//打印根节点
System.out.print(node.data);
preOrder(node.lChild);
preOrder(node.rChild);
}
//中序遍历
公共无效inOrder（BinaTreNodenode）{
if (节点==null) {
返回；
}
inOrder(node.lChild);
//打印根节点
System.out.print(node.data);
inOrder(node.rChild);
}
//后序遍历
公共无效postOrder（BinaTreNodenode）{
if (节点==null) {
返回；
}
postOrder(node.lChild);
postOrder(node.rChild);
//打印根节点
System.out.print(node.data);
}
//层序遍历：使用队列实现层序遍历
公共无效levelOrder（）{
BinaTreNode[] 队列=new BinaTreNode[this.maxNodes];
int 前面=-1; //队列头指针
int 后=0; //队列尾指针
if (this.root==null) {
返回；
}
queue[rear]=this.root;//二叉树的根节点进入队列
//如果队伍不为空，则继续遍历
while(后！=前) {
前面++；
//打印根节点
System.out.print(queue[front].data);
//将队伍第一个节点的左孩子添加到队伍中
if (队列[front].lChild !=null) {
后方++；
队列[后]=队列[前].lChild;
}
//将队头的右孩子也添加到队伍中
if (队列[front].rChild !=null) {
后方++；
队列[后]=队列[前].rChild;
}
}
}
4.线索二叉树(Thread BinaryTree)
如果我们能够知道二叉树中每个节点的直接前驱节点或后继节点是谁，将会给二叉树的其他操作带来方便。然而，二叉树存储节点时，并不能体现每个节点的直接前驱节点或后继节点是谁。该信息只能在某种二叉树遍历过程中动态获得。
一棵有n个节点的二叉树，其二叉链表存储共有2n个指针域（每个节点有两个左右子指针域），以及n-1条分支线（即两个节点之间的连接线），因此，还有2n-(n-1)=n+1个指针字段为空，被浪费而未被利用。因此，请考虑使用这些空闲指针字段：
利用节点空闲的左指针域(lChild)来存储该节点在一定遍历下的直接前驱节点
利用节点空闲的右指针域(rChild)来存储该节点在一定遍历下的直接后继节点
我们把这个指向前驱和后继的指针称为线程，添加了线程的二叉树称为线程二叉树。
线索二叉树的节点结构：
ltag lChild 数据 rChild rtag
ltag，rtal 是两个标志位（每个仅占用1位空间）用于指示lChild和rChild是否代表左（右）子节点或前驱（后继）节点。
0, 表示左子指针ltag=
1, 代表前驱节点指针
0, 表示右子指针rtag=
1, 代表后继节点指针
由于线索二叉树的遍历顺序不同，得到的线索二叉树也不同：
先序线索二叉树
有序线索二叉树
后序线索二叉树
"节点代码说明"
/**
* 线索二叉树的节点
* @author 管理员
*
*/
公共类ThreadedTreNode{
公共T 数据； //数据字段
公共ThreadedTreNodelChild； //左指针域
公共ThreadedTreNoderChild； //右指针域
//左标志位，这里写成boolean类型，方便后续代码
公共布尔ltag； //true表示前驱节点指针
//右边标志位写成boolean类型，方便后续代码。
公共布尔rtag； //true表示后续节点指针
公共ThreadedTreNode() {
数据=空；
lChild=null；
rChild=null;
ltag=假； //默认表示左右孩子
rtag=假；
}
公共ThreadedTreNode(T x) {
数据=x；
lChild=null；
rChild=null;
ltag=假；
rtag=假；
}
}"线索二叉树代码说明"
/**
* 线索二叉树
* @author 管理员
*
*/
公共类ThreadedTree{
/**
* 添加头节点只是为了方便操作。
* 其结构与其他线索二叉树的节点结构相同，只是数据域不存储信息。
* 左指针指向二叉树的根节点，右指针指向其自身。
* 原二叉树在一定遍历下的第一个节点的前驱线索和最后一个节点的后继线索
* 全部指向头节点
*/
私有ThreadedTreNodehead； //
私有ThreadedTreNodepre； //表示刚刚访问过的节点
//创建包含头节点的线索二叉树
公共线程树（）{
this.head=new ThreadedTreNode();
}
/**
* 通过中序遍历的顺序线索二叉树
* @返回
*/
公共布尔startInThreading（）{
如果（头==空）{
返回假；
}
//设置头节点为头节点，其左子节点指向根节点
head.ltag=false;
head.rtag=true;
head.rChild=头； //头节点的右指针指向自身。
if(head.lChild==null) {
//如果二叉树为空，则左指针指向自身
head.lChild=头；
} 别的{
//pre总是指向刚刚访问过的节点。
前=头； //设置默认前驱节点
inThreading(头); //通过中序遍历进行中序线程
//获取最后一个节点
pre.rChild=头；
pre.rtag=true;
}
返回真；
}
//按顺序完成二叉树线程
私有无效inThreading（ThreadedTreNodep）{
//p表示指向当前节点
如果（p==null）{
返回；
}
inThreading(p.lChild); //左子树线索
if(p.lChild==null) {
//表示当前节点没有左子节点（左指针字段为空），因此，该节点有前驱节点。
//此时，它的前驱节点pre 刚刚被访问过
//线索
p.ltag=true; //表示左指针是前驱节点指针
p.lChild=pre;
}
//由于此时节点p的后继节点还没有被访问，所以我们只能判断其前驱节点pre的右指针。
if(pre.rChild==null) {
//表示p是pre的后继者
pre.rtag=t
rue; pre.rChild = p; } pre = p; //保持 pre 指向 p 的前驱 inThreading(p.rChild); //右子树线索化 } //遍历二叉线索树 public void traversing() { ThreadedTreNodenode = head.lChild; if(node == null) { return; } while(!node.ltag) { //寻找中序序列的首结点 node = node.lChild; do { if (node != null) { System.out.println(node.data); node = searchPostNode(node); } } while (node.rChild != head); } } /** * 寻找中序的后继结点 * @param node * @return */ public ThreadedTreNodesearchPostNode(ThreadedTreNodenode) { ThreadedTreNodeq = node.rChild; if (!node.rtag) { while(!q.rtag) { q = q.lChild; } } return q; } /** * 寻找中序的前继结点 * @param node * @return */ public ThreadedTreNodesearchPreNode(ThreadedTreNodenode) { ThreadedTreNodeq = node.lChild; if (!node.ltag) { while(!q.ltag) { q = q.rChild; } } return q; } }5.普通树、森林、二叉树之间的转换
(1)转换1)树 ——>二叉树 步骤：1) 在所有的兄弟之间加一条连线 2) 对树中每一个结点，只保留它与第一个孩子的连线，删除与其他孩子的连线 3) 层次调整。简单的理解：想像用手捏住根结点往起来一提溜，靠重力下垂， 便可得到调整后的层次 2)森林 ——>二叉树 步骤：1) 把每个树转换为二叉树 2) 第一个二叉树不动，从第二棵开始，依次把后一棵二叉树的根结点作为前一棵根结点的右孩子 3)二叉树 ——>树 是上面树到二叉树的逆过程 4)二叉树 ——>森林 如果这棵二叉树有右孩子，那么该二叉树就能转换为森林是上面森林到二叉树的逆过程(2)树与森林的遍历1)树的遍历 先根遍历 (类似先序遍历) 后跟遍历 (类似后跟遍历) 2)森林遍历 前序遍历(先访问第一棵树，每棵树内用先根遍历) 后序遍历(先访问第一棵树，每棵树内用后跟遍历) 注意：森林的前序遍历和二叉树的前序遍历结果相同 森林的后序遍历和二叉树的中序遍历结果相同 因此，当以二叉链表来存储树时，其先根遍历和后根遍历算法完全同二叉树的前序遍历和后序遍历 这样就可以将树和森林这种复杂问题进行简单处理6.二叉树的应用：Huffman树与Huffman编码
(1)几个概念：1)路径长度：从树中一个结点到另一个结点之间的分支(其实就是结点之间的连线)构成两个结点之间的路径，而把这条路径上的的分支(即连线)数目(之和)称做路径长度。注意："路径长度" 是针对任意两个结点间而言的2)树的路径长度：指从树根到每一个结点的路径长度之和(对就是字面意思) 3)结点的带权路径长度：该结点到树根结点之间的路径长度与该结点上权值的乘积 4)树的带权路径(WPL)：树中所有叶子结点的带权路径之和 WPL = ∑ W(k)*L(K) 其中，W(k)为叶子结点的权值，L(k)为叶子结点的路径长度5)Huffman树：把WPL最小的二叉树称为Huffman树(2)如何构造Huffman树 ?
根据Huffman树的定义知：要想使WPL最小，必须是权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。基本思想如下：ⅰ)把所有包含权值的数据元素(w1, w2, ..., wn)看成离散的叶子结点，并组成"结点集合": F={w1, w2, ..., wn} ⅱ)从集合中选取权值最小的和次小的两个叶子结点作为左右子树构造成一棵新的二叉树，则该二叉树的根结点(记为，R(i)，i表示第i个合成的根结点 )的权值为其左右子树根结点的权值之和 ⅲ)从结点集合中剔除刚选取过的作为左右子树的那两个叶子结点，并将新构建的二叉树的根结点(为R(i) )加入到结点集合中。 ⅳ)重复(ⅱ)(ⅲ)两步，当集合中只剩下一个结点时，该结点就是所建立的Huffman树的根结点，该二叉树便为Huffman树注意：对于一组给定的叶子结点所组成的Huffman树，其树形可能不相同，但其WPL一定是相等的，且为最小(3)Huffman编码
Huffman树最早是用于优化电文编码的。减小电文编码长度，节约存储或传输成本。 如：A B C D E F (字符，即叶子结点) 27 8 15 15 30 5 (字符出现的频率或权值) 构造Huffman树 将Huffman树的左分支代表0,右分支代表1 则，相应的Huffman编码： A B C D E F 01 1001 101 00 11 1000 ○ ╱ ╲ ╱ ╲ (42) (58) ╱ ╲ ╱ ╲ D(15) A(27) (28) E(30) ╱ ╲ (13) C(15) ╱ ╲深入浅出：数据结构与算法之树篇（第五部分）的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于、深入浅出：数据结构与算法之树篇（第五部分）的信息别忘了在本站进行查找哦。
【深入浅出：数据结构与算法之树篇（第五部分）】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
好久没接触树这种数据结构了，感觉要好好复习一下。
有20位网友表示赞同！
学习树的关键在于理解各种遍历方式吧！
有7位网友表示赞同！
想明白了二叉查找树，其他的树就更容易了。
有8位网友表示赞同！
这期视频讲啥树？是二叉树吗？我期待着学习新的知识点。
有19位网友表示赞同！
数据结构和算法的重中之重，对编程真的很重要！
有5位网友表示赞同！
树这种结构真是挺巧妙的，比线性结构更能体现层次关系。
有9位网友表示赞同！
希望这次课能够讲解明白红黑树和AVL树呀！
有10位网友表示赞同！
数据结构是打好编程基础的关键一步，学习起来还是很重要的!
有7位网友表示赞同！
视频讲得是不是很清晰呢？可以看下评论区听听其他人的感受。
有12位网友表示赞同！
感觉算法的实现跟树这种数据结构有很大的关系哦。
有8位网友表示赞同！
要好好理解树的性质和特性，才能灵活地运用。
有17位网友表示赞同！
学习数据结构和算法真的很有挑战！
有17位网友表示赞同！
学习树会让我更深入地理解代码背后的逻辑吧？
有15位网友表示赞同！
期待看到课程内容能帮助我更好地解决实际问题！
有7位网友表示赞同！
什么时候才能真正掌握这些知识呢？希望多加练习!
有17位网友表示赞同！
数据结构就像搭建建筑的框架，算法则是施工的方式。
有19位网友表示赞同！
学习完树这种数据结构，对其他数据结构的理解也会更深吧？
有18位网友表示赞同！
树结构在实际应用中比想象中用的更多！
有10位网友表示赞同！
要好好总结笔记，记录下各种树的定义和特点哦。
有12位网友表示赞同！
感觉学习数据结构很有趣，可以学到很多实用的知识！
有6位网友表示赞同！