树的特点

  • 每个结点有零个或多个子结点
  • 没有父节点的结点称为根节点
  • 每一个非根结点有且只有一个父节点
  • 除了根结点外,每个子结点可以分为多个不相交的子树

树的常见术语

结点的度:结点拥有的子树的数目

子节点(child): 结点子树的根称为该节点的子节点。

父节点(parents): 子节点的上层节点叫做该节点的父节点。

姊妹节点(sibling): 具有同一父节结点的结点。

堂结点(cousin):双亲在同一层的结点互为堂兄弟。

叶结点(leaf):度为0的结点

分支结点:度不为0的结点

树的度:树中结点的最大的度

层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1

树的高度:树中结点的最大层次

森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。

有序树: 树中结点各子树从左至右是有序的,不能互换。

无序树: 树中结点各子树从左至右是无序的,可以互换。

m叉树: 允许所有的节点的度都不大于m。可以是空树。


树结构与线性结构的比较

线性结构树结构
头结点无前驱头结点无双亲
尾结点无后继叶结点无孩子
其它元素一个前驱一个后驱其它结点一个双亲,多个孩子
元素之间一对一元素之间一对多

二叉树

二叉树是每个结点最多有两个子树的树结构。它有五种基本形态:

二叉树的性质

  1. 二叉树第层上的结点数目最多为
  2. 深度为的二叉树至多有个结点
  3. 包含个结点的二叉树的高度至少为
  4. 在任意一棵二叉树中,若终端结点的个数为,度为2的结点数为,则

满二叉树

高度为,并且由个结点组成的二叉树,称为满二叉树。满二叉树的叶结点只能出现在树的最底层

完全二叉树

一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下层的叶结点集中在靠左的若干位置上,这样的二叉树称为完全二叉树。叶结点只能出现在最下两层 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

二叉树的链式储存结构

二叉树的链式储存结构

typedef struct Node{
	ElemType data;
	struct Node* lchild;
	struct Node* rchild;
} BTNode, *BT*;
 
typedef struct{
	BTNode* data[MAXSIZE];
	int top;
} SqStack;

三叉树的链式储存结构:在二叉树的基础上增加一个指向父结点的指针域。

二叉树的遍历

这一部分可以用上图&贪心算法,深度遍历和广度遍历

深度遍历-前序遍历ALR

根结点 —> 左子树 —> 右子树

  • 递归形式
void visit(Tree t, int level){
	printf("%c位于第%d层\n", t->data, level);
}
void scan(Tree t,int level){
	if (t != NULL){
		 visit(t, level);
		 scan(t->LeftChild, level + 1);
		 scan(t->RightChild,level + 1);
	 }
 }
  • 非递归形式
void inorder(PBT pbt){ 
	PStack ps = init_stack(MAXSIZE); 
	while ((pbt != NULL) || ! is_empty(ps)){ 
	if (pbt !=NULL){ 
		printf (“%c”, pbt->data); // 访问当前结点
		push_stack(ps, pbt); // 将pbt压栈 
		pbt = pbt->lchild; // 将pbt指向其左子树 
	} 
	else{ 
		pbt = pop_stack(ps); // 栈顶元素退栈  
		pbt = pbt->rchild; // 将pbt指向其右子树 
		} 
	} 
	destroy_stack(&ps); // 释放为栈分配的内存 
}

深度遍历-中序遍历LAR

左子树—> 根结点 —> 右子树

void visit(Tree t, int level){
	printf("%c位于第%d层\n", t->data, level);
}
void scan(Tree t,int level){
	if (t != NULL){
		 scan(t->LeftChild, level + 1);
		 visit(t, level);
		 scan(t->RightChild,level + 1);
	 }
 }
  • 非递归形式
void inorder(PBT pbt){ 
	PStack ps = init_stack(MAXSIZE); 
	while ((pbt != NULL) || ! is_empty(ps)){ 
	if (pbt !=NULL){ 
		push_stack(ps, pbt); // 将pbt压栈 
		pbt = pbt->lchild; // 将pbt指向其左子树 
	} 
	else{ 
		pbt = pop_stack(ps); // 栈顶元素退栈 
		printf (“%c”, pbt->data); // 访问当前结点 
		pbt = pbt->rchild; // 将pbt指向其右子树 
		} 
	} 
	destroy_stack(&ps); // 释放为栈分配的内存 
}

深度遍历-后序遍历LRA

左子树 —> 右子树 —> 根结点

void visit(Tree t, int level){
	printf("%c位于第%d层\n", t->data, level);
}
void scan(Tree t,int level){
	if (t != NULL){
		 scan(t->LeftChild, level + 1);
		 scan(t->RightChild,level + 1);
		 visit(t, level);- [[共轭类方法]]
	 }
 }
  • 非递归形式
void inorder(PBT pbt){ 
	PStack ps = init_stack(MAXSIZE); 
	while ((pbt != NULL) || ! is_empty(ps)){ 
	if (pbt !=NULL){ 
		if (!pbt->visited){
			push_stack(ps, pbt); // 将pbt压栈 
			}
		pbt = pbt->lchild; // 将pbt指向其左子树 
	} 
	else{ 
		pbt = pop_stack(ps); // 栈顶元素退栈 
		if (pbt->visited){
		printf (“%c”, pbt->data); // 访问当前结点 }
		else{ 
			pbt->visited = 1;
			push_stack(pb, pbt);
		}
		pbt = pbt->rchild; // 将pbt指向其右子树 
		} 
	} 
	destroy_stack(&ps); // 释放为栈分配的内存 
}

广度遍历

  • 层次遍历算法
    • 从根节点开始从上到下逐层遍历
    • 同一层中从左到右依次遍历
    • 按照先进先出特点使用队列结构。
  • 算法描述
    • 首先将根节点指针入队
    • 循环读取队首元素,递归操作知道队空
      • 访问该节点的数据部分
      • 若该节点有左子节点,将其入队
      • 若该节点有右子节点,将其入队
void level_order(PBT pbt) { // 层序遍历 
	PBT p; 
	PQue que = init_que(MAXSIZE); 
	if(pbt){ // 二叉树非空 
		enque(que, pbt); // 根节点(指针)入队 
		while (! is_empty(que)){ p = deque(que); // 队首元素出队 
		printf("%c", p->data); 
		if (p->lchild != NULL) { 
			enque(que, p->lchild); } 
		if (p->rchild != NULL) { 
			enque(que, p->rchild); } 
		} 
	} 
	destroy_que(&que); // 释放为队列分配的内存 
}

不同遍历算法的图示


统计二叉树叶结点个数

int count_leavs(PBT pbt){ 
	if(! pbt){
	return 0; //空树的叶节点数为零
	} 
	if((!pbt->lchild) && (!pbt->rchild)){
	return 1; //左右子树均为空,则为叶节点
	} 
	return count_leavs(pbt->lchild) + count_leavs (pbt->rchild); 
	//存在左右子树。递归调用结点统计函数
}

二叉树深度

int get_depth(PBT pbt){ 
	int dL = 0, dR = 0 
	if( pbt == NULL ){
		return 0; //空树深度为0
	}
	if((!pbt->lchild) && (!pbt->rchild)){ 
		return 1; //叶节点深度为1
	} 
	dL = get_depth (pbt->lchild); 
	dR = get_depth (pbt->rchild); 
	// 二叉树的深度为根结点左、右子树的深度值较大者加一 
	return 1 + ((dL > dR) ? dL : dR); 
}

哈夫曼树

树和森林

树的储存结构

1. 双亲数组表示
  • 实现: 定义结构数组存放树的结点,每个结点含两个域 
    • 数据域: 存放结点本身信息
    • 双亲域: 指示本结点的双亲结点在数组中的位置
    • 特点: 找双亲容易,找孩子难

#define SIZE 10
 
typedef char Datatype;
typedef struct PTNode
{
	Datatype ch;
	int parent;             //双亲位置域
}PTNode;           
 
typedef sturct
{
	PTNode nodes[SIZE];
	int r, n;                              //根结点的位置和结点个数
}PTree;
2. 孩子链表

堆排序

参考文献