首页 > 代码库 > 树结构

树结构

二叉树:二叉树是每个节点最多有两个子树的树结构。

满二叉树:一棵深度为K且有2^k-1个结点的二叉树称为满二叉树。

完全二叉树:每个结点与其对应深度的满二叉树一一对应。

二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树: 
A. 左子树若不为空,则左子树上所有节点的值均小于它的根结点值; 
B. 右它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 
C. 它的左、右子树也分别是二叉排序树;

平衡二叉树:又称AVL树,或者是一棵空树,或者是具有下列性质的二叉树: 
A. 它的左右子树都是平衡二叉树,且左右子树深度差不超过1;

红黑树:自平衡二叉查找树,典型的用途是实现关联数组。它的特性保证了,最长路径长度不会是最短路径长度的2倍。 
特性: 
1. 节点是红色或黑色。 
2. 根节点是黑色。 
3. 每个叶节点(NIL节点,空节点)是黑色的。 
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

Trie树:字符索引,字典树 
桶状哈希表与直接定址表 
Trie树详解及其应用 
字典树(Trie树)的C程序实现代码 
Trie树的常见应用大总结(面试+附代码实现)

B-树:又称B树,B-树是一种平衡的多路查找树(查找均满足左小右大的条件),它在文件系统中很有用。 
一棵m阶的B-树,或为空树,或为满足下列特性的m叉树: 
A. 树中每个结点至多有m棵子树; 
B. 若根结点不为叶子结点,则至少有两棵子树; 
C. 除根之外的所有非终端结点至少有[ m/2 ]棵子树; 
D. 所有非终结点包含这样的信息:(n, A0, K1, A1, K2, A2, … Kn, An..);  代码有n个key,n+1个指针指向子树;
E. 所有叶子结点都出现在同一层次上,表示为空。

技术分享

 

B+树:B+树是应文件系统所需而出的一种B-树的变形树,一棵m阶的B+树和m阶的B-树差异在于: 
A: 有n个关键字的结点拥有n棵子树。(B-树中n个关键字有n+1棵子树); 
C: 非终节点关键字可看作是索引部分,是对应子树中关键字的最大或最小值; 
B: 所有的叶子结点中包含了全部关键字信息,及指向这些关键字记录的指针,且叶子结点中关键字按从小到大链接;

技术分享

 

 

最优二叉树(赫夫曼树): 
解决了带权值的的最短花费问题。 
赫夫曼编码(前缀编码):编码对象长度不一样,实现最短编码方案。原理是保证了每一种对象编码都不会是其它对象编码的前缀。

技术分享 技术分享

 

树的遍历方式: 
树:树先根遍历、后根遍历 
例:(先)A B C D E、(后)B D C E A 
____A 
B___C___E 
____D

森林:先序、中序(其实就是每棵树的后根遍历)

二叉树:先、中、后序

树结构