目录

开头说点题外话，在帅张星球上看到一个提问（下图），觉得帅张回答的很中肯很在理。论一个男生上进心的重要性，不上进找不到女朋友啊，当然了不要以为上进了就能找到女朋友！管他什么女朋友，我的心里只有学习！继续我们的数据结构学习之旅，这一次我们学习的是树。

树的定义

树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。

在任意一颗非空树中：

(1)有且仅有一个特定的称为根（Root）的结点。

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、.....、Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

下图就符合树的定义：

其中根结点A有两个子树：

需要注意的是虽然子树的个数没有限制，但是它们一定是互不交互的。下面的图明显不符合互不交互的原则，所以不是树。

树的结点

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。树的度是树内各结点度的最大值。

结点的层次从根开始定义起，根为第一层，根的孩子为第二层，以此类推。树的深度（Depth）或高度是树中结点的最大层次。

树的存储结构

二叉树

二叉树的定义

二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成（子树也为二叉树）。

二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树五种基本形态

1. 空二叉树
2. 只有一个根结点
3. 根结点只有左子树
4. 根结点只有右子树
5. 根结点既有左子树又有右子树

几种特殊的二叉树

斜树

左斜树：右斜树：

满二叉树

满二叉树：

完全二叉树

完全二叉树：

二叉树的性质

二叉树性质1

性质1：在二叉树的第i层上至多有2^i-1个结点（i>=1）

二叉树性质2

性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）

二叉树性质3

性质3：对任何一棵二叉树T，如果其终端结点数为n₀,度为2的结点数为n₂，则n₀ = n₂+1。

一棵二叉树，除了终端结点（叶子结点），就是度为1或2的结点。假设n₁度为1的结点数，则数T 的结点总数n=n₀+n₁+n₂。我们再换个角度，看一下树T的连接线数，由于根结点只有分支出去，没有分支进入，所以连接线数为结点总数减去1。也就是n-1=n₁+2n₂，可推导出n₀+n₁+n₂-1 = n₁+2n₂，继续推导可得n₀ = n₂+1。

二叉树性质4

性质4：具有n个结点的完全二叉树的深度为[log₂n ] + 1([X]表示不大于X的最大整数)。

由性质2可知，满二叉树的结点个数为2^k-1，可以推导出满二叉树的深度为k=log₂(n + 1)。对于完全二叉树，它的叶子结点只会出现在最下面的两层，所以它的结点数一定少于等于同样深度的满二叉树的结点数2^k-1，但是一定多于2^k-1 -1。因为n是整数，所以2^k-1 <= n < 2^k，不等式两边取对数得到：k-1 <= log₂n <k。因为k作为深度也是整数，因此 k= [log₂n ]+ 1。

二叉树性质5

性质5：如果对一颗有n个结点的完全二叉树（其深度为[log₂n ] + 1）的结点按层序编号（从第1层到第[log₂n ] + 1层，每层从左到右），对任一结点i(1<=i<=n)有：

1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。

2. 如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点i。

3. 如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。

结合下图很好理解：

二叉树的存储结构

二叉树顺序存储结构

^代表不存在的结点。

对于右斜树，顺序存储结构浪费存储空间：

二叉树的顺序存储结构缺点很明显：不能反应逻辑关系；对于特殊的二叉树（左斜树、右斜树），浪费存储空间。所以二叉树顺序存储结构一般只用于完全二叉树。

二叉链表

链表每个结点包含一个数据域和两个指针域：

其中data是数据域，lchild和rchild都是指针域，分别指向左孩子和右孩子。

二叉树的二叉链表结点结构定义:

/*二叉树的二叉链表结点结构定义*/typedef struct BiNode{    char data;      /*结点数据*/    struct BiNode *lchild, *rchild;     /*左右孩子指针*/}BiNode,*BiTree;

参考：《大话数据结构》

作者：

来源：

声明：本文为博主学习感悟总结，水平有限，如果不当，欢迎指正。如果您认为还不错，不妨点击一下下方的【推荐】按钮，谢谢支持。转载与引用请注明出处。