树与二叉树（一）

Share 
本篇文章是树系列的第一篇文章，主要介绍树的类型定义、二叉树的类型定义等基础知识结构。

树的数据类型

数据元素D：D是具有相同特性的数据元素的集合

数据关系R：

　　若D为空集，则称为空树；否则：
　　
　　1.在D中存在唯一的称为根的数据元素root

　　2.当n>1时，其他结点可分为m(m>0)个互不相交的有限集，其中每一棵子集本身又是一棵符合定义的树称为根root的子树。
　　
基本操作：

　　1.查找类

　　2.插入类
　　
　　3.删除类

查找类：

1
2
3
4
5
6
7
8
root(T);				//求树的根结点
value(T, cur_e);		//求当前结点的元素值
parent(T, cur_e);		//求当前结点的双亲结点（前驱）
leftChild(T, cur_e);	//求当前结点的左孩子
rightSibling(T, cur_e);//求当前结点的右兄弟
treeEmpty(T);			//判断树是否为空树
treeDepth(T);			//求树的深度
traverseTree(T);		//树的遍历

插入类：

1
2
3
4
initTree(&T);				//初始化置空树
createTree(&T, definition);	//按定义构造树
assign(&T, cur_e, value);	//给当前结点赋值
insertChild(&T, &p, i, c);	//将以c为根的树插入为结点p的第i棵子树

删除类：

1
2
3
clearTree(&T);				//将树清空
destroyTree(&T);			//摧毁树的结构
deleteChild(&T, &p, i); 	//删除结点p的第i棵子树

有向树：

　　1.有确定的根
　　
　　2.树根与子树根之间为有向关系
　　
有序树：

　　子树之间存在着确定的次序关系

无序树：

　　子树之间不存在着确定的次序关系
　　

二叉树的数据类型

二叉树：或为空树；或为由一个根结点加上两棵分别称为左子树与右子树的、互不相交的树组成。

二叉树的五种基本形态：

　　1.空树
　　
　　2.只有根节点

　　3.右子树为空树

　　4.左子树为空树

　　5.左右子树均不为空树
　　
二叉树的主要基本操作：

查找类：

1
2
3
4
5
6
7
8
9
10
11
12
13
root(T);			
value(T, e);			
parent(T, e);			
leftChild(T, e);		
rightChild(T, e);		
leftSibling(T, e);		
rightSibling(T, e);		
biTreeEmpty(T);		
biTreeDepth(T);		
preOrderTraverse(T, visit());	//先序遍历
inOrderTraverse(T, visit());		//中序遍历
postOrderTraverse(T, visit());	//后序遍历
levelOrderTraverse(T, visit());	//按层次遍历

插入类：

1
2
3
4
initBiTree(&T);
assign(T, &e, value);
createBiTree(&T, definition);
insertChild(&T, p, LR, c);

删除类：

1
2
3
clearBiTree(&T);
destroyBiTree(&T);
deleteChild(&T, p, LR);

两类特殊的二叉树

满二叉树：深度为k且含有(2^k)-1个结点二叉树

完全二叉树：树中所含有的n个结点和满二叉树中编号为1～n的结点一一对应。完全二叉树的叶子结点可能出现在倒数第一层或者倒数第二层

二叉树的重要特性

性质：

1.在二叉树的第 i 层上最多有2^(i-1) 个结点
2.深度为k的二叉树上最多有(2^k)-1个结点；最少有k个结点
　　推广：满二叉树的第k层结点的个数比其1～(k-1)层的结点总数多一
3.对任何一棵二叉树，若它含有n0个叶子结点，n2个度为2的结点，则必存在关系式：n0 = n2 + 1
4.具有n个结点的完全二叉树深度为(log2n)(向下取整)+1 或(log2(n+1))(向上取整)
5.若对含有n个结点的完全二叉树从上到下且从左至右进行1～n的编号，则对完全二叉树中任意一个编号为i的结点：

度即为其后继结点的个数

证明：

1
2
3
4
设二叉树上结点总数为 n = n0 + n1 + n2
又二叉树上分支总数为 b = n1 + 2n2
而 b = n-1 = n0 + n1 + n2 -1
所以 n0 = n2 + 1

推广：一棵度为m的树中有n1个度为1的结点……有nm个度为m的结点。问其有多少个叶子结点

证明：

1
2
3
4
5
设n为总结点数，n0为叶子结点数，
则：n = n0 + n1 + n2 +…+ nm
又 n - 1 = 分支总数
则 n - 1 = n1*1 + n2*2 +…+ nm*m
则有 n0 = 1 + n2 + 2n3 +…+ (m-1)nm

证明：

1
2
设其深度为k
则根据第二条性质可得 2^(k-1) <= n < 2^k，取对数即可

对性质5的补充：

　　(1)若 i ＝ 1，则该结点为二叉树的根，无双亲；否则编号为i/2(向下取整)的结点为其双亲结点
　　
　　(2)若2i > n ,则该结点无左孩子；否则编号为2i的结点为其左孩子结点
　　
　　(3)若2i+1 > n ,则该结点无右孩子；否则编号为2i+1的结点为其右孩子结点