企业官网建设流程全解析

三、树与二叉树

1、树

1.定义：树的定义是递归，它表明了树本身的固有特性，也就是一棵树由若干子树构成，而子树又由更小的子树构成

2.概念：根节点、叶子节点，父子节点，兄弟节点（同一层次的节点），节点度（某一节点子树的个数），树度（对于整棵树而言，各节点度的最大值），分支节点（非终端节点，度不为0的节点），层次（根为第一层，以此类推），树的高度（最大层次树）

2、二叉树

（1）：定义

二叉树是n（n >= 0）个节点的有限集合，空树n为0，或是由一根节点及两颗不相交的切分别左右对称的二叉子树所构成，具有递归性。树度与节点度都为2

n个节点的二叉树，高度最高为n，最低为log2n+1（log2n表示n是2的多少次幂）

设：二叉树的节点个数为7，其树高度最高为7（单支树），高度最低为log2^7+1即(2^2

（2）：存储

)1.数组顺序存储

补充成满二叉树后，存储在数组中，根据节点编号，即可还原成树

)2.链式存储

1.二叉链式存储：结构：左节点指针、值与编号、右节点指针

当二叉树有k个节点时，节点中必定有k+1个空子节点指针

2.三叉链式存储：结构：左节点指针、值与编号、右节点指针、父节点编号

（3）：特性

)1.节点

在二叉树的第i层上（i>=1），最少有1个节点，最多有2^(i-1)个节点

)2.高度

高度为k的二叉树（k>=1），最多有2^k-1个节点

)3.编号

如果对一棵有n个节点的完全二叉树编号，从第1层到log2n+1层，每层从左到右（1

1.如果i=1，则i无父节点，是二叉树的根

2.如果i>1，则父节点是 i/2（除不通则向下取整）

3.如果2i>n，则其节点为叶子节点，无左子节点

4.如果2i

5.如果2i+1>n，则其节点为叶子节点，无右子节点

6.如果2i+1

)4.形态数

递增公式：A[n] = ∑m=0,m

1.0个节点的二叉树形态只有一种：空树

2.1个节点的二叉树形态只有一种：单节点树

3.2个节点的二叉树形态：套入公式 A[2] = ∑m=0,m

快速计算：

4.3个节点的二叉树形态：套入公式 A[3] = ∑m=0,m

快速计算：

5.4个节点的二叉树形态：套入公式 A[4] = ∑m=0,m

快速计算：

A[0]有1种形态，A[1]有1种形态，A[2]有2种形态，A[3]有5种形态

)5.分支（枝丫）数

对任何一颗二叉树，如果其叶子节点数为n0（度为0），度为2的节点树为n2，则n0=n2+1

1.一棵树，从根向叶子伸展，根据度的定义：节点（不包含根节点）数为k，则伸展枝丫数为k

枝丫数：n0*0+n1*1+n2*2+···+nk*k

2.一棵树，从叶子向根回溯，根据父子关系：每个节点都会通过1根枝丫，与其父节点连接，除了根节点

枝丫数：节点总数-1=(n0+n1+n2+···+nk)-1

3.二叉树：度为2，(n0+n1+n2)-1 = n0*0+n1*1+n2*2 等同于 n0=n2+1

设：已知树T的度为4，度为4的节点数有7个，度为3的节点数有5个，度为2的节点数有8个，度为1的节点数有10个

求节点总数：套入伸展公式：n0*0+n1*1+n2*2+···+nk*k = 1*10+2*8+3*5+4*7 = 10+16+15+28 = 69

求叶子节点数（度为0）：套入叶子回溯公式：节点总数-1=(n0+n1+n2+···+nk)-1 = 69=(n0+10+8+5+7)-1 = n0=69-(10+8+5+7)+1 = n0=40

（4）：遍历

)1.遍历方式

1.前序遍历：递归遍历，遍历顺序 根 =》左子树 =》右子树

遍历结果：1，2，4，5，7，8，3，6

2.中序遍历：递归遍历，遍历顺序 左子树 =》根 =》右子树

遍历结果：4，2，7，8，5，1，3，6

3.后序遍历：递归遍历，遍历顺序 左子树 =》右子树 =》根

遍历结果：4，8，7，5，2，6，3，1

4.层次遍历：逐层遍历

遍历结果：1，2，3，4，5，6，7，8

)2.反向构造

方法：

第一步：先根据前序和中序，将根区分出来，并划分左右子树

第二步：再根据子树将新的根划分出来，直至还原

设：前序序列：ABHFDECG，中序序列：HBEDFAGC，推算还原二叉树

思路：

1.通过前序得出A为根

2.已知A为根，通过中序得出HBEDF为左子树，GC为右子树

3.已知HBEDF为左子树，通过前序ABHFDECG得出B为左子树根节点

4.已知B为左子树根节点，通过中序HBEDFAGC得出H在B之前并且H是中序中第一个节点，说明H在B左侧并且H下再没有子树

5.已知H为B的左子树，并且EDF非H下子树，通过前序得出ABHFDECG，F为B的右子树

6.已知DE为F下的子树，通过中序HBEDFAGC得出，F为最后，说明ED并非F的右子树，E在D前表示E为D的左子树，并通过前序ABHFDECG可验证左子树是否准确

7.已知A为根节点，BHFDE为左子树，通过前序ABHFDECG得出C为根节点

8.已知C为根节点，通过中序HBEDFAGC得出：G为C的左子树

（5）：排序

左子树小于根，右子树大于根，第一个值为根

从左到右排列同一个层次的节点，其关键字呈现有序排列的特点

最大高度值n

最小高度值（满二叉树）[log2n]+1

设：待排序序列：{89, 48, 112, 20, 56, 51}

)1.查找节点

查找关键字：左子树小于根，右子树大于根

如查找关键字56，小于根节点89得出在左侧 =》小于左子树根节点48得出在右侧，得出结果

)2.插入节点

1.若该键值节点已存在，则不再插入

2.若查找二叉树为空树，则以新节点为查找二叉树（单节点树）

3.将要插入节点键值与插入后父节点键值比较，就能确定新节点是父节点的左子节点还是右子节点

)3.删除节点

1.若待删除节点是叶子节点，则直接删除

2.若待删除节点只有一个叶子节点，则将这个子节点与待删除节点的父节点直接连接

3.若待删除的节点右两个子节点，则在其左子树上，用中序遍历寻找关键值最大节点，并用此节点代替待删除节点

（6）：最优二叉树（哈夫曼树）

二叉树代价最小的形态（可以存在多种，只要代价最小即可）

权值越大离根节点越近

哈夫曼树中不存在只有一个子树的节点

哈夫曼树中的节点总数一定为奇数

权值相同的节点到树根的路径长度不一定相同

)1.概念

1.树路径长度：叶子节点到根的枝丫树

2.权（权值）：节点当中的数值

3.带权路径长度：权值*树路径长度

4.树带权路径的长度（代价）：所有叶子节点带权路径的长度

5.最优二叉树：代价最小

其中：设叶子节点‘3’树路径长度为3，节点当中数值为权值，权值为3的带权路径长度（3*3）为9，树带权路径长度（代价）为4*2+3*3+6*2=29

其中：设叶子节点‘3’树路径长度为2，节点当中数值为权值，权值为3的带权路径长度（3*2）为6，树带权路径长度（代价）为4*2+6*3+3*2=35

综上两图相比：图1比图2代价更小，所以图1为最优二叉树

)2：降低二叉树代价

权值最大的节点，放置根节点

权值最小的节点，放置离根最远的节点

设叶子节点序列{1，2，4，8}，最优二叉树表现为：

>例题：叶子节点序列为：5，29，7，8，14，23，3，11，求最优二叉树

解：思路：

1.先将叶子节点序列排序为：3，5，7，8，11，14，23，29

2.先取最小两节点开始拼接，完成后得出子节点序列为：3，5，7，8，11，14，23，29 ==》7，8，8，11，14，23，29

3.7，8，8，11，14，23，29 ==》8，11，14，15，23，29

4.14，15，19，23，29 ==》19，23，29，29

5.19，23，29，29 ==》29，29，42

6.29，29，42 ==》42，58

7.得出根节点：58，42 ==》100

8.拼接所有子树到根节点下，得出

)3：哈夫曼编码

变长、压缩编码

设：某文档5个字符，每个字符出现的频率为下表，并在哈夫曼树中右侧节点表示1，左侧节点表示0

则求得最优二叉树结果为：

根据表格进行转换，替换当中的数字为字母得出：

已知此哈夫曼树右侧节点表示1，左侧节点表示0，则可以得出：

根据上述分析：得出结论：a=0，b=100，c=111，d=110，e=101

定长：a的长度为1位，b/c/d/e的长度均为3位，则平均定长为3

变长：a的长度为40%（使用频率）*1（定长）= 0.4，b~e定长都为3，60%（b~e的使用频率总和为）*3（定长）=1.8，平均变长为 0.4+1.8 = 2.2

压缩比例：（3-2.2）/3 ≈ 0.27 = 27%

（7）：特殊的二叉树

)1：平衡二叉树

平衡因子：右侧高度 - 左侧高度

任意节点左右子树的深度相差不超过1

每个节点的平衡因子只能是1，0，-1

)2：线索二叉树

遍历：利用填补空节点，指向遍历的前驱和后继