基本概念

定义

树是n个节点的有限集，有且仅有一个特定的称为根的节点

图示
特点

根节点是唯一的
子树的个数没有限制，但他们一定是互不相交的

树中的概念

结点的度(Degree)
- 结点拥有的子树数
叶结点
- 度为0的结点
分支结点
- 度不为0的节点
内部结点
- 除了根节点以外的分支节点
树的度
- 树内各结点的度的最大值

结点的关系

Child
- 结点的子树
Parent
- 该结点
Sibing
- 同一个Parent的Child

其他概念

树的深度(Depth)
- 结点的最大层次
有序树
- 树中结点的各子树从左至右是有序的，则称其为有序树
森林
- m棵互不相交的树的集合

树的ADT

树的存储结构

Parent表示法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


#define MAXSIZE 100 //具体数字依实际情况而定

typedef int TElemType;
typedef struct PTNode
{
	TElemType data;
	int parent;
}PTNode;

typedef struct
{
	PTNode Nodes[MAXSIZE];
	int r,n;
}PTree;

Child表示法

多重链表表示法

每个结点有多个指针域，每个指针域指向一棵子树的根节点

Child表示法

把每个结点的孩子结点排列起来，以单链表作为存储结构将他们存储起来

图示

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


typedef struct CTNode //定义孩子结点
{
	int child;
	struct CTNode *next;
}*ChildPtr;

typedef struct //定义头结点
{
	TElemType data;
	ChildPtr firstchild;
}CTBox;

typedef struct //定义树
{
	CTBox nodes[MAXSIZE];
	int r,n; // 根的位置和结点数
}CTree;

Sibling表示法

方法

设置两个指针，指向该结点的fristchild和rightsib

结构定义

1
2
3
4
5


typedef struct CSNode
{
	TElemType data;
	struct CSNode *firstchild,*rightsib;
}CSNode,*CSTree;

图示

二叉树

定义

n个结点的有限集合，由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树构成

特点

每个结点最多两棵子树
左子树和右子树是有顺序的,一定要区分开
五种形态

空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树

特殊二叉树

斜树

左斜树和右斜树并称斜树

满二叉树

分支节点均有两个子树的二叉树
图示

完全二叉树

定义
- 编号为$i(1\le i\le n)$的结点与满二叉树中相应位置编号相同的二叉树
特点
- 叶子结点只出现在最下两层
- 最下层的子叶一定集中在左部连续位置
- 同样结点数的二叉树，完全二叉树的深度最小
图示

二叉树的性质

在二叉树的第$i$层上，最多只有$2^{i-1}$个结点
深度为$k$的二叉树，至多有$2^k -1$个结点
叶结点为$n_0$,度为2的结点数为$n_2$，则$n_0 = n_2 + 1$
具有$n$个结点的完全二叉树的深度为$\lfloor log_2 n\rfloor + 1$
对于完全二叉树的任意结点$i(1\le i \le n)$

$i=1$，则为根结点
$i \gt 1$，则parent结点为$\lfloor i/2 \rfloor$
$2i \gt n$，则其无左孩子，否则其左孩子是结点$2i$
$2i+1 \gt n$，则其无右孩子，否则其右孩子是结点$2i+1$

二叉树的存储结构

顺序存储结构

一般只用于完全二叉树

二叉链表

结点结构

lchild	data	rchild

代码表示

1
2
3
4
5


typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

遍历二叉树

定义

从根结点出发，依照某找次序，依次遍历结点，使得每个结点仅被访问一次

方法

前序遍历

定义

若二叉树为空，则空操作返回;否则先访问根结点,再前序遍历左子树，最后前序遍历右子树

代码实现

1
2
3
4
5
6
7
8
9


// 通过递归实现前序遍历
void PreOrderTranverse(BiTree *T)
{
	if (T==NULL)
		return;
	printf("%c",T->data); //显示结点数据
	PreOrderTranverse(T->lchild);
	PreOrderTranverse(T->rchild);
}

中序遍历

定义

若二叉树为空，则空操作返回;否则从根结点开始，先中序遍历左子树，再访问根结点，最后中序遍历右子树

代码实现

1
2
3
4
5
6
7
8


void InOrderTranverse(BiTree *T)
{
	if (T==NULL)
		return;
	InOrderTranverse(T->lchild);
	printf("%c",T->data);
	InOrderTranverse(T->rchild);
}

后序遍历

定义可根据上述自行推导
代码实现

1
2
3
4
5
6
7
8


void PostOrderTranverse(BiTree *T)
{
	if (T==NULL)
		return;
	PostOrderTranverse(T->lchild);
	PostOrderTranverse(T->rchild);
	printf("%c",T->data);
}

二叉树遍历的性质

已知前序和中序遍历(后序和中序遍历)可以确定唯一的二叉树.
已知前序和后序遍历，无法确定唯一的二叉树.

二叉树的建立

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void CreateBiTree(BiTree *T)
{
	TElemType ch;
	scanf("%c",&ch);
	if (ch == "#")
		*T = NULL;
	else 
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
			exit(0);
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

线索二叉树

线索

指向前驱和后继的指针被称为线索，加上线索的二叉链表就被称为二叉链表，相应的二叉树被称为线索二叉树(Threaded Binary Tree)

线索化

定义

对于二叉树使用某种方式遍历使其成为线索二叉树

结点结构

lchild	ltag	data	rtag	rchild

ltag为0时，指向lchild;为1时，指向前驱
rtag为0时，指向rchild;为1时，指向后继

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


typedef enum {Link, Thread} PointerTag; 
// Link == 0 代表指向child;
// Link == 1 代表指向tag;

typedef struct BiThrNode
{
	TElemType data;
	struct BiThrNode *lchild,*rchild;
	PointerTag Ltag,Rtag;
}BiThrNode,*BiThrNode;

// 中序遍历进行中序线索化

void InThreading (BiThrTree p)
{
	if (p)
	{
		InThreading(p->lchild);
		
		InThreading(p->rchild);
	}
}