6. 树

6.1 树的定义及其存储结构
6.2 二叉树的定义和遍历
6.3 堆

6.1 树的定义及其存储结构

一、树的定义：
树是n(n>=0)个结点的有限集。在任意一棵非空树中：
(1)有且仅有一个特定的称为根的结点；
(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树.

二、树的基本概念：

树的 结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数称为结点的 度。
度为0的结点称为 叶子或 终端结点。
度不为0的结点称为 非终端结点或 分支结点。

树的度是树内各结点的度的最大值。
结点的子树的根称为该结点的 孩子，相应地，该结点称为孩子的 双亲。
同一个双亲的孩子之间互称 兄弟。
结点的 祖先是从根到该结点所经分支上的所有结点。
以某结点为根的子树中的任一结点都称为该结点的 子孙。
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度，或高度。
如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。
森林是m(m>=0)棵互不相交的树的集合。

三、二叉树的定义
二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
一棵深度为k且有2(k)-1个结点的二叉树称为满二叉树，如图(a)，按图示给每个结点编号，如果有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
二叉树的定义如下：

ADT BinaryTree{
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:
基本操作P:

InitBiTree(&T);
DestroyBiTree(&T);
CreateBiTree(&T,definition);
ClearBiTree(&T);
BiTreeEmpty(T);
BiTreeDepth(T);
Root(T);
Value(T,e);
Assign(T,&e,value);
Parent(T,e);
LeftChild(T,e);
RightChild(T,e);
LeftSibling(T,e);
RightSibling(T,e);
InsertChild(T,p,LR,c);
DeleteChild(T,p,LR);
PreOrderTraverse(T,visit());
InOrderTraverse(T,visit());
PostOrderTraverse(T,visit());
LevelOrderTraverse(T,Visit());

}ADT BinaryTree

四、二叉树的性质

五、二叉树的顺序存储结构
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

第i号结点的左右孩子一定保存在第2i及2i+1号单元中。
缺点：对非完全二叉树而言，浪费存储空间

六、二叉树的链式存储结构
一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置
对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。

也可以在结点中加上指向父结点的指针域P。

对结点有二个指针域的存储方式有以下表示方法：
typedef struct BiTNode{
TElemType data;
struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
基于该存储结构的二叉树基本操作有：
Status CreteBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示的二叉树T。
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
四、总结本课内容
顺序存储与链式存储的优缺点。

6.2 二叉树的遍历

三、递归法遍历二叉树
先序：
Status(PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
if(T){
if(Visit(T->data))
if(PreOrderTraverse(t->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}else return OK;
}

遍历结果：1,2,4,5,6,7,3
四、非递归法遍历二叉树

中序一：
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
InitStack(S);Push(S,T);
while(!StackEmpty(S)){
while(GetTop(S,p)&&p)Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S)){
Pop(S,p); if(!Visit(p->data)) return ERROR;
Push(S,p->rchild);
}
}
return OK;
}
中序二：
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
InitStack(S);p=T;
while(p||!StackEmpty(S)){
if(p){Push(S,p);p=p->lchild;}
else{
Pop(S,p); if(!Visit(p->data)) return ERROR;
p=p->rchild);
}//else
}//while
return OK;
}
五、总结
二叉树遍历的意义

二叉树实验

生成如下二叉树，并得出三种遍历结果：

一、二叉树的链式存储结构表示
typedef struct BiTNode{
TElemType data;
struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
二、二叉树的链式存储算法实现
CreateBiTree(&T,definition);
InsertChild(T,p,LR,c);
三、二叉树的递归法遍历
PreOrderTraverse(T,Visit());
InOrderTraverse(T,Visit());
PostOrderTraverse(T,Visit());

#include <alloc.h>

#define ERROR 0;
#define OK 1;

typedef int ElemType;
typedef struct BinaryTree

{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;

BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}

CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}

CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}

printelem(ElemType d)
{
printf("%d\n",d);
}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
main()
{
BiTree root;
CreateBiTree(&root);
PreOrderTraverse(root,printelem);

}

6.3 堆

堆（heap）
1) 堆ADT

定义：A max tree是一棵树，树中的每个结点的键值不小于它的所有子结点的键值。A max heap既是一棵完全二叉树，也是a max tree。
定义：A min tree是一棵树，树中的每个结点的键值不大于它的所有子结点的键值。A min heap既是一棵完全二叉树，也是a min tree。

通常我们用数组来表示一个堆，（因为它是一棵完全二叉树），数组的0元素不用，这样我们可以用前面完全二叉树的寻址方式来定位结点。
根据堆的定义，小堆中ROOT的键值是树中的最小值，大堆中ROOT的键值是树中的最大值。

大堆ADT的其他操作：
（1） 建立一个空堆；
（2） 插入一个新的元素到堆中；
（3） 从堆中删除最大值。
真正的挑战在于如何设计堆的表达方式，使有效地进行插入和删除。

2) 优先级队列
堆经常用于实现优先级队列。
与普通的队列不同，优先级队列首先将具有最高优先级的元素出队列。我们也可以在任何时候将具有一定优先级的元素插入一个优先级队列。
如果键值越大，优先级越高时，我们可以使用一个大堆来实现这样的优先级队列。比如操作系统的作业调度，给administrators高优先级，给student低优先级。对于相反的情况，我们可以使用一个小堆来实现这样的优先级队列。比如，假设操作系统的作业调度基于运行时间，具有最短运行时间的作业优先调度。

堆是实现优先级队列的一种方法。但是还有其他方法来实现优先级队列。
1． 数组是优先级队列的最简单的表达方式。它的效率为：插入只要简单地将元素放在当前数组最后的位置，因此，插入的时间复杂度为O（1）。为了实现删除，必须首先找到队列中的最大值再删除该元素，查找时间为O（n），移动元素的时间也为O（n）。
2． 有序队列也可以实现优先级队列，删除所用的时间为O（1），但插入一个元素需要移动1个或多个元素，需要O（n）时间。
3． 链表也可以用来实现优先级队列。假设链表维持一个非递增的序列，此时最高优先级的元素总在链表的第一个结点。然而，由于在插入时必须遍历链表，遍历所用的时间也要O（1）。
4． 堆，就象我们即将要讨论的，进行插入和删除操作所需的时间为：O（log2n）

Representation	Insertion	Deletion
Unordered array	θ(1)	θ(n)
Unordered linked list	θ(1)	θ(n)
Sorted array	O(n)	θ(1)
Sorted linked list	O(n)	θ(1)
Max heap	O （log2n ）	O （log2n ）

3) 大堆的插入
为了演示插入操作，我们从具有5个元素的大堆开始。当插入一个元素到大堆后，新的具有6个元素的大堆具有图5。28b所示的结构。在其他位置加入元素则违反了堆的定义：堆必须是一个完全二叉树。
为说明问题，我们举以下例子来说明：
（1） 插入1
（2） 插入5
（3） 插入21
为了实现操作，我们沿着从某元素到其父结点的路径进行。如果采用链表结构，则必须在结点中增加指向父结点的指针域。但由于大堆是完全二叉树，所以我们可以使用数组来实现。
Lemma 5.3: if a complete binary tree with n nodes (depth = [log2n +1]) is represented sequentially, then for any node with index I, 1 <= I <= n , we have:
(1) parent(I) is at [i/2] if I<>1. If I =1, I is at the root and has no parent
(2) left_child(I) is at 2I if 2I<=n. If 2I>n , then I has no left child
(3) right_child(I) is at 2I+1 if 2I+1<=n . If 2I+1>n , then I has no right child.

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n == MAX_ELEMENTS – 1)
#defiine HEAP_EMPTY(n) (!n)
typedef struct{
int key;
}element;
element heap[MAX_ELEMENTS];
int n = 0;

void insert_max_heap(element item, int *n)
{
int i;
if (HEAP_FULL(*n)){
fprintf(stderr,”The heap is full.\n”);
exit(1);
}
i = ++(*n);
While((i != 1) && (item.key > heap[i/2].key)){
Heap[i] = heap[i/2];
i /= 2;
}
heap[i] = item;
}

分析：沿着从新的叶结点到根结点的路径进行比较和更新，由于n个元素的完全二叉树的高度为[log2(n+1)]，这就意味着while循环要进行O（log2n）次，因此复杂度也为O（log2n）。

4) 在大堆中删除
当从大堆中删除时，总是将根结点的元素删除。这样，我们必须在删除后重建完全二叉树树。可以将最后一个元素移到根结点来完成重建完全二叉树，但该树不满足大堆的定义。为了重建堆，我们从根结点开始向下移动，比较父结点和它的子结点，如果父结点小于子结点则交换，直到堆被重建为止。

element delete_max_heap(int *n)
{
int parent, child;
element item, temp;
if (HEAP_EMTPY(*n)){
fprintf(stderr,”The heap is empty\n”);
exit(1);
}
item = heap[1];
temp = heap[(*n)--];
parent = 1;
child = 2;
while(child <= *n){
if(child < *n) && (heap[child].key < heap[child+1].key)
child ++;
if(temp.key >= heap[child].key) break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
复杂度也为O（log2n）。