【原】数据结构——二叉树的原理与代码应用

文章目录

简介

二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念，不再赘述。
二叉树分类

1、完全二叉树

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。

2、满二叉树

国际标准定义是除了叶结点外每一个结点都有左右子结点的二叉树
在这里插入图片描述
国内的定义是：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。很显然，按照这个定义，上面的图示二叉树就不是满二叉树。

3、扩充二叉树

扩充二叉树是对已有二叉树的扩充，扩充后的二叉树的节点都变为度数为2的分支节点。也就是说，如果原节点的度数为2，则不变，度数为1，则增加一个分支，度数为0的叶子节点则增加两个分支。

4、平衡二叉树

是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1
在这里插入图片描述
二叉树的应用场景
普通的二叉树，很难构成现实的应用场景，但因其简单，常用于学习研究，平衡二叉树则是实际应用比较多的。常见于快速匹配、搜索等方面。
常用的树有：AVL树、红黑树、B+树、Trie（字典）树。

1、AVL树:

最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

2、红黑树:

平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的。还有Linux文件管理。

3、B/B+树:

用在磁盘文件组织 数据索引和数据库索引。

4、Trie树(字典树):

用在统计和排序大量字符串，如自动机、M数据库索引。

二叉树的构建

0、遍历方式

前序遍历：root -> left -> right
中序遍历：left -> root -> right
后续遍历：left ->right -> root
层序遍历：按照层次遍历