目录

一、基本概念：

二、二叉树

---

一、基本概念

     1、树是n(n≥0)个节点的有限集T,n为0时称为空树，对于非空树有且仅有一个特定被称为根的节点。下图中树的节点有限集T={A,B,C,D,E,F,G,H,I,G,K,L,M,N,O}            

 

 

 

          

 

 

 

    2、     对于非空树有且仅有一个节点被称为根节点；（其中A是根节点）

3、非根节点的m个互不相交的子集T1,T2….,Tm ,其中每个子集本身又是一棵树。称为子树。T1={B},T2={C,F,G,K,L,M,N},T3={D,H,I,O,J};T4={E} 构成根A的四颗子树。

4、每一颗子树的根都被来自根r的一条有向的边所连接；

5、树中的一个节点拥有的子树的数称为该节点的度。一棵树的度是指该树节点的最大度数。

•       树的度为4
•       节点A的度数为4，节点B的度数为0，节点C的度数为2，节点D的度数为3，节点F 的度数为4.

6、树中某个节点的子树的根称为该节点的孩子，该节点称为孩子节点的双亲。

7、没有子树的节点称为树叶

•     节点B,E,K,L,M,M,H,G,J,O为树叶

8、具有相同根的节点叫做兄弟节点；

9、从节点n1到nk的路径定义为节点n1，n2， n3 ，n4………. nk的一个序列，使得对于序列上1≤i<k 节点 ni是ni+1的父亲，这条路径的长为该路径上的边数的条数，即：k-1;

10、任意节点的深度为从根到ni节点的唯一路径的长。因此根的深度都是0；（K的深度是3）

节点ni的高是从ni到一片树叶的最长路径的长。因此树叶的高都是0，一棵树的高等于它的根的高。F的高度为1.

二、二叉树

1. 二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

      

 

2、二叉树性质、

• 性质1：二叉树第i层上的节点数目最多为2i-1（i>0）
• 性质2：深度为k的二叉树支队有2k-1个节点（k≥0）
• 在任意一棵二叉树中，若叶子节点个数为n0，度为2的节点数为n2，则n0= n2+1
• 具有n个节点的完全二叉树的深度为|log2n|+1

3、一棵深度为k且有2k-1个节点的二叉树称为满二叉树（除最后一层无任何子节点外，每一层上的所有结点都有两个子结点，也可以这样理解：除叶子结点外的所有结点均有两个子结点）；

4、若二叉树的高度为h,除第h层外，其他各层（1~h-1）的节点数都达到了最大的个数，并且最下一层上的节点都连续集中在最左边的若干位置上，则次二叉树称为完全二叉树。在完全二叉树中，若某个节点没有左孩子，则它一定没有右孩子，且该节点一定是叶子节点。