树与二叉树学习小结

树与二叉树学习小结

对于数据结构的内容，这里不再对栈与队列进行说明。我们先来说一下树与二叉树的内容（概念性的东西有点多）：

树的有关概念：

一棵树是由n（n>0）个元素组成的有限集合，其中：
（1）每个元素称为结点(node)；
（2）有一个特定的结点，称为根结点或树根（root）；
（3）除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合T0,T1,T2,……Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。
一个结点的子树个数，称为这个结点的度；度为0的结点称为叶结点；度不为0的结点称为分支结点；根以外的分支结点又称为内部结点，树中各结点的度的最大值称为这棵树的度。
定义一棵树的根结点的层次（level）为1，其它结点的层次等于它的父结点层次加1。一棵树中所有的结点的层次的最大值称为树的深度（depth）。
在用图形表示的树型结构中，对 两个用线段（称为树枝）连接的相关联的结点，称上端结点为下端结点的 父结点，称下端结点为上端结点的 子结点。称同一个父结点的多个子结点为 兄弟结点。称 从根结点到某个子结点所经过的所有结点为这个子结点的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。
对于树中任意两个不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。
森林（forest）是m(m>=0)棵互不相交的树的集合。

树的储存结构：

有如下几种方式：
一、数组（父亲表示法）：一个数据域，一个指针域（指向父节点），利用了树中除根结点外每个结点都有唯一的父结点这个性质。很容易找到树根，但找孩子时需要遍历整个线性表。
二、树形单链表结构（孩子表示法）：每个结点包括一个数据域和一个指针域（指向若干子结点），树的结点仅存放字符，只能从根（父）结点遍历到子结点，不能从某个子结点返回到它的父结点。
三、树形双链表结构（父亲孩子表示法）：每个结点包括一个数据域和二个指针域（一个指向若干子结点，一个指向父结点）这样就能综合前两种方法的功能。
例：

	const int m = 10;           //树的度
	typedef struct node;
	typedef node *tree; //声明tree是指向node的指针类型
	struct node
	{
	    char data;             //数据域
	    tree child[m];          //指针域，指向若干孩子结点
	    tree father;            //指针域，指向父亲结点
	};
	tree t;

四、二叉树型表示法（孩子兄弟表示法）（双链表表示结构）：每个结点包括一个数据域和二个指针域（一个指向该结点的第一个孩子结点，一个指向该结点的下一个兄弟结点）。

char data;            //数据域
tree firstchild, next;    //指针域，分别指向第一个孩子结点和下一个兄弟结点

树的遍历：

一、先序（根）遍历：先访问根结点，再从左到右按照先序思想遍历各棵子树。（与广搜类似）
二、后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。
三、层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。

下面再说一下二叉树的概念：

二叉树基本概念：

二叉树（binary tree,简写成BT）是一种特殊的树型结构，它的度数为2的树。即二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，它的两棵子树分别称为左子树、右子树。
二叉树有下面五种基本形态：

二叉树一定是有序的，通过它的左、右子树关系体现出来。

一棵深度为k且有2k–1个结点的二叉树称为满二叉树。这种树的特点是每层上的结点数都是最大结点数。当对满二叉树进行有序排列后可以引入完全二叉树的概念。

关于二叉树的一些具体性质：

一、在二叉树的第i层上最多有2^(i-1)个结点（i>=1）。（这里不作证明）
二、深度为k的二叉树至多有2^k –1个结点（k>=1）。（这里不作证明）
三、对任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数n0、1度结点n1和2度结点数n2之和：
n=no+n1+n2 ……(式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 ……(式子2)
由式子1和式子2得到：
no=n2+1
四、具有n个结点的完全二叉树的深度为floor(log2n)+1
五、对于一棵n个结点的完全二叉树，对任一个结点（编号为i），有：
①如果i=1,则结点i为根，无父结点；如果i>1,则其父结点编号为i/2。
如果2 * i>n，则结点i无左孩子（当然也无右孩子，即结点i为叶结点）；否则左孩子编号为2 * i。
②如果2*i+1>n，则结点i无右孩子；否则右孩子编号为2 * i+1。

二叉树的操作:

最重要的是遍历二叉树，但基础是建一棵二叉树、插入一个结点到二叉树中、删除结点或子树等。
所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
对于二叉树的储存结构与对二叉树的具体操作将后续写到。