二叉树的基本概念和底层实现

1. 树型结构

1.1 认识树

在学习二叉树之前我们需要了解一下树型结构

树是一种非线性的数据结构,它是由n个结点组成的一个有层次关系的集合,看起来像个倒挂的树,也就是根朝上,枝叶朝下.

特点:

1. 根结点没有前驱结点

2. 除了根结点外其他的结点被分为互不相交的集合,每个集合又是一棵类似的子树.每棵子树的根结点都只有一个前驱,有0或多个后继.

3. 树是递归定义的

1.2 树的概念

重点:

结点的度: 一个结点含有子树的个数为结点的度.

树的度: 所有结点的最大的度就是树的度.

叶子结点(终端结点): 度为0的结点.

双亲结点(父节点): 如果一个结点含有子节点,那么这个结点就是其子节点的父节点.

孩子结点(子节点): 一个结点的子树所含有的根结点称为该结点的子节点.

根结点: 一棵树没有双亲的结点.

结点的层次: 从根开始定义,根为第一层,根的子节点为第二层...

树的深度: 指的是从根结点(度为0)自顶向下逐层累加至该结点时的深度.树的深度十数中最大结点的深度.

树的高度: 结点的高度指从该结点最底层的叶子节(度为0)点出发,自定向上逐层累加至该结点的高度.树的高度是树中高度最大的结点的高度.

以下了解即可

非终端结点(分支结点): 度不为0的结点.

兄弟结点: 有相同父亲的结点互称为兄弟结点.

堂兄弟结点: 双亲在同一层的结点互为堂兄弟结点.

结点的祖先: 从根到该结点所经分支上的所有结点.

子孙: 某结点经由下面的结点就是该结点的子孙.

森林: 由m棵互补相交的树组成的集合为森林.

1.3 树的表示形式

树的存储方法有很多表示方式: 双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法

主要了解孩子兄弟表示法:

然后树型结构的话主要就应用在我们的文件和目录管理上

2. 二叉树

2.1 概念

二叉树: 每个结点的度都是<=2

如果一棵树是二叉树,那么它的每一棵子树都是二叉树,二叉树是有序树

合成二叉树的结构

2.2 俩种特殊的二叉树

满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^(k -1) ，则它就是满二叉树。
简而言之就是每层结点都达到最大值:2^(k - 1);

完全二叉树: 全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树
简而言之就是从上到下从左到右依次存放,不能有割开的
满二叉树是一种特殊的完全二叉树

2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i - 1) (i>0)个结点.

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k -1(k>=0).

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为 log2(n-1)上取整,2在这里为底数

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

若2i+1<n，左孩子序号：2i+1，否则无左孩子

若2i+2<n，右孩子序号：2i+2，否则无右孩子

2.3.1 一些相关计算题

第一题:

第二题和第三题:

第四题:

2.4 二叉树的遍历

遍历指的是沿着某条路线遍历

前序遍历(先根遍历): 根 -> 左子树 -> 右子树

中序遍历: 左子树 -> 根 -> 右子树

后序遍历: 左子树 -> 右子树 -> 根

层次遍历: 从左到右从上到下依次遍历

2.4.1 一些相关的题目

题目一:

题目二:

题目三:

题目四

题目五:

问:如果给你一个前序和后序能否创建一个二叉树?

前序和后序不能创建一个二叉树: 因为前序和后序确定的都是根,不能确定左右.

2.5 二叉树的底层实现

2.5.1 前置准备

我们来自己实现一个二叉树,为了更好的理解二叉树,我们先手动连接一个二叉树.在这之前我先介绍一些我们自定义的属性和类.首先我们先创建结点内部类,我们使用孩子表示法,每个结点分为val域,left域,right域.然后我们提供一个构造方法,每次创建结点的时候我们都要把val的参数传进去.

然后我们正式进入二叉树的手动连接,我们如图手动构造二叉树,我们只要对着图操纵每个结点的right和left即可.

2.5.2 实现二叉树的三种遍历操作

前序遍历,我们按照: 根结点 -> 左子树 -> 右子树. 这种顺序来进行遍历,因此我们先要判断根结点是不是空的,然后我们再打印根结点,再递归左子树,然后递归右子树.如图,我们就展示了遍历A的左子树一部分的遍历流程.

中序遍历,我们按照: 左子树 -> 根结点 -> 右子树.这种顺序来进行遍历,首先我们还是要判断根结点是不是空的,然后我们先递归左子树,然后递归到最左边结点的时候,我们就打印我们的子树的根结点,然后我们再递归我们的右子树.如图简要分析了一下它的过程.

后序遍历,我们按照: 左子树 -> 右子树 -> 根结点.这种顺序来对二叉树进行遍历.我们先递归左子树,然后递归右子树,最后在进行打印,如图.

2.5.3 获取树中结点的个数

1> 遍历的方式 : 只要遍历的结点不为空,我们就让全局变量++

我们获取树中的结点数目,我们只要遍历整个树,然后经过一个结点就记录一下就可以; ,因此我们选择前序遍历.每次遍历一个结点,我们就让全局遍历++

2> 用子问题的思路来解决: 整棵树的结点数 = 左子树的结点数 + 右子树的结点数 + 根结点(1)

2.5.4 获取叶子结点的个数

1> 遍历的方式: 按照某种方式来进行遍历,遍历到某个结点,判断是不是叶子,是就计数器++

2> 用子问题的思路来写: 整棵数的叶子 = 左子树的叶子 + 右子树的叶子

用子问题,我们就可以充分利用我们的返回值了

2.5.5 获取第k层结点的个数

子问题方法: 第k层节点数 = 左子树的k-1 层的节点数 + 右子树k-1层的结点数

我们从上到下标号,每次遍历到下一层,我们k就--,直到k == 1的时候,我们就遍历到了给定的第k层,然后我们就返回1.

2.5.6 获取二叉树的高度

子问题解决: 整棵树的高度 = max(左子树的高度,右子树的高度) + 1

不定义结点数变量也可以,但是在刷题软件往往会超时,因为第一种写法只递归了一次,而下面这种写法在判断的时候递归了一次,在返回值的时候又递归了一次.

2.5.7 返回检测值为value的结点

我们直接前序遍历,先判断根结点是不是,然后判断左子树里面有没有val,再判断右子树有没有.我们如果没有找到,一定返回的是null,如果找到了,我们一定返回的是那个结点.

2.5.8 整体代码

package 二叉树;import java.util.ArrayList;
import java.util.List;//TODO 孩子表示法
//
public class BinaryTree {static class TreeNode {//每一棵树的结点public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}//手动连接二叉树public 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');TreeNode H = new TreeNode('H');A.left = B;B.left = D;B.right = E;E.right = H;A.right = C;C.left = F;C.right = G;return A;}//进行遍历操作// 前序遍历(根左右)//用递归 的方式来写 : 把大问题处理成小问题,处理方式是一样的void preOrder(TreeNode root) {//先判断根结点为不为空if (root == null) {return;}//不为空就按照根左右的方式来打印;System.out.print(root.val + " ");//遍历根结点的左子树preOrder(root.left);//遍历根结点的右子树preOrder(root.right);}// 中序遍历(左根右)void inOrder(TreeNode root) {if (root == null) {return;}//从左子树开始遍历inOrder(root.left);//打印左子树的值System.out.print(root.val + " ");inOrder(root.right);}// 后序遍历(左右根)void postOrder(TreeNode root) {if (root == null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+" ");}//把前序遍历的结构存储到List里面去List<Integer> list1 = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {//先判断根结点为不为空if (root == null) {return list1;}//不为空就按照根左右的方式来打印;list1.add((int) root.val);//遍历根结点的左子树preorderTraversal(root.left);//遍历根结点的右子树preorderTraversal(root.right);return list1;//如何合理利用返回值?}//我们进行优化public List<Integer> preorderTraversal2(TreeNode root) {List<Integer> list = new ArrayList<>();//先判断根结点为不为空if (root == null) {return list;}//不为空就按照根左右的方式来打印;list.add((int) root.val);//遍历根结点的左子树List<Integer> leftTree =  preorderTraversal2(root.left);//把左边的树放进去list.addAll(leftTree);//遍历根结点的右子树List<Integer> rightTree = preorderTraversal2(root.right);//把右边的树放进去list.addAll(rightTree);return list;}public int nodeSize;//TODO 获取树中的个数//只要遍历的结点不为空,我们就++//遍历思路来写int size(TreeNode root) {if(root == null) {return 0;}nodeSize++;size(root.left);size(root.right);return nodeSize;//利用返回值来进行优化}//用子问题的思路来解决:整棵树的结点个数 = 左子树结点个数 + 右子树结点个数int size2(TreeNode root) {if(root == null) {return 0;}return size2(root.left) + size2(root.right) + 1;//左子树的结点数 + 右子树的结点数 + 根结点(1)}//TODO 获取叶子结点的个数//遍历思路来写// 按照某种方式来进行遍历,遍历到某个结点,判断是不是叶子,是就计数器++int leafCount;int getLeafNodeCount(TreeNode root){if(root == null) {return 0;}//如果每次遍历我们的结点左右都为空就让全局变量leftCount++;if (root.left == null && root.right == null) {leafCount++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafCount;}//用子问题的思路来写: 整棵数的叶子 = 左子树的叶子 + 右子树的叶子int getLeafNodeCount1(TreeNode root) {if(root == null) {return 0;}//如果左右都为null那么就返回1if(root.right == null && root.left == null) {return 1;}//计算左子树和右子树的return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);}//接下来我们都用子问题来解决//TODO 获取第k层结点的个数//第k层的结点数 = 左子树k-1层的节点数 + 右子树k-1层的节点数int getLeveNodeCount(TreeNode root, int k) {if(root == null) {return 0;}if(k == 1) {return 1;}//计算k-1层的左子树结点 + 计算k-1层的右子树结点return getLeveNodeCount(root.left,k - 1) + getLeveNodeCount(root.right,k - 1);}//TODO 获取二叉树的高度 时间复杂度O(N)因为遍历了每一个结点//整棵树的高度 = max(左子树的高度,右子树的高度) +   1int getHight(TreeNode root) {if (root == null){return 0;}//计算左树的高度int leftHight = getHight(root.left);int rightHight = getHight(root.right);//返回左树和右树的高度最高的+1return leftHight > rightHight ? leftHight + 1 : rightHight + 1;}int getHight2(TreeNode root) {if (root == null){return 0;}//返回左树和右树的最大值+1return getHight(root.left) > getHight(root.right) ? getHight(root.left) + 1 : getHight(root.right) + 1;//这里递归太多次了没有第一种好,第一种只递归了一次}//TODO 检测值为value的元素是否存在//直接前序遍历,先判断根是不是,然后判断左子树是不是,最后判断右子树是不是TreeNode find(TreeNode root ,char val) {if(root == null) {return null;}//判断根是不是if(root.val == val) {return root;}//判断左子树TreeNode ret1 = find(root.left,val);if(ret1 != null) {//如果不为空就找到了return ret1;}//判断右子树是不是TreeNode ret2 = find(root.right,val);if(ret2 != null) {return ret2;}//左右都没找到return null;}}

运行结果: