文章目录

5. 树与二叉树

5.1 数的基本概念

5.1.1 树的定义

5.1.2 树的常用术语

5.2 二叉树的概述

5.2.1 基本概念

5.2.2 满二叉树定义

5.2.3 完全二叉树定义

5.2.4 单分支树的定义

5.2.5 二叉树的特性

5.2.6 存储结构

5. 树与二叉树

• 树形结构是一种非常重要的==非线性结构==，树形结构中数据元素之间具有==一对多==的逻辑关系。

5.1 数的基本概念

5.1.1 树的定义

• 树是由n(n>=0)个结点所构成的有限集合

  • 当n=0时，称为空树

  • 当n>0时，n个结点满足以下条件

    • 有且仅有一个称为根的结点

    • 其余结点可分为m个互不相交的有限集合，且每一个集合又构成一棵树，该树称为根节点的子树。

• 对于一颗非空树，其中有且仅有一个没有前驱的结点，这个结点就是==根节点==，其余结点有且仅有一个前驱，但可以有多个后继。

A

A

B

C

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

• 树的表示法：树形表示法、文氏图表示法、凹入图表示法和广义表(括号)表示法

  • 树形表示法

  • 文氏图表示法

    

  • 凹入图表示法

    

  • 广义表(括号)表示法

    

     

5.1.2 树的常用术语

5.2 二叉树的概述

5.2.1 基本概念

• 二叉树是一个特殊的树，每个结点最多只有两棵子树，且两棵子树也是二叉树。

• 精确定义：二叉树是由n（n>=0)个结点所构成的有限集合。当n=0时，这个集合为空，此时二叉树为空树，当n>0时，这个集合是由一个根结点和两个互不相交的分别称为左子树和右子树的二叉树构成。

• 二叉树的两棵子树有左右之分，所以二叉树是有序树。

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

• 二叉树的5种基本形态：空树、只有根结点、只有左子树、只有右子树、既有左子树又有右子树

/

X

X

X

/

X

/

X

X

X

X

5.2.2 满二叉树定义

• 满二叉树是二叉树的一种特殊情况。

• 如果在一棵二叉树中，它的所有结点或者叶结点，或者是左、右子树都非空，并且所有叶结点都在同一层上，则称这棵二叉树为满二叉树。

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

5.2.3 完全二叉树定义

• 如果在一棵具有n个结点的二叉树中，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同，则称这样的二叉树为完全二叉树。

A

B

C

D

E

F

G

H

I

J

K

5.2.4 单分支树的定义

• 左支树：所有结点都没有右孩子的二叉树。

  

   

• 右支树：所有结点都没有左孩子的二叉树。

  

   

5.2.5 二叉树的特性

1）特性1：i层最多结点数 2^i

• 二叉树中第i(i>=0)层上的结点数最多为2^i

$$
\begin{array}{c|cc} \hline i层&0&1&2&3&4&5&\cdots&i\\ \hline 最多结点数&2^0&2^1&2^2&2^3&2^4&2^5&\cdots&2^i\\ \hline 最多结点数&1&2&4&8&16&32&\cdots&2^i\\ \hline \end{array} \tag{i层最多结点数}
$$

2）特性2：最多结点个数 2^h-1

• 深度为h(h>=1)的二叉树中最多有2^h-1个结点

$$
S_n=a_1 + a_2 + a_3 + \cdots + a_{n-1} + a_n \\ S_n=a_1 + a_1q + a_1q^2 + \cdots + a_1q^{n-2} + a_1q^{n-1} \\ qS_n=a_1q + a_1q^2 + a_1q^3 + \cdots + a_1q^{n-1} + a_1q^n \\ S_n-qS_n=a_1-a_1q^{n} \\ S_n=\dfrac{a_1-a_1q^n}{1-q} \\ S_n=\dfrac{a_1(1-q^n)}{1-q} \tag{等比数列求和}
$$

$$
S_n=\dfrac{a_1(1-q^n)}{1-q} = 2^n-1 & (a_1=1, q=2) \\ S_n= 2^h-1 & (h \ge 1 , 最多) \\ S_n= 2^{h-1} & (h \ge 1 , 最少) \\ \tag{二叉树求和}
$$

3）特性3：叶子结点关系 n_0 = n_2 + 1

• 对于任意一颗二叉树，若其叶结点的个数为n_0，度为2的结点个数为n_2，则有n_0=n_2+1

  $$
  n_0 = n_2 + 1 & (n_0叶子节点个数,n_2度为2的结点个数) \\ \tag {}
  $$

• 验证1：

• 验证2：

  

   

• 证明

$$
& n_1 度为1的结点个数 ，n 总结点个数，e分支的个数 \\ n = n_0 + n_1 + n_2 & 总数 = 叶结点 + 度为1结点 + 度为2结点 \\ e = n_1 + 2 × n_2 & 度为1结点有1个分支，度为2的结点有2个分支 \\ n = e + 1 & 除了根结点，其他每个结点均对应一个进入它的分值 \\ n_0 = n_2 + 1
$$

4）特性4：深度 ⌊log2n⌋ + 1

• 具有n个结点的完全二叉树的深度为⌊log2n⌋ + 1 或 ⌊log2(n+1)⌋

  $$
  h = ⌊log_2n⌋ + 1 \tag{}
  $$

$$
\begin{array}{c|c|c} \hline 数的深度 &取值&公式&log_2n的值 & ⌊log2n⌋的值\\ \hline 3& 4 \le n \lt 8& 2^2 \le n \lt 2^3 & 2 \le log_2n \lt 3 & 2 \\ \hline 4& 8 \le n \lt 16& 2^3 \le n \lt 2^4 & 3 \le log_2n \lt 4 & 3 \\ \hline 5& 16 \le n \lt 32& 2^4 \le n \lt 2^5 & 4 \le log_2n \lt 5 & 4 \\ \hline 6& 32 \le n \lt 64& 2^5 \le n \lt 2^6 & 5 \le log_2n \lt 6 & 5 \\ \hline h& & 2^{h-1} \le n \lt 2^h & h-1 \le log_2n \lt h & h-1 \\ \hline \end{array} \tag{}
$$

• 数学常识

  向下取整的运算称为Floor，用数学符号⌊ ⌋表示；向上取整的运算称为Ceiling，用数学符号⌈ ⌉表示

  例如： ⌊59/60⌋=0 ⌈59/60⌉=1 ⌊-59/60⌋=-1 ⌈-59/60⌉=0

5）特性5：判断是否

• 若对含n个结点的完全二叉树从上到下且从左至右进行0至n-1的编号，则对完全二叉树中任意一个编号为1的结点有：

  1. 若i=0，则该结点是二叉树的根，无双亲，否则编号为(i-1)/2的结点为其双亲结点。

  2. 若2i+1>=n，则该结点无左孩子，否则，编号为2i+1的结点为其左孩子结点

  3. 如果2i+2>=n，则该结点无右孩子结点，否则，编号为2i+2的结点为其右孩子结点。

0

1

2

3

4

5

6

7

8

9

10

$$
\begin{array}{c|c|c} \hline 序号i& 结论5.1双亲节点 \frac{i-1}{2} & 个数n & 2i+1 & 结论5.2左孩子 & 2i+2 & 结论5.3：右孩子 \\ \hline 5 & \frac{5-1}{2}=2 & 7 & 11 & 无 & 12 & 无\\ \hline 3 & \frac{3-1}{2}=1 & 8 & 7 & 2×3+1 =7 & 8 & 无\\ \hline 4 & \frac{4-1}{2}=1 & 11 & 9 & 2×4+1=9 & 10 & 2×4+2=10\\ \hline \end{array} \tag{}
$$

5.2.6 存储结构

1）顺序存储结构

• 完全二叉树存储：

  用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各节点元素，即将完全二叉树编号为i的结点元素存储在下标为i数组元素中。

  

   

• 非完全二叉树：

  先在树中增加一些并不存在的虚结点并使其成为一棵完全二叉树，然后用与完全二叉树相同的方法对结点进行编号，再将编号为i的结点的值存放到数组下标为i的数组单元中，虚结点不存放任何值。

  

   

• 顺序存储适用于满二叉树和完全二叉树。

• 对于非完全二叉树来说，一个深度为h的树，需要的存储单元为2^h-1，会造成空间的浪费，如：对于右支树来说，只需要h个存储单元，但是存储的时候却要使用2^h-1个空间。

2）链式存储结构

• 二叉树的链式存储：将二叉树的各个结点随机的存放在位置任意的内存空间中，各个结点之间的逻辑关系通过指针来反映。

• 链式存储有2种方式：二叉链表存储结构、三叉链表存储结构

  • 二叉链表存储结构有3个域：数据域data、左孩子域lchild、右孩子域rchild

    

     

  • 三叉链表存储结构有4个域：数据域data、左孩子域lchild、右孩子域rchild、父节点域parent

    

     

• 二叉链表存储结构示意图

  

   

• 三叉链表存储结构示意图

  

   

• 二叉链式存储结构是二叉树最常用的存储结构。

  • 结点类

    public class BiTreeNode {
        public Object data;                 //数据域
        public BiTreeNode lchild, rchild;   //左、右孩子域
    }

  • 二叉树类

    public class BiTree {
        private BiTreeNode root;    
        //树的根节点
        public BiTree() {                   //构建一颗空树
            this.root = null;
        }
        public BiTree(BiTreeNode root) {    //构建一棵树
            this.root = root;
        }
    }

    root.lchild = new BiTreeNode("B");

    root.rchild = new BiTreeNode("C");