Javajava算法
数据结构复习：二叉树的概念、性质与遍历实现
树型结构与二叉树的基础知识。涵盖树形结构特点、基本术语及表现形式；详细讲解了二叉树的概念、满二叉树与完全二叉树的定义；阐述了二叉树的五条核心性质。重点实现了二叉树的三种递归遍历方式（前序、中序、后序）及其特点对比，并提供了获取节点数、叶子节点数、第 k 层节点数、树高、元素查找及层序遍历等常用操作的 Java 代码实现。
树型结构与二叉树的基础知识。涵盖树形结构特点、基本术语及表现形式；详细讲解了二叉树的概念、满二叉树与完全二叉树的定义；阐述了二叉树的五条核心性质。重点实现了二叉树的三种递归遍历方式（前序、中序、后序）及其特点对比，并提供了获取节点数、叶子节点数、第 k 层节点数、树高、元素查找及层序遍历等常用操作的 Java 代码实现。
树型结构是一种非线性的数据结构，它是由节点和边组成的，有一个特定的节点被称为根节点，其余节点通过边连接形成的层次关系，将它称为树是因为看起来像一棵倒挂的树：
树形结构：
层次分明：数据和结构之间存在明确的层次关系，便于表示和理解具有层次特征的信息 递归性：许多树形结构的操作都是通过递归的方式实现的 有序性：节点的子节点之间可能存在特定的顺序 有一个特殊的节点。称为根节点，根节点没有前驱节点
在我们的树形结构中，子树之间是不能有交集的否则就不是树形结构啦
在树型结构的概念中：
子树是不相交的；除了根节点外，每个节点有且只有一个父节点；一棵 N 个节点的树有 N-1 条边；
但是在下图可以发现 G 这个节点是有两个父节点的，并且只有 10 个节点却有 11 条边，所以这不是我们意义上的树形结构
树型结构相对线性表来说比较复杂，有很多种表示方式：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等；其中最常用的就是孩子兄弟表示法：
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
上面我们了解了什么是树型结构，接下来看看什么是二叉树
二叉树是一种树型结构，但是二叉树中的每个结点最多有两个子结点，分别称为左结点和右结点
二叉树的特点：
上图演示的其实是一个最普通的二叉树，在二叉树的概念中有两种二叉树比较特殊，我们一起来看看吧
当一棵二叉树，如果每一层的结点都达到最大值，那么这棵树就是满二叉树：
从上图可以发现：该树的层数为 3，结点总数为 2^3-1=7，那么也就是说，如果一棵二叉树的层数为 K，结点总数为 2^K-1，那么它就是一棵满二叉树。
假设一个二叉树的深度为 n，那么除了第 n 层，其他每一层的节点数都达到了最大个数，最后一层的结点按照从左到右的顺序，依次进行排列：
满二叉树是一个特殊的完全二叉树，并且完全二叉树是效率很高的数据结构~
根据下图我们来分析一下二叉树的性质
1. 若规定根结点的层数为 1，那么一棵非空二叉树的第 i 层最多有 2^(i-1) 个结点：例如上图的满二叉树，第 4 层有 2^(4-1)=8 个结点；
2. 若规定只有根结点的二叉树深度为 1，则深度为 K 的二叉树最大结点数是 2^K-1：例如上图的满二叉树，深度为 4，那么该树（刚好是满二叉树）的最大结点数就是 2^4-1=15 个结点；
3. 对任何一棵二叉树，如果其叶子结点个数为 n0，度为 2 的非叶子结点个数为 n0=n2+1：
从上图可以看到：叶子结点的个数为 5 个，度为 2 的非叶子结点的个数为 4 个（n0=n2+1）;
4. 具有 n 个结点的完全二叉树的深度 K 为 log2(n+1) 上取整 +1：
5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的顺序从 0 开始编号，那么对于序号为 i 的结点有：
以上就是二叉树最基本的性质啦
根据上图我们来创建一个二叉树：
public class Binary_Tree {
static class TreeNode{
public TreeNode left;//表示左孩子
public TreeNode right;//表示右孩子
char value;//表示存放数据的变量
public TreeNode(char val) {//结点的构造方法
this.value = val;
}
}
public static TreeNode createTree(){
//创建结点
TreeNode A=new TreeNode('A');
TreeNode B=new TreeNode('B');
TreeNode C=new TreeNode('C');
TreeNode D=new TreeNode('D');
TreeNode E=new TreeNode('E');
TreeNode F=new TreeNode('F');
TreeNode G=new TreeNode('G');
//连接结点
A.left=B; A.right=C;
B.left=D; B.right=E;
C.left=F; C.right=G;
//返回根节点
return A;
}
public static void main(String[] args) {
TreeNode tree=createTree();
}
}
那么这样一棵二叉树就创建好了，接下来我们来看看该如何遍历这棵二叉树吧
所谓遍历 (Traversal) 就是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。二叉树的遍历主要有三种方式：前序遍历、中序遍历、后序遍历，我们来看看这三种遍历方式是如何遍历的
前序遍历的顺序是：根节点--->左子树---->右子树的顺序进行遍历的，对于每棵子树也是按照这样的顺序进行遍历：
代码实现：
public static void preOrder(TreeNode root){
//判断结点是否为空
if(root==null)return ;
System.out.print(root.value);//打印根节点的值
//遍历左子树
preOrder(root.left);
//遍历右子树
preOrder(root.right);
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
//前序遍历二叉树
preOrder(tree);
}
运行结果：
具体的遍历过程在上述的图中已经讲过啦，这里就不在论述~
中序遍历的遍历顺序是：根的左子树--->根节点--->根的右子树。对于每棵子树也是按照这样的顺序进行遍历：
代码实现：
public static void inOrder(TreeNode root){
//判断结点是否为空
if(root==null)return ;
//按照左子树--->根结点---->右子树的顺序进行遍历
//遍历左子树
inOrder(root.left);
//打印根节点
System.out.print(root.value);
//遍历右子树
inOrder(root.right);
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
//中序遍历二叉树
inOrder(tree);
}
运行结果：
后序遍历的遍历顺序是：根的左子树--->根的右子树--->根节点。对于每棵子树也是按照这样的顺序进行遍历：
代码实现：
public static void PostOrder(TreeNode root){
//判断结点是否为空
if(root==null)return;
//按照左子树-->右子树-->根节点的顺序进行遍历
//遍历左子树
PostOrder(root.left);
//遍历右子树
PostOrder(root.right);
//打印根结点
System.out.print(root.value);
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
//后序遍历二叉树
PostOrder(tree);
}
运行结果：
| 前序遍历 | 中序遍历 | 后序遍历 | |
| 遍历顺序 | 根、左、右 | 左、根、右 | 左、右、根 |
| 遍历结果 | ABDECFG | DBEAFCG | DEBFGCA |
| 根节点位置 | 第一个 | 中间 | 最后一个 |
从表格中不难看出通过前序遍历、后续遍历，我们能快速的知道根节点是谁，那么则可以得出结论：
前序遍历和后序遍历的结果能够确定根是谁，而中序遍历的根节点位置是在中间，说明根节点 (A) 的左边就是根结点的左子树元素 (DBE)，根结点 (A) 的右边就是根结点的右子树元素 (FCG)；
以下介绍的是使用二叉树的过程中一些常见的操作
public static int size(TreeNode root){
//判断结点是否为空
if(root==null)return 0;
//如果结点不为空，那么 usedsize++
//遍历左子树
int left=size(root.left);//记录左子树的结点个数
//遍历右子树
int right=size(root.right);//记录右子树的结点个数
return left+right+1;//返回左子树结点个数和右子树结点个数 +1（加上当前结点）
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
System.out.println(size(tree));
}
运行结果：
public static int getLeafTreeNodeCount(TreeNode root){
//判断结点是否为空
if(root==null)return 0;
//判断当前结点是否为叶子结点
if(root.left==null&&root.right==null){
return 1;//是就返回 1
}
//不是就当前结点左子树的叶子结点个数和右子树的叶子结点个数
return getLeafTreeNodeCount(root.left)+getLeafTreeNodeCount(root.right);
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
System.out.println(getLeafTreeNodeCount(tree));
}
运行结果：
public static int getKLevelTreeNodeCount(TreeNode root,int k){
//判断结点是否为空或者 k 是否小于 1
if(root==null||k<1)return 0;
//如果 k=1，表示是要查找的层次，返回 1
if(k==1)return 1;
//递归左右子树，直到 k==1，递归到了要查找的层次
//就返回左子树的 k 层次的节点数 + 右子树的 K 层次的节点数==k 层次总的节点数
return getKLevelTreeNodeCount(root.left,k-1)+getKLevelTreeNodeCount(root.right,k-1);
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
System.out.println(getKLevelTreeNodeCount(tree,2));
}
运行结果：
public static int getHeight(TreeNode root){
//判断该结点是否为空
if(root==null)return 0;
//如果不为空，递归左子树和右子树，返回左子树和右子树的深度的最大值加上当前结点（深度 1）
return Math.max(getHeight(root.left),getHeight(root.right))+1;
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
System.out.println(getHeight(tree));
}
运行结果：
public static TreeNode findvalue(TreeNode root,char val){
//判断结点是否为空
if(root==null)return null;
//判断当前结点的值是否等于 val
if(root.value==val)return root;
//如果当前结点的值不是 val，就去左子树中找
TreeNode leftNode=findvalue(root.left,val);
//如果左子树找到了就返回
if(leftNode!=null)return leftNode;
//如果左子树找不到就去右子树中找
TreeNode rightNode=findvalue(root.right,val);
//如果右子树找到了就返回
if(rightNode!=null)return rightNode;
//找不到返回 null
return null;
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
System.out.println(findvalue(tree,'C').value);
}
运行结果：
画图分析：
这里实现层序遍历需要借助队列来实现，如果对队列不熟悉的话可以看一下上一期博客：栈和队列
代码实现层序遍历：
public static void levelOrder(TreeNode root){
if(root==null)return ;
//创建队列
Queue<TreeNode> queue=new LinkedList<>();
//将根结点放入队列中
queue.offer(root);
while(!queue.isEmpty()){
//如果队列为空说明遍历完了
TreeNode cur=queue.poll();//弹出元素
System.out.print(cur.value);
//将弹出结点的孩子结点放入队列
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}
public static void main(String[] args) {
TreeNode tree=createTree();//创建二叉树
levelOrder(tree);
}
运行结果：
以上就是二叉树的一些基本操作啦~
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online