C语言：二叉树基础

一、树

1.1    树的概念

1.树是有n个节点组成的具有层次关系的集合，是一种非线性的结构。

2.树的第一个节点称为根，根没有前驱节点。

3.除了根节点，其余每个节点都只有一个前驱节点，有0个或多个后继节点。

4.节点的度：一个节点含有子树的个数（后继节点的个数）称为该节点的度。

5.叶子节点或终端节点：度为0的节点。

6.非终端节点或分支节点：度不为0的节点。

7.父节点或子节点：如果一个节点含有子节点（后继节点），则这个节点为子节点的父节点。

8.子节点或孩子节点：如果一个节点含有父节点（前驱节点），则这个节点为父节点的子节点。

9.兄弟节点：具有相同父节点的节点互为兄弟节点。

10.树的度：在一颗树中，所有节点中度最大的节点的度，就是这颗树的度。

11.节点的层次：从根开始位第一层，根的子节点为第二层，以此类推。

12.树的高度或深度：节点的最大层次即为树的高度。

13.堂兄弟节点： 两个节点的父节点在同一层的节点互为堂兄弟节点。

14.节点的祖先：从该节点到根经过的所有节点均为该节点的祖先。根节点是所有节点的祖先。

15.子孙：以某一个节点为根的子树中的任意节点都是该节点的子孙。

16.森林：有n(n>0)棵互不相交的树的集合称为森林。

二、二叉树

2.1二叉树的概念

1.概念：如果一颗树的所有节点的子节点都不超过2，则这颗树可以称为二叉树。

2.满二叉树：如果一个二叉树的每一层节点数都达到最大，则这个二叉树为满二叉树。

3.完全二叉树：完全二叉树与满二叉树的区别在最后一层，完全二叉树的最后一层最后一层可以不满，但从左至右的节点必须连续不能有空。满二叉树是一种特殊的完全二叉树。

4.二叉树的性质：

 1. 若规定根节点的层数为i，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.

2. 若规定根节点的层数为i，则深度为h的二叉树的最大结点数是2^i-1.

3. 对任何一棵二叉树 , 如果度为0 其叶结点个数为x , 度为 2 的分支结点个数为y  ,则x=y+1.

4. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ，h=log(n+1)

5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子

3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子