【C++天梯计划】1.10二叉树(binarytree)-创新互联

文章目录
    • 什么是二叉树?
    • 二叉树的定义
    • 二叉树的基本形态
    • 二叉树的性质
    • 例题1:二叉树的遍历
        • 题目描述
        • 输入
        • 输出
        • 样例
        • 代码
    • 例题2:哈夫曼树
        • 题目描述
        • 输入
        • 输出
        • 样例
        • 代码

成都创新互联是一家专注于网站制作、成都网站设计与策划设计,龙岩网站建设哪家好?成都创新互联做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:龙岩等地区。龙岩做网站价格咨询:18982081108

🎆🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎆
今天我要开启一个新计划----【C++天梯计划】
目的是通过天梯计划,通过题目和知识点串联的方式,完成C++复习与巩固。

什么是二叉树?

二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分 。
二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个节点 。

二叉树的定义

二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树 。

二叉树的基本形态

二叉树是递归定义的,其节点有左右子树之分,逻辑上二叉树有五种基本形态
1、空二叉树——如图(1)
2、只有一个根节点的二叉树——如图(2)
3、只有左子树——如图(3)
4、只有右子树——如图(4)
5、完全二叉树——如图(5)

1-----------2-----------------3---------------4------------------5

二叉树的性质

性质1: 二叉树的第i层上至多有2i-1(i≥1)个节点 [6] 。
性质2: 深度为h的二叉树中至多含有2h-1个节点 [6] 。
性质3: 若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1 [6] 。
性质4: 具有n个节点的满二叉树深为log2n+1。
性质5: 若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的节点:
当i=1时,该节点为根,它无双亲节点。
当i>1时,该节点的双亲节点的编号为i/2 。
若2i≤n,则有编号为2i的左节点,否则没有左节点。
若2i+1≤n,则有编号为2i+1的右节点,否则没有右节点 。

例题1:二叉树的遍历
题目描述

给出一个 nn 个结点的二叉树,请求出二叉树的前序遍历,中序遍历和后序遍历。

输入

第一行有一个整数 nn (0< n ≤ 260以下 nn 行,每行第一个为一个大写字母表示结点的值,第 i+1i+1 行的结点编号为 ii ;
后面为两整数,第一个表示该结点左孩子结点编号,第二个表示该结点右孩子的结点编号,如果该编号为 00 表示没有;(编号为 11 的结点是树的根)

输出

共三行,第一行为二叉树的前序遍历,第二行为中序遍历,第三行为后序遍历;

样例

输入
7
F 2 3
C 4 5
E 0 6
A 0 0
D 7 0
G 0 0
B 0 0
输出
FCADBEG
ACBDFEG
ABDCGEF

代码
#includeusing namespace std;
//1.用孩子表示法,存储二叉树
//2.用递归的方法得到先序中序后序遍历的结果 
const int N = 30;
struct node{char c;
	int lc,rc;//左右孩子 
}a[N]; 
int n;

//前序遍历:根左右 
void dfs1(int x){cout<if(a[x].lc) dfs2(a[x].lc);
	cout<if(a[x].lc) dfs3(a[x].lc);
	if(a[x].rc) dfs3(a[x].rc);
	cout<cin>>n;
	//读入结点
	for(int i = 1;i<= n;i++){cin>>a[i].c>>a[i].lc>>a[i].rc;
	} 
	
	//深搜
	//前序遍历
	dfs1(1);	
	cout<
例题2:哈夫曼树
题目描述

哈夫曼树的定义是:一棵具有 nn 个带权叶结点的二叉树,使得所有叶结点的带权路径长度(叶结点 ×× 叶结点到根结点的路径长度)之和最小,这样的二叉树被称为最优二叉树,也称哈夫曼树。
在这里插入图片描述
比如:有 44 个结点的权值是55 44 22 99,可以构建出如下三颗不同的二叉树,第 22 棵二叉树的带权路径长度是最小的。
请读入一个整数 nn ,代表叶结点的数量,再读入 nn 个整数,代表叶结点的权值,请求出对应哈夫曼树的带权路径长度。

输入

输入的第一行包含一个正整数 nn(n≤100n≤100)。
接下来是 nn 个正整数,表示 nn 个叶结点的权值,每个数不超过 10001000 。

输出

输出构造出的哈夫曼树的带权路径长度。

样例

输入
5
5 3 8 2 9
输出
59

代码
#includeusing namespace std;
//思路:使用优先队列模拟哈夫曼树的构建过程
//小根堆 
priority_queue,greater>q; 
int n,x,ans = 0;//ans:代表哈夫曼树的WPL的值 
 
int main(){cin>>n;
	//读入n个元素 
	while(n--){cin>>x;
		q.push(x);
	}
	
	//当队列中超过1个元素
	//获取队列头部的2个最小的元素
	int a,b; 
	while(q.size() >1){a = q.top();
		q.pop();
		b = q.top();
		q.pop();
		
		ans += a + b;
		q.push(a+b);
	} 
	
	cout<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前标题:【C++天梯计划】1.10二叉树(binarytree)-创新互联
URL链接:http://cdiso.cn/article/dhphsc.html