wen 编程最新 2024-01-31

树型结构

树

定义

树是递归定义的。

一棵树是由n（n>0）个元素组成的有限集合，其中每个元素称为结点(node)，有一个特定的结点，称为树根（root），除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合T₀,T₁,T₂,……T_m-1，其中的每个子集又都是一棵树，这些集合称为这棵树的子树。

如图是一棵树：

一棵树中至少有1个结点，即根结点。

一个结点的子树个数，称为这个结点的度（如结点1的度为3，结点3的度为0）。

度为0的结点称为叶结点（leaf）（如结点3、5、6、8、9）。

树中各结点的度的最大值称为这棵树的度（此树的度为3）。

上端结点为下端结点的父结点，称同一个父结点的多个子结点为兄弟结点（如结点1是结点2、3、4的父结点，结点 2、3、4是结点1的子结点，它们又是兄弟结点）。

遍历

树结构解决问题时，按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。

先序(根)遍历

先访问根结点，再从左到右按照先序思想遍历各棵子树（如，上图先序遍历的结果为125634789）。

后序（根）遍历

先从左到右遍历各棵子树，再访问根结点（如，上图后序遍历的结果为562389741）。

层次遍历

按层次从小到大逐个访问，同一层次按照从左到右的次序（如，上图层次遍历的结果为123456789）。

叶结点遍历

即从左到右遍历所有叶节点（如，上图叶节点遍历的结果为56389）。

二叉树

二叉树是一种特殊的树型结构，它是度数为2的树，即二叉树的每个结点最多有两个子结点。

每个结点的子结点分别称为左儿子、右儿子。

五种基本形态

性质

性质一

二叉树的第i层最多有2^i-1个结点（i>=1）（可用二进制性质解释。）。

性质二

深度为k的二叉树至多有2^k–1个结点（k>=1）。

性质三

任意一棵二叉树，如果其叶结点数为n₀，度为2的结点数为n₂，则一定满足：n₀=n₂+1。

性质四

有n个结点的完全二叉树的深度为floor(log₂n)+1。

性质五

一棵n个结点的完全二叉树，对任一个结点(编号为i)，有：如果i=1，则结点i为根，无父结点；如果i>1,则其父结点编号为floor（i/2），如果i为父节点编号，那么2*i是左孩子，2*i+1是右孩子。

图A-满二叉树

图B-完全二叉树

编号示意图

遍历

二叉树的遍历是指按一定的规律和次序访问树中的各个结点。

遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。

先序遍历

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

访问根结点、先序遍历左子树、先序遍历右子树

void preorder(tree bt)//先序递归算法
{
    if(bt)
    {  
        cout << bt->data;
        preorder(bt->lchild);
        preorder(bt->rchild);
    }
}

先序遍历此图结果为：124753689

中序遍历

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

中序遍历左子树、访问根结点、中序遍历右子树

void inorder(tree bt)//中序遍历递归算法
{
    if(bt)
    {  
        inorder(bt->lchild);
        cout << bt->data;
        inorder(bt->rchild);
    }
}

中序遍历上图结果为：742513869

后序遍历

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

后序遍历左子树、后序遍历右子树、访问根结点

void postorder(tree bt)//后序递归算法
{
    if(bt)
    {  
        postorder(bt->lchild);
        postorder(bt->rchild);
        cout << bt->data;
    }
}

后序遍历上图结果为：745289631

已知先序序列和中序序列可唯一确定一棵二叉树；

已知中序序列和后序序列可唯一确定一棵二叉树；

已知先序序列和后序序列不可唯一确定一棵二叉树；

二叉树操作（建树、删除、输出）

普通树转二叉树

由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。

通用法则：“左孩子，右兄弟”

建树

删除树

插入一个结点到排序二叉树中

在排序二叉树中查找一个数

相关题目

扩展二叉树

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用“.”补齐，称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

输入样例：

ABD..EF..G..C..

输出样例：

DBFEGAC

DFGEBCA

二叉树的建立和输出

以二叉链表作存储结构，建立一棵二叉树，并输出该二叉树的先序、中序、后序遍历序列、高度和结点总数。

输入样例：

12##3##

//#为空

输出样例：

123

//先序排列

213

//中序排列

231

//后序排列

//高度

//结点总数

因为本蒟蒻不太会用指针，所以自己写了一个不带指针的，代码很丑，见谅QwQ

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

int top,maxh;
char s;

struct t{
	int data,father,lson=0,rson=0,h=0;
}tree[100005];

void build(int father,bool right){
	cin>>s;
	if(s=="
")
	return;
	if(s!="#"){
		++top;
		int t=top;
		tree[t].father=father;
		tree[t].data=s-"0";
		tree[t].h=tree[father].h+1;
		maxh=max(tree[t].h,maxh);
		
		if(right==1)
		tree[father].rson=t;
		else
		tree[father].lson=t;
		
		build(t,0);
		build(t,1);
	}
	else return;
}

void xian(int now){
	cout<<tree[now].data;
	if(tree[now].lson!=0)
	xian(tree[now].lson);
	if(tree[now].rson!=0)
	xian(tree[now].rson);
}

void zhong(int now){
	if(tree[now].lson!=0)
	zhong(tree[now].lson);
	cout<<tree[now].data;
	if(tree[now].rson!=0)
	zhong(tree[now].rson);
}

void hou(int now){
	if(tree[now].lson!=0)
	hou(tree[now].lson);
	if(tree[now].rson!=0)
	hou(tree[now].rson);
	cout<<tree[now].data;
}

int main(){
	build(0,0);
//	for(int i=1;i<=top;i++){
//		cout<<tree[i].data<<" "<<tree[i].father<<" ";
//		cout<<tree[i].lson<<" "<<tree[i].rson<<" ";
//		cout<<tree[i].h<<endl;;
//	}
	xian(1);
	cout<<"
";
	zhong(1);
	cout<<"
";
	hou(1);
	cout<<"
";
	cout<<maxh<<"
"<<top<<"
";
	return 0;
}

P1030 求先序排列

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入：

2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出：

1行，表示一棵二叉树的先序。

输入样例：

BADC

BDCA

输出样例：

ABCD

分析
中序为BADC，后序为BDCA，所以A为根结点，B、DC分别为左右子树的中序序列，B、DC分别为左右子树的后序序列。然后再递归处理中序为B，后序为B的子树和中序为DC，后序为DC的子树。

求后序排列

输入：

二叉树的前序序列与中序序列

输出：

二叉树的后序序列

样例输入：

abcdefg

cbdafeg

样例输出：

cdbfgea

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
char qian[100005],zhong[100005];
int q[100005],z[100005],a[100005],cnt=0;
void find(int start,int end){
	if(start>end){
		return;
	}
	cnt++;
	if(start==end){
		cout<<char(z[q[cnt]]+"a"-1);
		return;
	}
	int t=cnt;
	find(start,q[t]-1);
	find(q[t]+1,end);
	cout<<char(z[q[t]]+"a"-1);
}
int main(){
	cin>>qian>>zhong;
	int len=strlen(qian);
	for(int i=0;i<len;i++){
		a[zhong[i]-"a"]=i;
	}
	for(int i=0;i<len;i++){
		z[i+1]=zhong[i]-"a"+1;
		q[i+1]=a[qian[i]-"a"]+1;
	}
	find(1,strlen(qian));
	return 0;
}

因为有小可爱说我的代码在输入时的处理不清楚，所以又写了一个版本QwQ

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
char qian[100005],zhong[100005];
int q[100005],z[100005],a[100005],cnt=0;
void find(int start,int end){
//	cout<<endl<<"*"<<start<<" "<<end<<"*"<<endl;
	if(start>end){
		return;
	}
	cnt++;
	if(start==end){
		cout<<char(z[q[cnt]]+"a"-1);
		return;
	}
	int t=cnt;
	find(start,q[t]-1);
	find(q[t]+1,end);
	cout<<char(z[q[t]]+"a"-1);
}
int main(){
//	cin>>qian+1>>zhong+1;
	scanf("%s%s",qian+1,zhong+1);//这里的输入下标从1开始
	int len=strlen(qian+1);
	for(int i=1;i<=len;i++){
		a[zhong[i]-"a"]=i;
	}
	for(int i=1;i<=len;i++){
		z[i]=zhong[i]-"a"+1;
		q[i]=a[qian[i]-"a"];
	}
	find(1,len);
	return 0;
}

补充

表达式树

关于表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如，对于下图的遍历结果如下，它们对应着表达式的3种表示方法。

-+a*b-cd/ef (前缀表示、波兰式)

a+b*(c-d)-e/f (中缀表示)

abcd-*+ef/- (后缀表示、逆波兰式)

哈夫曼树

QwQ，不是很会，那就推荐一篇博客吧。

hmoban主题是根据ripro二开的主题，极致后台体验，无插件，集成会员系统
自学咖网 » 树型结构

wen 普通

分享到：

wen 普通

相关推荐