博客

树和二叉树知识点总结

  • Post author:
  • Post category:其他




树的定义

树的定义：

树（Tree）是n（n>=0）个结点的有限集。

若n=0，称为空树

若n>0,则满足如下的两个条件：1.有且仅有一个特定的称为根的结点2.其余结点可分为m个互不相交的有限集

Tm,其中每一个集合本身又是一棵树，并称为根的子树

树的基本术语：

结点：数据元素以及指向子树的分支构成的

根结点：非空树中无前驱结点的结点

结点的度：结点拥有的子树数。

树的度：树内各结点的度的最大值。

度为0的结点被称为终端结点或者叶子结点。

度不为0的被称为分支结点或者非终端结点，根节点以外的分支结点被称为内部结点。

结点的子树的根被称为该结点的孩子，该结点被称为孩子的双亲。

有共同双亲的结点被称为兄弟结点

堂兄弟结点：双亲在同一层的结点。

结点的祖先：从根到该结点所经分支上的所有结点

结点的子孙：以某结点为根的子树中的任一结点

树的深度：树中结点的最大层次，根结点为第一层

有序树：树中结点的各子树从左到右有次序（最左边的为第一个孩子）。

无序树：树中结点的各子树无次序。

森林：是m（m>=0）棵互不相交的树的集合。

把一棵树的根结点删除后，树也就变成了森林。

一棵树可以看成是一个特殊的森林。

给森林中的各子树加上一个双亲结点，森林就变成了树。



二叉树的定义

因为普通树运算太复杂了，因此普通树转化为二叉树，可以方便运算。

二叉树：1.结构简单，规律性强2.可以证明所有树都能转为唯一对应的二叉树，不失一般性。

二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

二叉树定义：

二叉树是n个结点的有限集，它或者是空集或者由一个根节点及两棵互不相交的分别称为这个根的左子树和右子树的二叉树组成。

特点;

1.每个结点最多由两个孩子

2.子树有左右之分，次序不能颠倒

3.二叉树可以是空集合，根可以有空的左子树或者空的右子树

注意:二叉树不是树的特殊情况，它们是两个概念

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也进行区分，说明它是左子树还是右子树。

树当结点只有一个孩子的时候，就无需区分它是左还是右的次序。因此两种是不同的。这是二叉树与树的最主要的差别。



二叉树的性质

性质1：在二叉树的第i层上至多有2的（i-1）次方个结点（i>=1）,最少有一个结点。

性质2：深度为k的二叉树至多有（2的k次方-1）个结点，最少有k个结点。

性质3：对任何一棵二叉树T，如果其叶子树为n0，度为2的结点数为n2，则n0=n2+1。

性质4：

性质5：

4，5都是关于完全二叉树的性质

满二叉树和完全二叉树

这两种形式的二叉树在顺序存储方式下可以复原。

满二叉树：一棵深度为k且有（2的k次方-1）个结点的二叉树称为满二叉树

特点：1.每一层上的结点数都是最大结点数

2.叶子结点全部在最底层

编号规则:从根结点位置开始编号，自上而下，自左而右，每一个结点位置都有元素。

满二叉树在同样深度的二叉树中结点个数最多，叶子结点最多。

完全二叉树：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点相对应时，

称为完全二叉树。意思就是以满二叉树为模板，完全二叉树中的每个结点编号位子都跟满二叉树一样。

注意：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。

特点： 1.叶子只可能分布在层次最大的两层上

2.对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1。

性质4：具有n个结点的完全二叉树的深度为(log2 n)+1 ()的含义是不大于内部运算结果的最大整数 （表明了完全二叉树结点数n与完全二叉树深度k之间的关系）

性质5：（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲结点为i/2的最大整数。

（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i；

（3）如果2i+1>n。则结点i无右孩子；否则，其右孩子是结点2i+1.

（性质5）表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系。

性质5是用来当知道一个结点的编号的时候就可以找到其双亲结点和左孩子结点和右孩子结点的编号

二叉树的存储结构：顺序存储结构

链式存储结构：二叉链表

三叉链表



二叉树的顺序存储

二叉树的顺序存储

实现;按满二叉树的结点层次编号，依照编号存入到数组中，依次存放二叉树中的数据元素

二叉树的顺序存储缺点：最坏情况：深度为k的且只有k个结点的单支树需要长度为2的k次方-1的一维数组

特点：结点间关系蕴含在其存储位置中，浪费空间，适用于存储满二叉树和完全二叉树 

#define MAXTSIZE 100
typedef int TElmeType;
typedef TElmeType SqBiTree[MAXTSIZE];//定义数组类型，里面存储的类型为TElemType类型
SqBiTree bt;//定义变量



二叉树的链式存储结构

二叉树结点的特点：

存储方式：二叉链表 lchild|data|rchild
                  三叉链表 lchild|data|parent|rchild

在n个结点的二叉链表中，有2n-（n-1）个空指针域。

分析：必有2n个链域。除根节点外，每个结点有且仅有一个双亲，所有只会有n-1个结点的链域存放指针，指向非空子节点。



二叉链表表示方式

typedef struct BiNode
{
	TElmeType data;//数据域
	struct BiNode *lchild, *rchild;//左右孩子指针
}BiNode,*BiTree;



三叉链表表示方式`

typedef struct TriTNode
{
	TElmeType data;
	struct TriTNode *lchild, *parent, *rchild;

}TriTNode,*TriTree;



遍历二叉树

遍历定义–顺着某一条搜索路径巡访二叉树中的结点，使

得每个结点均被访问一次，而且仅被访问一次。

访问的含义很广：可以是对结点各种处理，如：输出结点的信息，修改结点的数据值等，但是要求这种访问不破坏原来的数据结构。

遍历的目的–得到树中所有结点的一个线性排列

遍历用途–它是树结构插入，删除，修改，查找和排序运算的前提，是二叉树一切运算的基础和核心。



先序遍历算法实现

规定先左后右（D根，L左子树，R右子树）

DLR–先（根）序遍历->得到的表达式为前缀表达式

若二叉树为空，则空操作；否则

（1）访问根结点；

（2）先序遍历左子树

（3）先序遍历右子树 

typedef int Status;
#define OK 1
void visit(const BiTree T)
{
	//待执行的操作
}
Status PreOrderTraverse(BiTree T)
{
	if (T == nullptr)return OK;//空二叉树
	else
	{
		visit(T);//访问根结点
		PreOrderTraverse(T->lchild);//递归遍历左子数
		PreOrderTraverse(T->rchild);//递归遍历右子树
	}
	return OK;
}



中序遍历算法实现

LDR–中（根）序遍历->得到的表达式为中缀表达式

若二叉树为空，则空操作；否则

（1）中序遍历左子树

（2）访问根结点；

（3）中序遍历右子树 

typedef int Status;
#define OK 1
void visit(const BiTree T)
{
	//待执行的操作
}
Status InOrderTraverse(BiTree T)
{
	if (T == nullptr)return OK;//空二叉树
	else
	{
		InOrderTraverse(T->lchild);//递归遍历左子数
		visit(T);//访问根结点
		InOrderTraverse(T->rchild);//递归遍历右子树
	}
	return OK;
}



后序遍历算法实现

LRD–后（根）序遍历 ->得到的表达式为后缀表达式

若二叉树为空，则空操作；否则

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点； 

typedef int Status;
#define OK 1
void visit(const BiTree T)
{
	//待执行的操作
}
Status PostOrderTraverse(BiTree T)
{
	if (T == nullptr)return OK;//空二叉树
	else
	{
		PostOrderTraverse(T->lchild);//递归遍历左子数
		PostOrderTraverse(T->rchild);//递归遍历右子树
		visit(T);//访问根结点
	}
	return OK;
}

可以通过前缀表达式和中缀表达式或中缀表达式和后缀表达式，反推二叉树。

遍历左子树和右子树可如同遍历二叉树一样递归的进行下去。

若二叉树中各结点的值均不相同，则二叉树结点的先序序列，中序序列，后序序列都是唯一的。

可以通过先序序列，中序序列或者后序序列，中序序列来判断一个唯一的二叉树

在先序和后序中寻找根，在中序中寻找根的左右子树。



中序遍历非递归算法

二叉树中序遍历的非递归算法的关键:在中序遍历过某结点的整个左子树后，如何找到该节点的根以及右子树。

基本思想;

(1)建立一个栈

（2）根结点进栈，遍历左子树

（3）根结点出栈，输出根节点，遍历右子树。 

#include<stack>
using namespace std;
Status InOrderTraverse(BiTree T)
{
	BiTree p,q;//定义两个指向结点的指针
	stack<BiTree> S;//建立一个栈
	p = T;//首先让树的第一个根被p所指

	while (p||!S.empty())//判断p和栈是否为空
	{
		if (p)
		{
			S.push(p);//进栈
			p = p->lchild;//将p现在指的结点的左子树赋值给p

		}
		else
		{
			S.pop();//出栈
			printf("%c", q->data);//打印出栈元素
			p = q->rchild;//将出栈的根的右子树赋值给p
		}
	}
	return OK;
}



二叉树的层次遍历算法

算法设计思路：使用一个队列

1.将根结点进队

2.队不空时循环：从队列中出列一个结点*p，访问它；

若它有左孩子结点，将左孩子结点进队；

若它有右孩子结点，将右孩子结点进队。 

伪代码块，需要加上数据结构队列的封装。
typedef struct
{
	BTNode data[MaxSize];//存放队中元素
	int front, rear;//队头和队尾指针
}SqOueue;//顺序循环队列类型

void LevelOrder(BTNode *b)
{
	BTNode *p;
	SqOueue *qu;
	InitQueue(qu);//初始化队列
	enQueue(qu, b);//根节点指针进入队列
	while (!QueueEmpty(qu))//队不为空，则循环
	{
		deQueue(qu, p);//出队结点p
		printf("%c", p->data);//访问结点p
		if (p->lchild != NULL)enQueue(qu, p->lchild);//有左孩子的时候，左孩子进队
		if (p->rchild != NULL)enQueue(qu, p->rchild);//有右孩子的时候，右孩子进队

	}
}



二叉树遍历算法的应用



创建二叉树

例如已知某一个先序序列，要求按照先序遍历序列建立二叉树的二叉链表

1.从键盘输入二叉树的结点信息，建立二叉树的存储结构

2.在建立二叉树的过程中按照二叉树先序方式建立

（注意，只知道先序序列是得不到唯一的二叉树，可以添加叶子结点下面两个结点为#号或者其他符号变为完全二叉树，这样就可以知道唯一的二叉树）

字符串：ABC##DE#G##F### 先序排列 

#include<iostream>
Status CreatBiTree(BiTree & T)
{
	char ch;
	std::cin >> ch;//输入字符
	if (ch == '#')
		T = nullptr;//如果字符输入为#号则为空
	else
	{
		if (!(T = new BiNode))//在堆区创建区域，并判断是否创建成功
			exit(OVERFLOW);
		T->data = ch;//向数据域传入字符
		CreatBiTree(T->lchild);//构造左子树
		CreatBiTree(T->rchild);//构造右子树
	}
	return OK;
}



复制二叉树

如果是空树，递归结束；

否则，申请新结点空间，复制根节点

递归复制左子树

递归复制右子树` 

int Copy(BiTree T, BiTree & NewT)
{
	if (T == NULL)
	{
		NewT = nullptr;
		return 0;
	}
	else
	{
		NewT = new BiNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);//复制左孩子
		Copy(T->rchild, NewT->rchild);//复制右孩子

	}
}



计算二叉树深度

如果是空树，则深度为0

否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，

二叉树的深度则为m与n的较大者加1. 

int n = 0;
int m = 0;
int Depth(BiTree T)
{
	if (T == nullptr)
		return 0;
	else
	{
		m = Depth(T->lchild);//递归计算左子树的深度
		n = Depth(T->rchild);//递归计算右子树的深度                                                                                     
		if (m > n)
			return(m + 1);
		else
			return (n + 1);
	}
}



计算二叉树结点总数

如果是空树，则结点个数为0；

否则，结点个数为左子树的结点个数+右子树的结点个数再+1 

int NodeCount(BiTree T)
{
	if (T == nullptr)
		return 0;
	else
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}```



计算叶子结点个数

如果是空树，则叶子结点个数为0，

否则，为左子树的叶子结点个数+右子树的叶子结点个数 

int LeadCount(BiTree T)
{
	if (T == nullptr)
		return 0;
	if (T->lchild == nullptr && T->rchild == nullptr)
		return 1;
	else
		return LeadCount(T->lchild) + LeadCount(T->rchild);

}



线索二叉树

提出问题:

任何寻找特定遍历序列中二叉树结点的前驱和后继

解决的办法：

1.通过遍历寻找，但是费时间

2.再增设前驱后继指针域，但是增加了存储负担

3.利用二叉链表中的空指针域

利用二叉树性质4，具有n个结点的二叉链表中国，一共有2n个指针域，因为

n个结点中有n-1个孩子，即2n个指针域中，有n-1个用来指示结点的左右孩子，

其余n+1个指针域为空。

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；

如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继（这种改变指向的指针称为线索）

加上了线索的二叉树称为线索二叉树

为区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表

中每个结点增设两个标志域ltag和rtag，并约定：

ltag = 0 lchild指向该结点的左孩子

ltag = 1 lchild指向该结点的前驱

rtag = 0 rchild指向该结点的右孩子

rtag = 1 rchild指向该结点的后继 

typedef struct BiThrNode
{
	int data;
	int ltag, rtag;
	struct BiThrNode * lchild, * rchild;

}BiThrNode,*BiThrTree;

这样每一个序列遍历必有一个头节点的左孩子域和尾结点的右孩子域处于悬空状态

为了更加方便的操作，增加一个头节点，让头节点的数据与为空，头结点的lchild指向根节点

lfag置为0，rchild指向尾节点，rfag置为1，并且头结点的lchild和尾结点的rchild均指向头结点。

/*

树的定义：

树（Tree）是n（n>=0）个结点的有限集。

若n=0，称为空树

若n>0,则满足如下的两个条件：1.有且仅有一个特定的称为根的结点2.其余结点可分为m个互不相交的有限集

Tm,其中每一个集合本身又是一棵树，并称为根的子树



森林的定义：

是m棵互不相交树的集合

*/



双亲表示法（找双亲容易，找孩子难）

//根节点没有双亲结点：其双亲域存放-1.

typedef int TElemType;

typedef struct PTNode

{


TElemType data;//数据域

int parent;//指针域

}PTNode;//结点结构

#define MAX_TREE_SIZE 100

typedef struct

{


PTNode nodes[MAX_TREE_SIZE];

int r, n;

}PTree;//树结构



孩子链表（找孩子容易，找双亲难）可以在双亲结点中新加一个双亲域

//孩子结点结构

typedef struct CTNode

{


int child;//孩子链表在数组中的位置

struct CTNode *next;//指向下一个孩子

}ChildPtr;

//双亲结点结构

typedef struct

{


TElemType data;//双亲数据域

ChildPtr firstchild;//孩子链表的第一个孩子

}CTBox;

//树结构-存放双亲

typedef struct

{


CTBox nodes[MAX_TREE_SIZE];

int n, r;//显示结点数和根结点的位置

}CTree;



孩子兄弟表示法（二叉树表示法，二叉链表表示法）

//实现:用二叉链表作树的存储结构，链表的每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

typedef struct CSNode

{


TElemType data;//数据域

struct CSNode *firstchild, *nextsibling;//指针域，第一个指向第一个孩子指针，第二个指向兄弟指针

}CSNode,*CSTree;



树与二叉树的转换

//树转换为二叉树：树中的第一个孩子，转化为根结点的左孩子，后面的兄弟结点依次转换为上一个兄弟的右孩子

/*



树转化为二叉树

步骤：
1.加线：在兄弟之间加一连线
2.抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
3.旋转：以树的根结点为轴心，将整数顺时针转45°
兄弟相连留长子



二叉树转化为树

步骤：
1.加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子.....沿分支找到的所有右孩子，都与p的双亲用线连起来
2.抹线：抹掉原二叉树中双亲与右孩子之间的连线
3.调整：将结点按层次排列，形成树结构
左孩右右连双亲，去掉原来右孩线

*/



森林转换成为二叉树（森林转换成二叉树，二叉树与多棵树之间的关系）

/*



森林转化为二叉树

步骤：

1.将各科树分别转换成二叉树

2.将每棵树的根节点用线相连

3.以第一棵树根结点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构

树变二叉根相连



二叉树转换成森林

1.抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

2.还原：将孤立的二叉树还原成树

去掉全部右孩线，孤立二叉再还原

*/

/*



树的遍历（三种方式）

先根（次序遍历）：若树不空，则先访问根结点，然后依次先根遍历各棵子树

后根（次序）遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点

按层次遍历：若树不空，则自上而下自左至右访问树种的每个结点

森林的遍历：

将森林看作由三部分构成：

1.森林中第一棵树的根结点

2.森林中第一棵树的子树森林

3.森林中其他树构成的森林

先序遍历顺序是1 2 3 ，中序遍历顺序是 2 1 3.

*/


版权声明：本文为holdtao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。