二叉树简介

Published on:
Tags: 数据结构 树

二叉树的定义#

定义：二叉树是一种特殊的树形结构，其特点是每个节点至多只有两棵子树，并且二叉树的子树有左右之分，次序不能颠倒。

二叉树的递归定义：二叉树是 $n(n>=0)$ 个节点的有限集合，其或者为空二叉树 $(n=0)$ ，或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。

几个特殊的二叉树#

满二叉树

定义：一棵高为 $h$ ，且有 $2^{h-1}$ 个节点的二叉树称为满二叉树。

特点：

  1. 叶子节点都在最下一层；
  2. 只有度为0和度为2的节点。

完全二叉树

定义：二叉树中最多只有最下面两层的节点的度数可以小于2，并且最下面一层的叶节点都依次排列在该层最左边的位置上。

特点：

  1. 叶子节点只能在层次最大的两层上出现；
  2. 最大层次上的叶子节点，都依次排列在该层最左边的位置；
  3. 如果有度为1的节点，只能有一个，且该节点只有左孩子，没有右孩子；
  4. 若 $i<=floor(n/2)$ ，则节点 $i$ 为分支节点，否则为叶子节点；

二叉搜索树

二叉搜索树（Binary Search Tree），又称二叉排序树（Binary Sort Tree）。

定义：一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 左、右子树也分别为二叉排序树；
  4. 没有键值相等的节点；

平衡二叉搜索树

定义：树上任一节点的左子树和右子树的深度之差不超过1。

平衡二叉搜索树也叫 AVL树 ，是平衡树的一种。

一般的，二叉排序树的查询复杂度取决于目标节点到树根的距离（即深度），因此当节点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡二叉树。

二叉树的性质#

性质1 非空二叉树上叶节点数等于双分支节点数加 $1$ 。

证明：

  1. 设节点数 $n$ ，叶子节点数 $n_0$ ，单分支节点数 $n_1$ ，双分支节点数 $n_2$，于是有等式： $n=n_0+n_1+n_2$
  2. 设度数 $r$ ，则有等式： $r=n_1+2n_2$
  3. 由树的 性质1 可知有等式： $n=r+1$
  4. 因此有等式：$n_1+2n_2+1=n_0+n_1+n_2$
  5. 所以有： $n_2+1=n_0$

性质2 非空二叉树上第 $i$ 层上至多有 $2^{i-1}$ 个节点，这里应有 $(i>=1)$ 。

由树的 性质2 可推出

性质3 高度为 $h$ 的二叉树至多有 $2^{h-1}$个节点 $(h>=1)$ 。

由树的 性质3 可推出

性质4 对完全二叉树中编号为 $i$ 的节点 $(1<=i<=n,n>=1)$

  1. 若 $i<=floor(n/2)$ ，即 $2i<=n$ ，则编号为 $i$ 的节点为分支节点，否则为叶子节点。
  2. 若 $n$ 为奇数，则每个分支节点都既有左孩子节点，也有右孩子节点；若 $n$ 为偶数，则编号最大的分支节点只有左孩子节点，没有右孩子节点，其余分支节点都有左、右孩子节点。
  3. 若编号为 $i$ 的节点有左孩子节点，则左孩子节点的编号为 $2i$ ；若编号为 $i$ 的节点有右孩子节点，则右孩子节点的编号为 $2i+1$ 。

性质5 具有 $n(n＞0)$ 个节点的完全二叉树的高度为 $ceil(log_2n)$ 或 $floor(log_2n)+1$

证明：

  1. 设二叉树高度为 $h$ ，可得等式：$f(h)=2^h-1=n$
  2. 二叉树的节点数量范围等式：$f(h-1) < n <= f(h)$
  • 两边加1： $f(h-1)+1$表示完全二叉树有 $h$ 层，且第 $h$ 层只有一个元素，$f(h)+1$同理表示完全二叉树有 $h+1$ 层，且第 $h+1$ 层只有一个元素
  • 变换可得等式： $f(h-1)+1 <= n < f(h)+1$
  • 即是： $2^{h-1} <= n < 2^h$
  • 求对数： $h-1 <= log_2{n} < h$
  • 整理可得： $log_2{n} < h <= log_2{n}+1$

二叉树的存储结构#

图1
图2

顺序存储结构

对二叉树中的每个节点进行编号，从根节点1开始，从上到下，从左到右，依序编号。

存储时，其编号从小到大的顺序就是节点在连续存储空间的先后次序。

如果是非完全二叉树（如图2），则需要先用空节点补全成为完全二叉树，然后再确定编号，最后再存储。

顺序存储结构保存的二叉树，需要先使用字符串表示法，描述二叉树结构，作为输入参数。

  1. 图1二叉树表示为：”#1234567”
  2. 图2二叉树表示为：”#123#5#7”

二叉树若使用顺序存储结构，则需要先使用字符串表示法描述二叉树结构。
如果遇到结构复杂的树，字符串表示法非常不方便描述树形结构，所以在实际应用中几乎不用。

链式存储结构

链式存储结构保存二叉树，使用括号表示法描述二叉树结构，作为输入参数。

  1. 图1二叉树表示为：”1(2(4,5),3(6,7))”
  2. 图2二叉树表示为：”1(2(,5),3(,7))”

定义一个结构体节点，包含有值域和两个分别指向左孩子节点和有孩子节点的指针。

1
2
3
4
5
6
7
typedef char ElemType;
typedef struct node
{
    ElemType data;                          //数据元素
    struct node *lchild;                    //指向左孩子
    struct node *rchild;                    //指向右孩子
} BTNode;

二叉树的遍历#

定义 按照一定次序访问树中所有节点，并且每个节点仅被访问一次的过程称为遍历。
遍历是最基本的运算，是树中所有其他运算的基础。

二叉树遍历算法有四种，分别是先序遍历、中序遍历、后序遍历、层次遍历。一般提及的有前三种，第四种层次遍历法比较少出现。

先序遍历

  • 访问顺序：根节点-左子树-右子树
  • 遍历图1结果：1245367

中序遍历

  • 访问顺序：左子树-根节点-右子树
  • 遍历图1结果：4251637

后序遍历

  • 访问顺序：左子树-右子树-根节点
  • 遍历图1结果：4526731

层次遍历

  • 访问顺序：从上到下，从左到右依次访问
  • 遍历图1结果：1234567