文章目录

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

🎆🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎆
今天我要开启一个新计划----【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

代码

#include 
using 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<

#include 
using 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<