IT小白

这个屌丝很懒，什么也没留下！

热门标签

树的学习使用_树的双亲存储法

作者：IT小白 | 2024-05-06 16:43:07

踩

树的双亲存储法

一、树的逻辑结构

每个结点仅有一个父节点，或没有。

1：树的基本术语

1）结点的度：结点所拥有的的子树的个数（往下能再数几层）；

2）树的度：书中各节点度的最大值

3）叶子结点：度为0的结点，也称终端节点；

4）分支节点：度不为0的结点，也称非终端结点；

5）孩子、双亲：树中某结点子树的根节点称为这个结点的孩子结点，这个结点称为他孩子结点的双亲结点（近一个）；

6）兄弟：具有同一个双亲的孩子结点互相称之为兄弟；

7）路径：如果树的结点下班列n1,n2......nk有如下关系：结点ni是n（i+1）的双亲（1<=i<k），则把n1,n2......nk称之为一条由n1至nk的路径；路径上经过的边的个数称之为路径长度；

8）祖先、子孙：在树中，如果有一条从节点x到结点y，则x称之为y的祖先，而y称之为x的子孙；

9）结点所在层数：根节点的层数为1，对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层；

10）树的深度：树中所有节点的最大层数，也称高度；

11）层序编号：将树中节点从上层到下层、同层从左到右的次序一次给他们编从1开始的连续自然数；

12）有序树、无序树：如果一个数中结点的各子树从左到右是有次序的，则称这棵树为有序树；反之，称为无序树；

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

2：树结构和线性结构的比较

3：树的遍历操作

树的遍历：从根节点出发，按照某种次序访问树中所有结点，使得每个节点被访问且仅被访问一次；

1）前序遍历：

若树为空则空操作返回：

否则：访问根节点，并按照从左到右的顺序前序遍历根节点的每一棵子树；

A B D E H I F C G;(类似于迷宫栈或递归操作)

2）后序遍历

如树为空则空操作返回；

否则：按照从左到右的顺序前序遍历根节点的每一棵子树，并访问根节点；

D H I E F B G C A;

3)层序遍历：从树的第一层(即根结点)开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

上图：A B C D E F G H I;

二、树的存储结构

-----实现树的存储结构的关键是如何表示树中节点的逻辑关系

1：双亲表示法

用一个一维数组来存储输的各个节点（一般按照层序存储），数组中的一个元素对应树中的一个节点，包括节点的数据信息以及该节点的双亲在数组中的下标；

双亲表示法的实质是一个静态链表；

eg：（好像并查集）

上述查找所有节点类似于bfs和queue的操作；A->B,C;B->D,E,F;C->G,H;

2:孩子链表表示法

链表中的每个节点包括一个数据域和多个指针域，每个指针域指向该节点的一个孩子结点；

1）（每个节点）指针域的个数等于树的度；

缺点：浪费存储空间；

2）指针域的个数等于该节点的度；

缺点：结点结构不一致，编程操作麻烦；

3：双亲孩子表示法

将所有的孩子放在一起，构成线性表；

基本思想：把每个节点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有n个孩子链表。这n个单链表共有n个头指针，这n个头指针又组成了一个线性表，为了便于进行查找采用顺序存储。最后，将存放n个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组；

双亲孩子表示法：可以快速找孩子和双亲；

4：孩子兄弟表示法

某结点的第一个孩子是唯一的，某结点的右兄弟是唯一的。

三、二叉树的逻辑结构

1：二叉树的定义

二叉树是n（n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成；

2：二叉树的特点

（1）每个节点最多有两棵子树；

（2）二叉树是有序的，其次序不能任意颠倒；

注意：二叉树和树是两种树结构。

3：二叉树的基本形态

具有三个结点的树和具有三个结点的二叉树的形态：

4：特殊的二叉树

（1）斜树：所有节点都只有左子树的二叉树称为左斜树，只有右子树则称之为右斜树；

特点：1）在斜树中，每一层只有一个节点；

2）斜树的结点个数与其深度相同。

（2）满二叉树：在一棵二叉树种，如果所有分支节点都存在左子树和右子树，并且所有叶子树都在同一层上。

特点：1）叶子只能出现在最下一层；

2）只有度为0和度为2的结点；

3）满二叉树在同样深度的二叉树中结点个数最多；

4）满二叉树在同样深度的二叉树中叶子结点个数最多；

（3）完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。

左图为满二叉树，右图为完全二叉树；

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

上图则不是完全二叉树；

综上完全二叉树特点：

1）叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面：

2）完全二叉树中吐过有度为1的结点，只可能有1个，且该节点只有左孩子。

3）深度为k的完全二叉树在k-1层上一定是满二叉树；

4）在同样结点个数的二叉树中，完全二叉树的深度最小。

四、二叉树的基本性质

1：二叉树的基本性质

（1）二叉树的第i层上最多有2^(i-1)个结点(i>=1);

（2）一棵深度为k的二叉树中，最多有2^k -1个结点，最少有k个结点;

注：1）深度为k的具有2^k -1 个结点的二叉树一定是满二叉树；

2）深度为k且具有k个结点的二叉树不一定是斜树；

(3)在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有：n0=n2+1；

（4）具有n个结点的完全二叉树的深度为floor（(int)(log2（n）））+1；

（5）对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1<=i<=n）的结点，有：

五、二叉树的存储结构

1：顺序存储结构

用一维数组存储二叉树中的结点，并且结点的存储位置（下表）应能体现节点之间的逻辑关系--父子关系；一般仅存储完全二叉树；

缺点：对于斜树或者有很多空缺的非完全二叉树的二叉树，需增加很多空节点，会造成大量的空间浪费；

2：二叉链表

令二叉树的每个节点的对应一个链表节点，链表节点除了存放二叉树节点有关的数据信息外，还要设置指示左右孩子的指针；

在具有n个结点的二叉链表中，有n+1个空指针。

可以找双亲的三叉链表：

三叉链表的静态链表形式：数组模拟

优点：搜索快，节省空间；

缺点：不适合用于频繁插入、修改的；

六、二叉树的遍历操作

D的位置；

1：前序 DLR

A B D G C E F

2：中序LDR

D G B A E C F

3：后序LRD

G D B E F C A

4：层序遍历：从上到下、从左到右

使用顺序队列，（其操作类似于广度优先搜素的过程）;

队列中的元素都为指针，用来指向一个一个孩子结点的指针；


if(A!=NULL) q.push(A);
else return;
 
while(!q.empty()){
    func(q.front());
    //任意操作
    if(q.front().lchild!=NULL){
        q.push(q.front().lchild);
        //任意操作
    }
     if(q.front().rchild!=NULL){
        q.push(q.front().rchild);
        //任意操作
    }   
    q.pop();
}

七、二叉树的各种操作的实现

c++

1：创建二叉树


#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define ll long long
int a[N],b[N];
struct Bitree{
	char data;
	Bitree *lchild;
	Bitree *rchild;
}; 
int flag = 0;//
Bitree *creat(Bitree *bt){//以创建字符二叉树为例 
	char ch;cin>>ch;//输入 
	if(ch=='#'){
		bt = NULL;
	}
	else{//以前序遍历的方式创建一棵树 
		bt = new Bitree;
		bt->data = ch;//生成一个节点，数据域为ch
		bt->lchild = creat(bt->lchild);//递归建立左子树 
		bt->rchild = creat(bt->rchild);//递归建立右子树 
	//必须返回，不然只是建立了孩子结点，但未将他们和父节点连接起来 
	}
	return bt;
}
void print_tree(Bitree *bt){
	if(bt==NULL){
		cout<<'#';
	}else{
		 //AB#D##C##
		print_tree(bt->lchild);//后序遍历 
		print_tree(bt->rchild);
		cout<<bt->data;
	}
	return; 
}
int main()
{
	int i,j;
	//int n;cin>>n;
	Bitree *root;
	root = creat(root);
	print_tree(root);
}


//创建过程也可以写成这样
void *creat(Bitree* &bt){//以创建字符二叉树为例 
	char ch;cin>>ch;//输入 
	if(ch=='#'){
		bt = NULL;
	}
	else{//以前序遍历的方式创建一棵树 
		bt = new Bitree;
		bt->data = ch;//生成一个节点，数据域为ch
		creat(bt->lchild);//递归建立左子树 
		creat(bt->rchild);//递归建立右子树 
	//必须返回，不然只是建立了孩子结点，但未将他们和父节点连接起来 
	}
	return ;
}

2:根据二叉树的遍历结果确定二叉树

根据一棵二叉树的的前序和中序遍历序列，构造该二叉树；


#include<bits/stdc++.h>
using namespace std;
typedef struct Bitree{
	char data;
	Bitree *lchild;
	Bitree *rchild;
}Bitree_t,*Bitree_l; 
int find_index(char pre,char *mid)
{
	//目的是找b中和a中相等的那个结点代表的数据 
	for(int i=0;*(mid+i)!='\0';i++){
		if(pre == *(mid+i)){
			return i;
		}
	}
}
void create(Bitree_l *root,char prelist[],char midlist[])
{
	//定义静态变量，因为每一次前序每一个元素就销毁一个元素
	//
	static int index = 0;
	
	int mid_index = find_index(prelist[index],midlist); 
	*root = (Bitree_l)malloc(sizeof(Bitree_t));//开辟
	//将节点数据存在根节点中
	(*root)->data = prelist[index];
	//将先序已遍历的数据遍布置为'\0'
	prelist[index++] = '\0';
	//并且将中序遍历的那个数据所处位置置为'\0'
	midlist[mid_index] = '\0';
	//判断那个位置之前是否为空,若非空说明当前结点有左子树，继续递归创建左子树
	if(midlist[mid_index-1]!='\0'){
		create(&((*root)->lchild),prelist,midlist);
	}else{
		(*root)->lchild = NULL;//否则置为空 
	}
	//若当前节点有右孩子，递归创建
	if(midlist[mid_index+1]!='\0'){
		create(&((*root)->rchild),prelist,&midlist[mid_index+1]);
	}else{
		(*root)->rchild = NULL;
	} 
}
void print(Bitree_l root)
{
	if(root){
		print(root->lchild);
		print(root->rchild);
		cout<<root->data<<" ";
	}
}
int main()
{
	char prelist[100],midlist[100];
	cin>>prelist>>midlist;
	Bitree_l root;
	create(&root,prelist,midlist);
	//ABCDEFGHI
    //BCAEDGHFI
	print(root);
}