【数据结构】树和二叉树
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
半山腰很挤你得去山顶看看
目录
1.树
1.1 树的概念
树是一种非线性的数据结构它是由 nn>=0个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
- 有一个特殊的节点称为根节点根节点没有前驱结点但可以有后继节点
- 除了根节点以外其他结点都有唯一的前驱所有的结点都可以有0个或多个后继节点
- 树是递归定义的
1.2 树的特征
- 子树不相交
- 除了根结点以外每个结点都有且只有一个父结点根节点没有父结点
- 一棵N个结点的树有N-1条边
当树不满足上述的树的特征时则就不是树
1.3 树每个结点的关系
节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6
树的度一棵树中最大的节点的度称为树的度 如上图树的度为6
叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I...等节点为叶节点
非终端节点或分支节点度不为0的节点 如上图D、E、F、G...等节点为分支节点
双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B 的父节点
孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节 点
兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点
节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推
树的高度或深度树中节点的最大层次 如上图树的高度为4
节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先
子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙
森林由mm>0棵互不相交的多颗树的集合称为森林
1.4 树的表示形式
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式 如双亲表示法孩子兄弟表示法、孩子表示法等等。
这里我们就简单了解一下双亲表示法和孩子兄弟表示法
双亲表示法
双亲表示法就是将每个节点的双亲节点父节点存储在数组中根节点没有父节点直接存储 -1 因为数组没有 -1 下标
孩子兄弟表示法
孩子兄弟表示法每个节点都有数据域、孩子域、兄弟域要是一个节点有多个孩子节点那就让它的孩子域指向第一个孩子节点它的第一个孩子节点跟它的第二个孩子节点又是兄弟关系那么第一个孩子节点的兄弟域指向第二个孩子节点第二个孩子节点又跟第三个孩子节点又是兄弟关系让第二个孩子节点的兄弟域指向第三个孩子节点依次这样。
2.二叉树
2.1 二叉树的概念
概念一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成
- 每个结点最多有两棵子树左、右子树即二叉树不存在度大于2的节点。度最多为2
- 二叉树的子树有左右之分其子树的次序不能颠倒。
注当一棵树的每个节点的度小于或等于二时此树都为二叉树。当没有节点时也为二叉树
二叉树每个节点只可能为以下几种情况
2.2 特殊的二叉树
满二叉树一个二叉树如果每一个层的节点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为 h且结点总数是 (2^h) -1 则它就是满二叉树
完全二叉树一棵二叉树的高度为 h当它的 h-1 层都是满的。最后一层不是满的但是最后一层从左往右是连续的这样的一颗二叉树便是完全二叉树满二叉树是特殊的完全二叉树
2.3 二叉树的性质
- 若规定根节点的层数为1则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点
- 若规定根节点的层数为1则深度为 h 的二叉树的最大结点数是 (2^h)- 1
- 对任何一棵二叉树, 如果度为0的叶结点个数为 n0, 度为2的分支结点个数为 n2,则有 n0=n2 +1
- 若规定根节点的层数为1具有 n 个结点的满二叉树的深度h为 h=log₂n+1
- 具有n个结点的完全二叉树的深度h为 h=log₂(n+1)上取整
- 将一个完全二叉树从上至下从左至右的顺序依次存储在数组除了根节点也就是0下标的节点外,其他节点的父节点都为 (下标-1)/2。所有节点的左孩子节点为 下标*2+1右孩子节点为 下标*2+2
2.4 二叉树的存储
二叉树的存储通常分为顺序存储和链式存储
- 顺序存储通常用于完全二叉树
- 链式存储通常通过一个节点的左、右、双亲节点域引用其他节点
孩子表示法就是用两个节点域分别存储此节点的左右孩子节点
//孩子表示法
public class Node {
private int val;//数据
private Node left;//左孩子
private Node right;//右孩子
}
孩子双亲表示法就是用三个节点域分别存储此节点的左右双亲节点
//孩子双亲表示法
public class Node {
private int val;//数据
private Node left;//左孩子
private Node right;//右孩子
private Node parent; // 当前节点的双亲节点
}
2.5 二叉树的基本操作
首先我们先写一个对二叉树基本操作的类
public class MyBinaryTree {
}
二叉树是由节点构造的所以需要在MyBinaryTree类中写一个内部类当做节点类
//树的节点
public class Node {
private int val;//数据
private Node left;//左孩子
private Node right;//右孩子
private Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node{" +
"节点=" + val +
", 左子节点=" + left.val +
", 右子节点=" + right.val +
'}';
}
}
要对二叉树进行基本操作首先需要有一颗二叉树那么我们就先在MyBinaryTree类中写一个方法创建一棵固定的二叉树
//构造一棵二叉树
public Node createBinaryTree() {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
return node1;
}
有了一棵二叉树后我们就可以完成二叉树的基本操作
2.5.1 判断二叉树是否为空
直接判断传过来的根节点是否为null如果为null则是空树否则不是空树
//判断二叉树是否为空
public boolean isEmpty(Node root) {
return root == null;
}
2.5.2 二叉树的前序遍历
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则无法继续往下遍历直接 return。不为空就打印传过来的节点然后采用递归遍历左子树和右子树
- 判断节点是否为空 节点为空 return
- 节点不为空打印节点值
- 递归左节点
- 递归右节点
//前序遍历
public void preOrder(Node root) {
if (isEmpty(root)) {
return;
}
//节点不为空打印val值
System.out.print(root.val+" ");
//访问左子树
preOrder(root.left);
//访问右子树
preOrder(root.right);
}
2.5.3 二叉树的中序遍历
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则无法继续往下遍历直接 return。不为空采用递归遍历左子树再打印节点的值然后采用递归遍历右子树
- 判断节点是否为空 节点为空 return
- 节点不为空递归左节点
- 打印节点值
- 递归右节点
//中序遍历
public void inOrder(Node root) {
if (isEmpty(root)) {
return;
}
//先访问左子树
inOrder(root.left);
//当左子树遍历完返回时打印val值
System.out.print(root.val+" ");
//再访问右子树
inOrder(root.right);
}
2.5.4 二叉树的后序遍历
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则无法继续往下遍历直接 return。不为空采用递归遍历左子树再采用递归遍历右子树然后打印节点的值
- 判断节点是否为空 节点为空 return
- 节点不为空递归左节点
- 递归右节点
- 打印节点值
//后序遍历
public void postOrder(Node root) {
if (isEmpty(root)) {
return;
}
//先访问左子树
inOrder(root.left);
//再访问右子树
inOrder(root.right);
//当左子树和右子树都访问完后打印val
System.out.print(root.val+" ");
}
2.5.5 获取二叉树的节点个数
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接返回 0。不为空就递归左子树、然后递归右子树当递归为null返回时将左子树的节点个数+右子树的节点个数+本身的节点个数
// 获取树中节点的个数
public int size(Node root) {
if(isEmpty(root)) {
return 0;
}
//将遍历的左子树右子树加起来然后再加上本身的一个节点
return size(root.left) + size(root.right) + 1;
}
2.5.6 获取二叉树的叶子节点个数
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接返回 0。不为空就判断它的左节点和右节点是否为空如果为空返回1如果不为空就递归它的左子树和右子树然后将它左子树和右子树的叶子节点个数加起来即可
// 获取叶子节点的个数
public int getLeafNodeCount(Node root) {
if (isEmpty(root)) {
return 0;
}
//如果一个节点的左子树和右子树都为null说明这个节点就是叶子节点
if (root.left == null && root.right == null) {
return 1;
}
//将返回的叶子节点加起来
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
2.5.7 获取二叉树指定层的节点个数
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接返回 0。不为空就递归到第 k 层如果第 k 层的节点不为空就返回1如果为空就返回0将返回的第k层的节点个数加起来即可
// 获取第K层节点的个数
public int getKLevelNodeCount(Node root,int k) {
if (isEmpty(root)) {
return 0;
}
//当k=1时就是我们要获取的第k层的节点个数
if (k == 1) {
return 1;
}
//递归到第k层
return getKLevelNodeCount(root.left, k - 1)
+ getKLevelNodeCount(root.right, k - 1);
}
2.5.8 获取二叉树的高度
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接返回 0。不为空就遍历它的左子树和右子树然后判断左子树和右子树谁的节点多多的子树加上本节点返回给上一层
// 获取二叉树的高度
public int getHeight(Node root) {
if (isEmpty(root)) {
return 0;
}
//遍历左子树
int left = getHeight(root.left);
//遍历右子树
int right = getHeight(root.right);
//判断左子树和右子树谁的节点多多的子树加上本节点返回给上一层
return left >= right ? left+1 : right+1;
}
2.5.9 检测值为value的元素是否存在
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接返回 null。不为空就判断这个节点的 val 值是否是我们要找的 value如果是则不需要再递归直接返回这个节点如果整棵树都遍历完了则没有这个节点则会返回null
// 检测值为value的元素是否存在
public Node find(Node root, int value) {
if (isEmpty(root)) {
return null;
}
//当元素存在直接返回这个元素的节点
if (root.val == value) {
return root;
}
//访问左子树
Node nodeL = find(root.left,value);
if (nodeL != null) {
return nodeL;
}
//访问右子树
Node nodeR = find(root.right,value);
if (nodeR != null) {
return nodeR;
}
//如果没有这个节点就返回null
return null;
}
2.5.10 二叉树的层序遍历
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接return。不为空就实例化一个队列队列先进先出将节点放入队列中判断队列不为空就进入循环从队列中出一个元素放入临时变量tmp中然后打印 tmp 节点的 val 值如果tmp节点的左节点不为空就入队如果tmp节点的右节点不为空就入队依次这样循环直到队列为空跳出循环
//层序遍历
public void levelOrder(Node root) {
if(isEmpty(root)) {
return;
}
//用队列存储节点
Queue<Node> queue = new LinkedList<>();
//将第一个节点放入队列中
queue.offer(root);
//当队列不为空就进入循环
while (!queue.isEmpty()) {
//弹出队列的队头元素
Node tmp = queue.poll();
//打印队头元素的值
System.out.print(tmp.val+" ");
//如果弹出的这个元素的左节点不为空就入队列
if (!isEmpty(tmp.left)) {
queue.offer(tmp.left);
}
//如果弹出的这个元素的右节点不为空就入队列
if (!isEmpty(tmp.right)) {
queue.offer(tmp.right);
}
}
System.out.println();
}
2.5.11 判断一棵二叉树是不是完全二叉树
首先我们得调用 isEmpty 方法判断传过来的节点是否为空如果为空则没有节点直接返回true。不为空就实例化一个队列队列先进先出将节点放入队列中判断队列不为空就进入循环从队列中出一个元素放入临时变量tmp中判断tmp中的节点是否为null如果tmp的节点为空则将队列中的节点挨个出并判断出的节点是否都为null 如果有一个不为null则就不是完成二叉树直接返回false。如果tmp中的节点不为null则将这个节点的左右节点都入队。当队列为空不进入循环时则为完全二叉树返回true
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(Node root) {
if (isEmpty(root)) {
return true;
}
//用队列存储节点
Queue<Node> queue = new LinkedList<>();
//将第一个节点放入队列中
queue.offer(root);
//队列不为空进循环
while (!queue.isEmpty()) {
//弹出队列的队头节点
Node tmp = queue.poll();
/*
判断弹出的节点是否为null如果是则将队列中的节点挨个弹出并判断弹出的节点是否都为null
如果有一个不为null则就不是完成二叉树直接返回false.
如果弹出的节点不为null则将这个节点的左右节点都入队。
当队列为空不进入循环是则为完全二叉树返回true
*/
if (tmp == null) {
while (!queue.isEmpty()) {
Node t = queue.poll();
if (t != null) {
return false;
}
}
} else {
queue.offer(tmp.left);
queue.offer(tmp.right);
}
}
return true;
}