树和二叉树(二级)

树

树的概念:树是一种典型的非线性结构,它具有明显的层次性,与自然界中的树根极为相似,因此而得名.

1．父结点：即结点的前件。除根结点外每个结点只有一个父结点。

2．子结点：即结点的后件。

3．根结点：没有父结点的结点，一棵树只有一个根结点。（如上图A结点）

4．叶子结点：没有子结点的结点。（如上图G、H、1、J结点）

5．度：一个结点的后件个数称为该结点的度。（如上图A的度为2）

6．树的度：一棵树中所有结点中最大的度数称为树的度。（如上图树的度为3）

7．结点的深度：从根结点到该结点的累计层数。（如上图D的深度为3）

8．树的深度：树的总层数即为树的深度。（如上图树的深度为4）

9．子树：以某结点的一个子结点为根构成的树成为该结点的一棵子树。

树的性质（树的总结点数的3种算法）

1．树的总结点数等于每层结点数之和。即

Sn=N1+N2+N3+...+Nx(（N，表示第K层的节点数）

2．树的总结点数等于所有不同度数的结点数之和。即

Sn=No+N1+N2+...+Nm(Nm表示度为m的节点数）

3．树的总结点数等于所有结点度数加1。即

Sn=Nox0+N1x1+N2x2+...+Nmxm+1(Nm表示度为m的节点数）

 

二叉树

二叉树的概念

二叉树是一种特殊的树结构。

二叉树具有以下两个特点：

①非空二叉树只有一个根结点；

②每个结点至多有两棵子树（即结点的度≤2），分别称为该结点的左子树和右子树。

二叉树有五种基本形态，分别是没有结点、只有根结点、只有左子树、有左右子树和只有右子树。

如下图所示：

  （a）空二叉树

（b）只有根结点二叉树

（c）只有左子树的二叉树

（d）左右子树均非空的二叉树

（e）只有右子树的二叉树

满二叉树:满二叉树是二叉树的一种特殊形态,是指除最后一层外,其余每一层上的结点都有两个子结点的二叉树,即该二叉树中每一层的含有最多的结点

完全二叉树:完全二叉树也是二叉树的一种特殊形态,是指除最后一层外,其余每一层上的结点均达到最大值,且在最后一层上只会缺少右边的若干结点,这种二叉树称为完全二叉树.

满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树.

 

二叉树的性质

性质1：非空二叉树的第K层上最多有2K-1个结点。

性质2：深度为K的二叉树，最多有2K-1个结点。

性质3：具有n个结点的二叉树，深度最少为［log，n］＋1，其中［log2n］表示取log2n的整数部分。

性质4：非空二叉树中，叶子结点数（度为0的结点）等于度为2的结点数加1，即

No=N2+1

 

二叉树的存储结构:

一般二叉树采用链式存储;

满二叉树和完全二叉树可以采用顺序存储;

顺序存储对于一般二叉树不适用.

二叉树的遍历:​

二叉树的遍历是指按某条搜索路径访问树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次.

常见的遍历方法有前序遍历(DLR),中序遍历(LDR)和后序遍历(LRD)三种.

①前序遍历(根左右)

在遍历二叉树时,先访问根节点,再遍历左子树,最后遍历右子树.

在遍历左子树和右子树时,也是先访问该子树的根节点,再遍历其左子树,最后遍历其右子树.即"根左右".

②中序遍历(左根右)

在遍历二叉树时,先遍历左子树,再访问根节点,最后遍历右子树.

在遍历左子树和右子树时,也是先遍历其左子树,再访问该子树的根节点,最后遍历其右子树.即"左根右".

顺序:GDHBEGACFK

③后序遍历(左右根)

在遍历二叉树时,先遍历左子树,再遍历右子树,最后访问根节点.

在遍历左子树和右子树时,也是先遍历其左子树,再遍历右子树,最后访问该子树的根节点.即"左右根".

顺序:GHDIGEBKFCA

 

前序遍历序列和中序遍历序列可以确定唯一确定一颗二叉树;

后序遍历序列和中序遍历序列可以确定唯一确定一颗二叉树;