自己弄个网站要怎么弄,网页制作团队,中国新闻社,怎么建立微信公众号平台文章目录 1 二叉树概念2 二叉树的存储和编码2.1 二叉树的存储方法2.2 二叉树存储的编码实现2.3 二叉树的极简存储方法 3 例题4 习题 前面介绍的数据结构数组、队列、栈#xff0c;都是线性的#xff0c;它们存储数据的方式是把相同类型的数据按顺序一个接一个串在一起。简单的… 文章目录 1 二叉树概念2 二叉树的存储和编码2.1 二叉树的存储方法2.2 二叉树存储的编码实现2.3 二叉树的极简存储方法 3 例题4 习题 前面介绍的数据结构数组、队列、栈都是线性的它们存储数据的方式是把相同类型的数据按顺序一个接一个串在一起。简单的形态使线性表难以实现高效率的操作。
二叉树是一种层次化的、高度组织性的数据结构。二叉树的形态使得它有天然的优势在二叉树上做查询、插入、删除、修改、区间等操作极为高效基于二叉树的算法也很容易实现高效率的计算。
1 二叉树概念
二叉树的每个节点最多有两个子节点分别称为左孩子、右孩子以它们为根的子树称为左子树、右子树。二叉树的每一层以2的倍数递增所以二叉树的第k层最多有 2 k − 1 2^{k-1} 2k−1 个节点。根据每一层的节点分布情况有以下常见的二叉树。
1满二叉树
特征是每一层的节点数都是满的。第一层只有1个节点编号为1第二层有2个节点编号2、3第三层有4个节点编号4、5、6、7…第k层有 2 k − 1 2^{k-1} 2k−1 个节点编号 2 k − 1 2^{k-1} 2k−1、 2 k − 1 1 2^{k-1}1 2k−11、…、 2 k − 1 2^k-1 2k−1。
一棵n层的满二叉树节点一共有 1 2 4 . . . 2 n − 1 2 n − 1 124...2^{n-1} 2^{n-1} 124...2n−12n−1 个。 2完全二叉树
如果满二叉树只在最后一层有缺失并且缺失的节点都在最后称为完全二叉树。上图演示了一棵满二叉树和一棵完全二叉树。
3平衡二叉树
任意左子树和右子树的高度差不大于1称为平衡二叉树。若只有少部分子树的高度差超过1这是一棵接近平衡的二叉树。 4退化二叉树
如果树上每个节点都只有1个孩子称为退化二叉树。退化二叉树实际上已经变成了一根链表。如果绝大部分节点只有1个孩子少数有2个孩子也看成退化二叉树。
二叉树之所以应用广泛得益于它的形态。高级数据结构大部分和二叉树有关下面列举二叉树的一些优势。
1在二叉树上能进行极高效率的访问。一棵平衡的二叉树例如满二叉树或完全二叉树每一层的节点数量约是上一层数量的2倍也就是说一棵有N个节点的满二叉树树的高度是O(logN)。从根节点到叶子节点只需要走logN步例如N 100万树的高度仅有logN 20只需要20步就能到达100万个节点中的任意一个。但是如果二叉树不是满的而且很不平衡甚至在极端情况下变成退化二叉树访问效率会打折扣。维护二叉树的平衡是高级数据结构的主要任务之一。
2二叉树很适合做从整体到局部、从局部到整体的操作。二叉树内的一棵子树可以看成整棵树的一个子区间求区间最值、区间和、区间翻转、区间合并、区间分裂等用二叉树都很快捷。
3基于二叉树的算法容易设计和实现。例如二叉树用BFS和DFS搜索处理都极为简便。二叉树可以一层一层地搜索这是BFS。二叉树的任意一个子节点是以它为根的一棵二叉树这是一种递归的结构用DFS访问二叉树极容易编码。
2 二叉树的存储和编码
2.1 二叉树的存储方法
要使用二叉树首先得定义和存储它的节点。
二叉树的一个节点包括三个值节点的值、指向左孩子的指针、指向右孩子的指针。需要用一个结构体来定义二叉树。
二叉树的节点有动态和静态两种存储方法竞赛中一般采用静态方法。
1动态存储二叉树。例如写c代码数据结构的教科书一般这样定义二叉树的节点
struct Node{int value; //节点的值可以定义多个值Node *lson, *rson; //指针分别指向左右子节点
};其中value是这个节点的值lson和rson是指向两个孩子的指针。动态新建一个Node时用new运算符动态申请一个节点。使用完毕后需要用delete释放它否则会内存泄漏。动态二叉树的优点是不浪费空间缺点是需要管理不小心会出错竞赛中一般不这样用。
2用静态数组存储二叉树。在算法竞赛中为了编码简单加快速度一般用静态数组来实现二叉树。下面定义一个大小为N的结构体数组。N的值根据题目要求设定有时节点多例如N100万那么tree[N]使用的内存是12M字节不算大。
struct Node{ //静态二叉树int value; //可以把value简写为vint lson, rson; //左右孩子可以把lson、rson简写为ls、rs
}tree[N]; //可以把tree简写为ttree[i]表示这个节点存储在结构体数组的第i个位置lson是它的左孩子在结构体数组的位置rson是它的右孩子在结构体数组的位置。lson和rson指向孩子的位置也可以称为指针。
下图演示了一棵二叉树的存储圆圈内的字母是这个节点的value值。根节点存储在tree[5]上它的左孩子lson7表示左孩子存储在tree[7]上右孩子rson3存储在tree[3]。
编码时一般不用tree[0]因为0常常被用来表示空节点例如叶子节点tree[2]没有子节点就把它的子节点赋值为lson rson 0。
2.2 二叉树存储的编码实现
下面写代码演示上图中二叉树的建立并输出二叉树。
1C代码。第16~21行建立二叉树然后用print_tree()输出二叉树。
#include bits/stdc.h
using namespace std;
const int N100; //注意const不能少
struct Node{ //定义静态二叉树结构体char v; //把value简写为vint ls, rs; //左右孩子把lson、rson简写为ls、rs
}t[N]; //把tree简写为t
void print_tree(int u){ //打印二叉树if(u){coutt[u].v ; //打印节点u的值print_tree(t[u].ls); //继续搜左孩子print_tree(t[u].rs); //继续搜右孩子}
}
int main(){t[5].vA; t[5].ls7; t[5].rs3;t[7].vB; t[7].ls2; t[7].rs0;t[3].vC; t[3].ls9; t[3].rs6;t[2].vD; // t[2].ls0; t[2].rs0; 可以不写因为t[]是全局变量已初始化为0t[9].vE; // t[9].ls0; t[9].rs0; 可以不写t[6].vF; // t[6].ls0; t[6].rs0; 可以不写int root 5; //根是tree[5]print_tree(5); //输出 A B D C E Freturn 0;
}初学者可能看不懂print_tree()是怎么工作的。它是一个递归函数先打印这个节点的值t[u].v然后继续搜它的左右孩子。上图的打印结果是”A B D C E F”步骤如下 1首先打印根节点A 2然后搜左孩子是B打印出来 3继续搜B的左孩子是D打印出来 4D没有孩子回到BB发现也没有右孩子继续回到A 5A有右孩子C打印出来 6打印C的左右孩子E、F。
这个递归函数执行的步骤称为“先序遍历”先输出父节点然后再搜左右孩子并输出。还有“中序遍历”和“后序遍历”将在后面讲解。
2Java代码
import java.util.*;
class Main {static class Node {char v;int ls, rs;}static final int N 100;static Node[] t new Node[N];static void print_tree(int u) {if (u ! 0) {System.out.print(t[u].v );print_tree(t[u].ls);print_tree(t[u].rs);}}public static void main(String[] args) {t[5] new Node(); t[5].v A; t[5].ls 7; t[5].rs 3;t[7] new Node(); t[7].v B; t[7].ls 2; t[7].rs 0;t[3] new Node(); t[3].v C; t[3].ls 9; t[3].rs 6;t[2] new Node(); t[2].v D;t[9] new Node(); t[9].v E;t[6] new Node(); t[6].v F;int root 5;print_tree(5); // 输出 A B D C E F}
}3Python代码
N 100
class Node: # 定义静态二叉树结构体def __init__(self):self.v # 把value简写为vself.ls 0 # 左右孩子把lson、rson简写为ls、rsself.rs 0
t [Node() for i in range(N)] # 把tree简写为t
def print_tree(u):if u:print(t[u].v, end ) # 打印节点u的值print_tree(t[u].ls)print_tree(t[u].rs)
t[5].v, t[5].ls, t[5].rs A, 7, 3
t[7].v, t[7].ls, t[7].rs B, 2, 0
t[3].v, t[3].ls, t[3].rs C, 9, 6
t[2].v D # t[2].ls0; t[2].rs0; 可以不写因为t[]已初始化为0
t[9].v E # t[9].ls0; t[9].rs0; 可以不写
t[6].v F # t[6].ls0; t[6].rs0; 可以不写
root 5 # 根是tree[5]
print_tree(5) # 输出 A B D C E F2.3 二叉树的极简存储方法
如果是满二叉树或者完全二叉树有更简单的编码方法连lson、rson都不需要定义因为可以用数组的下标定位左右孩子。
一棵节点总数量为k的完全二叉树设1号点为根节点有以下性质
1 p 1 p 1 p1的节点其父节点是 ⌊ p / 2 ⌋ \lfloor p/2 \rfloor ⌊p/2⌋。例如 p 4 p4 p4父亲是 4 / 2 2 4/22 4/22 p 5 p5 p5父亲是 5 / 2 2 5/22 5/22。 2如果 2 × p k 2×p k 2×pk那么 p p p没有孩子如果 2 × p 1 k 2×p1 k 2×p1k那么 p p p没有右孩子。例如 k 11 k11 k11 p 6 p6 p6的节点没有孩子 k 12 k12 k12 p 6 p6 p6的节点没有右孩子。 3如果节点 p p p有孩子那么它的左孩子是 2 × p 2×p 2×p右孩子是 2 × p 1 2×p1 2×p1。
图中圆圈内是节点的值圆圈外数字是节点存储位置。
1C代码。
用 l s ( p ) ls(p) ls(p)找p的左孩子用 r s ( p ) rs(p) rs(p)找p的右孩子。 l s ( p ) ls(p) ls(p)中把 p ∗ 2 p*2 p∗2写成 p 1 p1 p1用了位运算。
#include bits/stdc.h
using namespace std;
const int N100; //注意const不能少
char t[N]; //简单地用一个数组定义二叉树
int ls(int p){return p1;} //定位左孩子也可以写成 p*2
int rs(int p){return p1 | 1;} //定位右孩子也可以写成 p*21
int main(){t[1]A; t[2]B; t[3]C;t[4]D; t[5]E; t[6]F; t[7]G;t[8]H; t[9]I; t[10]J; t[11]K;coutt[1]:lsont[ls(1)] rsont[rs(1)]; //输出 A:lsonB rsonCcoutendl;coutt[5]:lsont[ls(5)] rsont[rs(5)]; //输出 E:lsonJ rsonKreturn 0;
}2Java代码。
import java.util.Arrays;
public class Main {static int ls(int p){ return p1;}static int rs(int p){ return p1 | 1;}public static void main(String[] args) {final int N 100;char[] t new char[N];t[1]A; t[2]B; t[3]C;t[4]D; t[5]E; t[6]F; t[7]G;t[8]H; t[9]I; t[10]J; t[11]K;System.out.print(t[1]:lsont[ls(1)] rsont[rs(1)]);//输出A:lsonB rsonCSystem.out.println();System.out.print(t[5]:lsont[ls(5)] rsont[rs(5)]);//输出E:lsonJ rsonK}
}3Python代码。
N 100
t [] * N
def ls(p): return p 1
def rs(p): return (p 1) | 1t[1] A; t[2] B; t[3] C
t[4] D; t[5] E; t[6] F; t[7] G
t[8] H; t[9] I; t[10] J; t[11] Kprint(t[1] :lson t[ls(1)] rson t[rs(1)]) # 输出 A:lsonB rsonC
print(t[5] :lson t[ls(5)] rson t[rs(5)]) # 输出 E:lsonJ rsonK其实即使二叉树不是完全二叉树而是普通二叉树也可以用这种简单方法来存储。如果某个节点没有值那就空着这个节点不用方法是把它赋值为一个不该出现的值例如赋值为0或无穷大INF。这样会浪费一些空间好处是编程非常简单。
3 例题
二叉树是很基本的数据结构大量算法、高级数据结构都是基于二叉树的。二叉树有很多操作最基础的操作是搜索遍历二叉树的每个节点有先序遍历、中序遍历、后序遍历。这3种遍历都用到了递归函数二叉树的形态天然适合用递归来编程。
1先父序遍历父节点在最前面输出。先输出父节点再访问左孩子最后访问右孩子。上图的先序遍历结果是ABDCEF。为什么把结果分解为A-BD-CEF。父亲是A然后是左孩子B和它带领的子树BD最后是右孩子C和它带领的子树CEF。这是一个递归的过程每个子树也满足先序遍历例如CEF父亲是C然后是左孩子E最后是右孩子F。
2中父序遍历父节点在中间输出。先访问左孩子然后输出父节点最后访问右孩子。上图的中序遍历结果是DBAECF。为什么把结果分解为DB-A-ECF。DB是左子树然后是父亲A最后是右子树ECF。每个子树也满足中序遍历例如ECF先左孩子E然后是父亲C最后是右孩子F。
3后父序遍历父节点在最后输出。先访问左孩子然后访问右孩子最后输出父节点。上图的后序遍历结果是DBEFCA。为什么把结果分解为DB-EFC-A。DB是左子树然后是右子树EFC最后是父亲A。每个子树也满足后序遍历例如EFC先左孩子E然后是右孩子F最后是父亲C。
这三种遍历中序遍历是最有用的它是二叉查找树的核心。
例题 二叉树的遍历
1C代码
#include bits/stdc.h
using namespace std;
const int N 100005;
struct Node{int v; int ls, rs;
}t[N]; //tree[0]不用0表示空结点
void preorder (int p){ //求先序序列if(p ! 0){cout t[p].v ; //先序输出preorder (t[p].ls);preorder (t[p].rs);}
}
void midorder (int p){ //求中序序列if(p ! 0){midorder (t[p].ls);cout t[p].v ; //中序输出midorder (t[p].rs);}
}
void postorder (int p){ //求后序序列if(p ! 0){postorder (t[p].ls);postorder (t[p].rs);cout t[p].v ; //后序输出}
}
int main() {int n; cin n;for (int i 1; i n; i) {int a, b; cin a b;t[i].v i;t[i].ls a;t[i].rs b;}preorder(1); cout endl;midorder(1); cout endl;postorder(1); cout endl;
}2Java代码
下面的Java代码和上面的C代码略有不同。例如在preorder()中没有直接打印节点的值而是用joiner.add()先记录下来遍历结束后一起打印这样快一些。本题 n 1 0 6 n10^6 n106 规模大时间紧张。
import java.util.Scanner;
import java.util.StringJoiner;
class Main {static class Node {int v, ls, rs;Node(int v, int ls, int rs) {this.v v;this.ls ls;this.rs rs;}}static final int N 100005;static Node[] t new Node[N]; //tree[0]不用0表示空结点static void preorder(int p, StringJoiner joiner) { //求先序序列if (p ! 0) {joiner.add(t[p].v ); //不是直接打印而是先记录下来preorder(t[p].ls,joiner);preorder(t[p].rs,joiner);}}static void midorder(int p, StringJoiner joiner) { //求中序序列if (p ! 0) {midorder(t[p].ls,joiner);joiner.add(t[p].v );//中序输出midorder(t[p].rs,joiner);}}static void postorder(int p, StringJoiner joiner) { //求后序序列if (p ! 0) {postorder(t[p].ls,joiner);postorder(t[p].rs,joiner);joiner.add(t[p].v ); //后序输出}}public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();for (int i 1; i n; i) {int a sc.nextInt(), b sc.nextInt();t[i] new Node(i, a, b);}StringJoiner joiner new StringJoiner( ); preorder(1, joiner); System.out.println(joiner); joiner new StringJoiner( );midorder(1, joiner); System.out.println(joiner);joiner new StringJoiner( );postorder(1, joiner); System.out.println(joiner);}
}3Python代码
N 100005
t [0] * N # tree[0]不用0表示空结点
class Node:def __init__(self, v, ls, rs):self.v vself.ls lsself.rs rsdef preorder(p): # 求先序序列if p ! 0:print(t[p].v, end ) # 先序输出preorder(t[p].ls)preorder(t[p].rs)def midorder(p): # 求中序序列if p ! 0:midorder(t[p].ls)print(t[p].v, end ) # 中序输出midorder(t[p].rs)def postorder(p): # 求后序序列if p ! 0:postorder(t[p].ls)postorder(t[p].rs)print(t[p].v, end ) # 后序输出n int(input())
for i in range(1, n1):a, b map(int, input().split())t[i] Node(i, a, b)preorder(1); print()
midorder(1); print()
postorder(1); print()4 习题
完全二叉树的权值
FBI树
American Heritage
求先序排列
