本文共 14425 字，大约阅读时间需要 48 分钟。

作为数据结构的课程笔记，以便查阅。如有出错的地方，还请多多指正！

基本概念

• 树：仅有一个根、子树不相交
• 结点的度：结点拥有的子树数
• 一个结点的子树的根结点称为它的孩子结点， 而它称为孩子结点的父亲结点。与该结点同父亲的结点称为该结点的兄弟结点（同一层次非同父亲的结点称为堂兄弟结点)。如果存在一条从结点 $X$ 到结点 $Y$ 的从上至下的路径，那么称结点 $X$ 是结点 $Y$ 的祖先结点， 结点 $Y$ 是结点 $X$ 的子孙结点
  • 注意： 自己既是自己的祖先结点， 也是自己的子孙结点
• 树的度：一棵树中最大的结点度数
• 结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层……
• 深度(depth)：树中结点的最大层次数
• 森林(forest)：$m(m\ge 0)$棵互不相交的树的集合
• 有向树：树根和子树根之间为有向关系
• 有序树：子树之间存在确定的次序关系。将有序树最左边的子树的根称为第一个孩子
• 无序树：子树之间不存在确定的次序关系
• 满二叉树: 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树
• 完全二叉树：除最后一层外，每层都充满了结点，最下面一层结点都集中在该层的最左边。度小于2的结点只可能在层次最大的两层上出现，如果某个结点没有左孩子，那么它一定没有右孩子，该结点为叶子结点
  
• 结点的深度(depth) 是指从根结点（深度为1) 开始自顶向下逐层累加至该结点时的深度值；结点的高度(height) 是指从最底层叶子结点（高度为1)开始自底向上逐层累加至该结点时的高度值
• 树的深度是指树中结点的最大深度， 树的高度是指树中结点的最大高度。对树而言， 深度和高度是相等的，

---

• 注意：叶子结点被定义为度为 0 的结点，因此当树中只有一个结点（即只有根结点）时，根结点也算作叶子结点

二叉树 Binary Tree

二叉树的定义

• 二叉树的平均深度：$O(\sqrt{n})$
• 二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成
  • 二叉树的五种基本形态：
    

---

二叉树与度为 2 的树的区别

• 对树来说， 结点的子树是不区分左右顺序的， 因此度为 2 的树只能说明树中每个结点的子结点个数不超过 2。而二叉树虽然也满足每个结点的子结点个数不超过2, 但它的左右子树是严格区分的

二叉树的性质

• 二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点 ($i\ge 1$)
• 深度为 $k$ 的二叉树上至多含 $2^k-1$ 个结点（$k\ge 1$）
• 对任何一棵二叉树 $T$，如果其叶子结点数为 $n_0$，度为 2 的结点数为 $n_2$，则 $n_0=n_2+1$
  • 证明：设结点总数为 $n$
    $$n=n_0+n_1+n_2$$除了根节点外，其他结点都有分支结点进入，设分支结点数为 $B$，则
    $$n=B+1=n_1+2n_2+1$$两式联立可得 $n_0=n_2+1$
• 具有 $n$ 个结点的完全二叉树的深度为 $\lfloor lo{g}_{2}n\rfloor +1$
  • 证明：$$\begin{gathered} 2^{k-1}-1<n\le 2^k-1 \\ \therefore 2^{k-1}\le n<2^k \\ \therefore k-1\le lo{g}_{2}n<k \\ \therefore k=\lfloor lo{g}_{2}n\rfloor +1 \end{gathered}$$
• 如果对一棵有 $n$ 个结点的完全二叉树的结点按层序编号，则对任一结点 $i$ ($1\le i\le n$)，有：
  • (1) 如果 $i=1$，则结点 $i$ 是二叉树的根，无双亲；如果 $i>1$，则其双亲是$\lfloor i/2\rfloor$
  • (2) 如果 $2i\le n$，则其左孩子是 $2i$；如果 $2i>n$，则结点 $i$ 无左孩子
  • (3) 如果 $2i+1\le n$，则其右孩子是 $2i+1$；如果 $2i+1>n$，则结点 $i$ 无右孩子

二叉树的存储结构

顺序存储结构

• 按完全二叉树的结点层次编号，依次存放二叉树中的数据元素
  
• 适用于完全二叉树和满二叉树

二叉链表

• 每个结点包含数据域和左右指针域

typedef struct BiTNode {      	TElemType      data;    //数据域    struct BiTNode  *lchild, *rchild;} BiTNode, *BiTree;

三叉链表

• 比二叉链表多一个指针域指向父结点

typedef struct TriTNode{       TElemType   data;       //数据域     struct TriTNode  *lchild, *rchild, *parent; } TriTNode, *TriTree;

双亲数组

• 结点结构;
  
  

typedef struct BPTNode {    // 结点结构     TElemType  data;     int  parent;     // 双亲指针（下标）     char  LRTag;    // 左、右孩子标志域} BPTNode;typedef struct BPTree{    // 树结构     BPTNode nodes[MAX_TREE_SIZE];     int  num_node;     // 结点数目     int  root;                // 根结点的位置} BPTree;

线索二叉树

定义

• 遍历二叉树实质上是对一个非线性结构进行线性化操作。但是以二叉链表作为存储结构时，不能直接得到结点在任一序列中的前驱和后继信息
• 在$n$个结点的二叉链表中，一定有 $n+1$ 个空指针域，可以利用这些空指针域来存放结点的前驱和后继信息

在二叉链表的结点中增加两个标志域，并作如下规定：

• 若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域LTag的值为“指针 Link”； 否则，Lchild域的指针指向其“前驱”，且左标志LTag的值为“线索 Thread”
• 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域RTag的值为 “指针 Link”；否则，rchild域的指针指向其“后继”，且右标志RTag的值为“线索 Thread”

如此定义的二叉树的存储结构称作“线索链表”，与其相应的二叉树，称作 “线索二叉树”，指向结点前驱和后继的指针，称作"线索"

• 上图中，虚线为线索。左边为中序线索二叉树，右边为中序线索链表
• 线索链表中新增了一个头结点，LTag=0，左指针指向根结点，RTag=1，右指针指向中序遍历的最后一个结点。方便从第一个结点起顺后继遍历，或从最后一个结点起顺前驱遍历
• 空树时，线索链表的头结点的左右指针都指向自己

上图要求会画

typedef enum {   	Link,	Thread,}PointerTag_t;typedef struct BiTree {   	struct BiTree* L;	struct BiTree* R;	TreeElementType_t data;	PointerTag_t LTag;//线索二叉树	PointerTag_t RTag;}BiTree_t, *pBiTree_t;

遍历线索链表

下面以中序线索链表为例进行介绍

如何在中序线索链表中找结点的后继？

• 若无右子树，则为后继线索所指结点
• 否则为对其右子树进行中序遍历时访问的第一个结点(右子树中最左下的结点)

如何在中序线索链表中找结点的前驱？

• 若无左子树，则为前驱线索所指结点
• 否则左子树中最右下的结点(左子树中最后访问的结点)即为其前驱

//head为线索链表的头结点//顺序遍历中序线索二叉树Status_e In_order_thread_tree_traverse(pBiTree_t head, Status_e(*visit)(TreeElementType_t data)){   	pBiTree_t p = head->L; //先指向根结点	while (p != head)	{   		while (Link == p->LTag) //移动到最左下的结点		{   			p = p->L;		}		visit(p->data);		while ((Thread == p->RTag) && (p->R != head))		{   			p = p->R;			visit(p->data);		}		p = p->R;//退出循环说明该结点有右子树。因此访问其右子树	}	return ok;}//head为线索链表的头结点//逆序遍历中序线索二叉树Status_e In_order_thread_tree_reversed_traverse(pBiTree_t head, Status_e(*visit)(TreeElementType_t data)){   	pBiTree_t p = head->L;	while (p != head)	{   		while (Link == p->RTag)		{   			p = p->R;		}		visit(p->data);		while ((Thread == p->LTag) && (p->L != head))		{   			p = p->L;			visit(p->data);		}		p = p->L;	}	return ok;}

建立线索链表(二叉树的线索化)

在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱

• 书上给的递归版本伪代码：

void InThreading(BiThrTree p) {     if (p) {       						// 对以p为根的非空二叉树进行线索化    InThreading(p->lchild);      	// 左子树线索化    if (!p->lchild)      			// 建前驱线索      {    p->LTag = Thread;    p->lchild = pre; }    if (!pre->rchild)   			// 建后继线索      {    pre->RTag = Thread;   pre->rchild = p; }     pre = p;             			// 保持 pre 指向 p 的前驱    InThreading(p->rchild);      	// 右子树线索化  } // if} // InThreadingStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) {    //构建中序线索链表	if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);	Thrt->LTag = Link;  Thrt->RTag =Thread;  	//添加头结点	Thrt->rchild = Thrt;     					//右指针回指	if (!T)  Thrt->lchild = Thrt; 				//若为空二叉树 则左指针回指	else {                		Thrt->lchild = T;   pre = Thrt;		InThreading(T);                 		pre->rchild = Thrt;   					//处理最后一个结点		pre->RTag = Thread;    		Thrt->rchild = pre;    	}		return OK;} // InOrderThreading

• 我实现的非递归版本：

//建立中序线索二叉树并访问二叉树中的结点//返回线索链表的头结点pBiTree_t Build_in_order_thread_tree(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	pStackNode_t ptop;	pBiTree_t head;	TreeStackNode_t stack_node;	pBiTree_t pnow = NULL;	pBiTree_t ppre = NULL;//指向上一个访问过的结点	head = (pBiTree_t)malloc(sizeof(BiTree_t));//建头结点	head->LTag = Link;	head->RTag = Thread;	head->R = head;//右指针回指	if (!root)//若为空二叉树 则左指针回指	{   		head->L = head;		return head;	}	head->L = root;	Stack_init(&ptop);	pnow = root;	ppre = head;	while (!Is_empty(ptop) || pnow)	{   		while (pnow)		{   			stack_node.ptree = pnow;			Push(&ptop, stack_node);			pnow = pnow->L;		}		Pop(&ptop, &stack_node);		pnow = stack_node.ptree;		visit(pnow->data);		if (!(pnow->L))		{   			pnow->LTag = Thread;			pnow->L = ppre;		}		else {   			pnow->LTag = Link;		}		if (!(ppre->R))		{   			ppre->RTag = Thread;			ppre->R = pnow;		}		else {   			ppre->RTag = Link;		}		ppre = pnow;		pnow = pnow->R;	}	//最后一个元素的后继指向头结点(最后一个元素一定没有右子树)	ppre->RTag = Thread;	ppre->R = head;	head->R = ppre;	head->RTag = Thread;	return head;}

遍历二叉树

• 先序、中序、后序遍历经过结点的路线是一样的，只是访问各个结点的时机不同
• 先序、中序、后序遍历的实现都利用了堆栈，层次遍历的实现利用了队列

先序遍历

递归实现

Status_e Pre_order_traverse_recursive(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	if (root)	{   		visit(root->data);		Pre_order_traverse_recursive(root->L, visit);		Pre_order_traverse_recursive(root->R, visit);	}	return ok;}

• 所需辅助空间为栈的最大深度，即树的深度，最坏情况下为 $n$，因此 $S(n)=O(n)$

---

非递归实现

typedef struct {   	pBiTree_t ptree;	int cnt; // 记录入栈次数}TreeStackNode_t, pTreeStackNode_t;

Status_e Pre_order_traverse(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	TreeStackNode_t stack_node;	pStackNode_t ptop;	pBiTree_t pnode = root;	Stack_init(&ptop);	while ((!Is_empty(ptop)) || (NULL != pnode))	{   		while (NULL != pnode)		{   			visit(pnode->data);			stack_node.ptree = pnode;			Push(&ptop, stack_node);			pnode = pnode->L;		}		Pop(&ptop, &stack_node);		pnode = stack_node.ptree;		pnode = pnode->R;	}	return ok;}

中序遍历

递归实现

Status_e In_order_traverse_recursive(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	if (root)	{   		In_order_traverse_recursive(root->L, visit);		visit(root->data);		In_order_traverse_recursive(root->R, visit);	}	return ok;}

---

非递归实现

typedef struct {   	pBiTree_t ptree;	int cnt; //记录入栈次数}TreeStackNode_t, pTreeStackNode_t;

Status_e In_order_traverse(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	TreeStackNode_t stack_node;	pStackNode_t ptop;	pBiTree_t pnode = root;	Stack_init(&ptop);	while ((!Is_empty(ptop)) || (NULL != pnode))	{   		while (NULL != pnode)		{   			stack_node.ptree = pnode;			Push(&ptop, stack_node);			pnode = pnode->L;		}		Pop(&ptop, &stack_node);		pnode = stack_node.ptree;		visit(pnode->data);		pnode = pnode->R;	}	return ok;}

后序遍历

递归实现

Status_e Post_order_traverse_recursive(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	if (root)	{   		Post_order_traverse_recursive(root->L, visit);		Post_order_traverse_recursive(root->R, visit);		visit(root->data);	}	return ok;}

---

非递归实现

• 后序遍历的非递归实现要复杂一些。根结点是在右子树之后访问，因此增加访问次数域
  • 出栈时若访问次数为1，则表示已访问完左子树，因此访问次数加1后再次入栈
  • 若访问次数为2，则表示右子树也访问完了，因此直接输出

typedef struct {   	pBiTree_t ptree;	int cnt; //记录入栈次数}TreeStackNode_t, pTreeStackNode_t;

Status_e Post_order_traverse(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	TreeStackNode_t stack_node;	pStackNode_t ptop;	pBiTree_t pnode = root;	Stack_init(&ptop);	stack_node.cnt = 0;	while ((!Is_empty(ptop)) || (NULL != pnode))	{   		while (NULL != pnode)		{   			stack_node.ptree = pnode;			stack_node.cnt = 0;			Push(&ptop, stack_node);			pnode = pnode->L;		}		Pop(&ptop, &stack_node);		pnode = stack_node.ptree;		if (0 == stack_node.cnt)		{   			++stack_node.cnt;			Push(&ptop, stack_node);			pnode = pnode->R;		}		else {   			visit(pnode->data);			pnode = NULL;//要加上这一句 否则会一直访问最后一个元素		}	}	return ok;}

层次遍历

Status_e Level_order_traverse(pBiTree_t root, Status_e(*visit)(TreeElementType_t data)){   	Queue_t queue;	pBiTree_t ptree = root;	//空树 直接返回	if (NULL == root)	{   		return err;	}	Queue_init(&queue);	//根结点入队	En_queue(&queue, ptree);	while (!Is_empty(&queue))	{   		De_queue(&queue, &ptree);		visit(ptree->data);		if (NULL != ptree->L)		{   			En_queue(&queue, ptree->L);		}		if (NULL != ptree->R)		{   			En_queue(&queue, ptree->R);		}	}	return ok;}

遍历二叉树的应用

表达式树

三种遍历方法恰好可以得到前缀、中缀、后缀表达式(得到中缀表达式时需要加括号)

统计二叉树中叶子结点个数

叶子结点个数=左子树叶子数+右子树叶子数

int Leaf_cnt(pBiTree_t root){   	if (NULL == root)	{   		return 0;	}	else if((NULL == (root->L)) && (NULL == (root->R)))	{   		return 1;	}	else {   		return Leaf_cnt(root->L) + Leaf_cnt(root->R);	}}

求二叉树深度

二叉树深度=max{左子树深度+1，右子树深度+1}

对应于后序遍历

int Get_height(pBiTree_t root){   	if (NULL == root)	{   		return 0;	}	else {   		return MAX(Get_height(root->L), Get_height(root->R)) + 1;	}}

复制二叉树

对应于后序遍历

pBiTree_t Copy_bitree(pBiTree_t root){   	if (NULL != root)	{   		pBiTree_t new_root = (pBiTree_t)malloc(sizeof(BiTree_t));		new_root->data = root->data;		new_root->L = Copy_bitree(root->L);		new_root->R = Copy_bitree(root->R);		return new_root;	}	else {   		return NULL;	}}

建立二叉树的存储结构

按先序遍历序列建立二叉树的二叉链表

上图对应的先序序列：

对应于先序遍历

//先序创建二叉树 递归Status_e Create_bintree_pre_order_recursive(pBiTree_t *proot){   	TreeElementType_t data;	scanf_s("%d", &data);	if (NO_CHILD == data)	{   		*proot = NULL;	}	else {   		*proot = (pBiTree_t)malloc(sizeof(BiTree_t));		(*proot)->data = data;		Create_bintree_pre_order_recursive(&((*proot)->L));		Create_bintree_pre_order_recursive(&((*proot)->R));	}	return ok;}

//先序创建二叉树 非递归pBiTree_t Create_bintree_pre_order(void){   	pBiTree_t root;//根	TreeElementType_t data; //每次输入的数据	pStackNode_t ptop = NULL;//栈顶	TreeStackNode_t stack_node_son;	TreeStackNode_t stack_node_father;	Stack_init(&ptop);	//root	scanf_s("%d", &data);	getchar();	if (NO_CHILD == data)	{   		return NULL;//空树	}	else {   		//创建一个带计数的树节点 用在堆栈中		//初始cnt==0		stack_node_son.ptree = (pBiTree_t)malloc(sizeof(BiTree_t));		if (!(stack_node_son.ptree))		{   			return NULL;		}		stack_node_son.ptree->L = NULL;		stack_node_son.ptree->R = NULL;		stack_node_son.ptree->data = data;		stack_node_son.cnt = 0;		Push(&ptop, stack_node_son);		//保存根节点		root = stack_node_son.ptree;	}	while (!Is_empty(ptop))//栈非空	{   		Pop(&ptop, &stack_node_father);		scanf_s("%d", &data);		getchar();		if (NO_CHILD == data)		{   			//无左孩子 父结点重新入栈			if (0 == stack_node_father.cnt)			{   				stack_node_father.cnt++;				Push(&ptop, stack_node_father);			}		}		else {   			//创建一个带计数的树节点 用在堆栈中			//初始cnt==0			stack_node_son.ptree = (pBiTree_t)malloc(sizeof(BiTree_t));			if (!(stack_node_son.ptree))			{   				return NULL;			}			stack_node_son.ptree->L = NULL;			stack_node_son.ptree->R = NULL;			stack_node_son.ptree->data = data;			stack_node_son.cnt = 0;			//该节点为左孩子			if (0 == stack_node_father.cnt)			{   				//父节点重新入栈				stack_node_father.cnt++;				stack_node_father.ptree->L = stack_node_son.ptree;				Push(&ptop, stack_node_father);				//子节点入栈				Push(&ptop, stack_node_son);			}			else {   //该节点为右孩子				//父节点				stack_node_father.ptree->R = stack_node_son.ptree;				//子节点入栈				Push(&ptop, stack_node_son);			}		}	}	return root;}

按层序遍历序列建立二叉树的二叉链表

上图对应的层序序列：

pBiTree_t Create_bintree_level_order(void){   	Queue_t queue;	pBiTree_t root;	pBiTree_t pfather;	pBiTree_t pson;	TreeElementType_t data;	Queue_init(&queue);	//root	scanf_s("%d", &data);	if (NO_CHILD == data)	{   		return NULL;//空树	}	else {   		pson = (pBiTree_t)malloc(sizeof(BiTree_t));				pson->data = data;		pson->L = NULL;		pson->R = NULL;		root = pson;		En_queue(&queue, pson);	}	//队非空	while (!Is_empty(&queue))	{   		De_queue(&queue, &pfather);		//left child		scanf_s("%d", &data);		if (NO_CHILD != data)		{   			pson = (pBiTree_t)malloc(sizeof(BiTree_t));			pson->data = data;			pson->L = NULL;			pson->R = NULL;			pfather->L = pson;			En_queue(&queue, pson);		}		else {   			pfather->L = NULL;		}		//right child		scanf_s("%d", &data);		if (NO_CHILD != data)		{   			pson = (pBiTree_t)malloc(sizeof(BiTree_t));			pson->data = data;			pson->L = NULL;			pson->R = NULL;			pfather->R = pson;			En_queue(&queue, pson);		}		else {   			pfather->R = NULL;		}	}	return root;}

由二叉树先序序列和中序序列，构造二叉树

可由先序找到根，再已知根由中序找到左右子树；再由先序找到左右子树的根…

同理也可由后序序列和中序序列，构造二叉树

也可由层序序列和中序序列，构造二叉树

//用中序和先序序列构造二叉树 要求二叉树各个结点元素不相同//n为结点个数pBiTree_t Create_bintree_pre_in_order_sequence(TreeElementType_t pre_sequence[], TreeElementType_t in_sequence[], int n){   	if (0 == n)	{   		return NULL;	}	else {   		pBiTree_t proot = (pBiTree_t)malloc(sizeof(BiTree_t));		int root_index;				proot->data = pre_sequence[0];		//在中序序列中找到根		for (root_index = 0; root_index < n && in_sequence[root_index] != pre_sequence[0]; ++root_index)		{   		}		//所给序列错误		if (root_index == n)		{   			return NULL;		}		//左子树		proot->L = Create_bintree_pre_in_order_sequence(&pre_sequence[1], &in_sequence[0], root_index);		//右子树		proot->R = Create_bintree_pre_in_order_sequence(&pre_sequence[root_index + 1], &in_sequence[root_index + 1], n - root_index - 1);		return proot;	}}