二叉树复习
2019-08-15 本文已影响12人
盼旺
现实生活中树
数据结构中树长这样子
二叉树的意思就是说：每个节点不能多于有两个儿子，上面的图就是一颗二叉树。
关键知识点
- 一棵树至少会有一个节点(根节点)
- 树由节点组成，每个节点的数据结构是这样的：
节点的定义就是：一个数据、两个指针(如果有节点就指向节点、没有节点就指向null) - 二叉树第i层上的结点数目最多为2的（i-1）次方
2^（i-1）(i>=1) - 深度为k的二叉树至多有
2k-1(k>=1)个结点
二叉树的遍历
四种主要的遍历思想为：
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
层次遍历：只需按层次遍历即可
静态创建二叉树
树是由若干个节点组成，节点连接起来就成了树，而节点由一个数据、两个指针组成
因此，创建树实际上就是创建节点，然后连接节点
举个栗子：这个二叉树为例来构建
定义节点类
package tree;
public class TreeNode {
// 左节点(儿子)
private TreeNode lefTreeNode;
// 右节点(儿子)
private TreeNode rightNode;
// 数据
private int value;
public TreeNode() {
super();
}
public TreeNode(int value) {
super();
this.value = value;
}
public TreeNode getLefTreeNode() {
return lefTreeNode;
}
public void setLefTreeNode(TreeNode lefTreeNode) {
this.lefTreeNode = lefTreeNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
创建上面二叉树代码
package tree;
public class TwoTreeDemo {
public static void main(String[] args) {
//先创建好这5个节点
//根节点-->10
TreeNode treeNode1 = new TreeNode(10);
//左孩子-->9
TreeNode treeNode2 = new TreeNode(9);
//右孩子-->20
TreeNode treeNode3 = new TreeNode(20);
//20的左孩子-->15
TreeNode treeNode4 = new TreeNode(15);
//把他们连接起来
//20的右孩子-->35
TreeNode treeNode5 = new TreeNode(35);
//根节点的左右孩子
treeNode1.setLefTreeNode(treeNode2);
treeNode1.setRightNode(treeNode3);
//20节点的左右孩子
treeNode3.setLefTreeNode(treeNode4);
treeNode3.setRightNode(treeNode5);
}
}
遍历代码
前序遍历10->9->20->15->35
public static void preTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问根节点
System.out.println(rootTreeNode.getValue());
//访问左节点
preTraverseBTree(rootTreeNode.getLefTreeNode());
//访问右节点
preTraverseBTree(rootTreeNode.getRightNode());
}
}
前序遍历
中序遍历
9->10->15->20->35
public static void inTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问左节点
inTraverseBTree(rootTreeNode.getLefTreeNode());
//访问根节点
System.out.println(rootTreeNode.getValue());
//访问右节点
inTraverseBTree(rootTreeNode.getRightNode());
}
}
后序遍历9->15->35->20->10
public static void endTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问左节点
endTraverseBTree(rootTreeNode.getLefTreeNode());
//访问右节点
endTraverseBTree(rootTreeNode.getRightNode());
//访问根节点
System.out.println(rootTreeNode.getValue());
}
}
层序遍历10->9->20->15->35
public static void cengTraverseBTree(TreeNode rootTreeNode){
//声明一个队列
//LinkedBlockingQueue的容量是没有上限的,也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。
//ArrayBlockingQueue在构造时需要指定容量
Queue<TreeNode> queue = new LinkedBlockingQueue<>();
if (rootTreeNode == null) {
return;
}
queue.add(rootTreeNode);
while(!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.println(tempNode.getValue());
if(tempNode.getLefTreeNode()!=null)queue.add(tempNode.getLefTreeNode());
if(tempNode.getRightNode()!=null)queue.add(tempNode.getRightNode());
}
}
动态创建二叉树查找树
上面我们是手动创建二叉树的，一般地：都是给出一个数组给你，让你将数组变成一个二叉树，此时就需要我们动态创建二叉树了。
二叉树中还有一种特殊的二叉树：
二叉查找树(binary search tree)定义：
当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。
假设我们有一个数组：int[] arrays = {3, 2, 1, 4, 5};
1.首先将3作为根节点
2.随后2进来了，我们跟3做比较，比3小，那么放在3的左边
3.随后1进来了，我们跟3做比较，比3小，那么放在3的左边，此时3的左边有2了，因此跟2比，比2小，放在2的左边
4.随后4进来了，我们跟3做比较，比3大，那么放在3的右边
5.随后5进来了，我们跟3做比较，比3大，那么放在3的右边，此时3的右边有4了，因此跟4比，比4大，放在4的右边
#无论任何一颗子树，左边都比根要小，右边比根要大
代码实现
因为是动态创建的，因此我们得用一个类来表示根节点
package tree;
public class RootNode {
private TreeNode treeRoot;
public TreeNode getTreeRoot() {
return treeRoot;
}
public void setTreeRoot(TreeNode treeRoot) {
this.treeRoot = treeRoot;
}
}
创建二叉搜索树代码
package tree;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class SerrchTwoTree {
public static void main(String[] args) {
int[] arrays = {3, 2, 1, 4, 5};
RootNode root = new RootNode();
for(int value:arrays) {
createtree(root, value);
}
System.out.println("前序遍历");
preTraverseBTree(root.getTreeRoot());
System.out.println("");
System.out.println("中序遍历");
inTraverseBTree(root.getTreeRoot());
System.out.println("");
System.out.println("后序遍历");
endTraverseBTree(root.getTreeRoot());
System.out.println("");
System.out.println("层序遍历");
cengTraverseBTree(root.getTreeRoot());
}
//rootNode 根节点 v需要创造的节点的值
public static void createtree(RootNode rootNode,int v) {
//如果树根为空(第一次访问)，将第一个值作为根节点
if(rootNode.getTreeRoot()==null) {
TreeNode treeNode = new TreeNode(v);
rootNode.setTreeRoot(treeNode);
}else {
//当前树根
TreeNode tempNode = rootNode.getTreeRoot();
while(tempNode!=null) {
//当前值大于根值，往右边走
if(v>tempNode.getValue()) {
//右边没有树根，那就直接插入 并且返回 记着返回哦
if(tempNode.getRightNode()==null) {
tempNode.setRightNode(new TreeNode(v));
return;
}else {
//如果右边有树根，到右边的树根去
tempNode = tempNode.getRightNode();
}
}else {
if(tempNode.getLefTreeNode()==null) {
tempNode.setLefTreeNode(new TreeNode(v));
return;
}else {
tempNode=tempNode.getLefTreeNode();
}
}
}
}
}
//前序遍历
public static void preTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问根节点
System.out.print(rootTreeNode.getValue()+" ");
//访问左节点
preTraverseBTree(rootTreeNode.getLefTreeNode());
//访问右节点
preTraverseBTree(rootTreeNode.getRightNode());
}
}
//中序遍历
public static void inTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问左节点
inTraverseBTree(rootTreeNode.getLefTreeNode());
//访问根节点
System.out.print(rootTreeNode.getValue()+" ");
//访问右节点
inTraverseBTree(rootTreeNode.getRightNode());
}
}
//后序遍历
public static void endTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问左节点
endTraverseBTree(rootTreeNode.getLefTreeNode());
//访问右节点
endTraverseBTree(rootTreeNode.getRightNode());
//访问根节点
System.out.print(rootTreeNode.getValue()+" ");
}
}
//层序遍历
public static void cengTraverseBTree(TreeNode rootTreeNode){
//声明一个队列
//LinkedBlockingQueue的容量是没有上限的,也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。
//ArrayBlockingQueue在构造时需要指定容量
Queue<TreeNode> queue = new LinkedBlockingQueue<>();
if (rootTreeNode == null) {
return;
}
queue.add(rootTreeNode);
while(!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.getValue()+" ");
if(tempNode.getLefTreeNode()!=null)queue.add(tempNode.getLefTreeNode());
if(tempNode.getRightNode()!=null)queue.add(tempNode.getRightNode());
}
}
}
结果
查询二叉树的深度
public static int getHeight(TreeNode treeNode) {
if (treeNode == null) {
return 0; // 达到叶子返回0的孩子 然后递归回去加1
} else {
//左边的子树深度
int left = getHeight(treeNode.getLefTreeNode());
//右边的子树深度
int right = getHeight(treeNode.getRightNode());
int max = left;
if (right > max) {
max = right;
}
return max + 1;
}
}
// System.out.println(getHeight(treeNode1));
查询二叉树的最大值
如果是二叉查找树就是中序遍历的最后一个
步骤：
左边找最大值->递归
右边找最大值->递归
然后分别再与根节点的值比较
public static int getMax(TreeNode rootTreeNode) {
if (rootTreeNode == null) {
return -1;
} else {
//找出左边的最大值
int left = getMax(rootTreeNode.getLefTreeNode());
//找出右边的最大值
int right = getMax(rootTreeNode.getRightNode());
//与当前根节点比较
int currentRootValue = rootTreeNode.getValue();
//假设左边的最大
int max = left;
if (right > max) {
max = right;
}
if (currentRootValue > max) {
max = currentRootValue;
}
return max ;
}
}
前中/中后序重建二叉树
已知前序和中序遍历，可以确定一棵二叉树。
已知中序和后序遍历，可以确定一棵二叉树。
但是，已知前序和后序遍历，不能确定一棵二叉树。
已知前序和中序
步骤过程:
-
前序数组中最左边的值就是树的头节点值，记为h，并用h生成头节点，记为head，然后在中序数组中找到h，假设位置是i，那么在中序数组中，i左边的数组就是头节点左子树的中序数组，假设长度为l，则左子树的先序数组就是先序数组中h往右长度也为l的数组。
-
用左子树的先序和中序数组，递归整个过程建立左子树，返回的头节点记为left。
-
i右边的数组就是头节点右子树的中序数组，假设长度为r，先序数组中右侧等长的部分就是头节点右子树的先序数组。
-
用右子树的先序和中序数组，递归整个过程建立右子树，返回的头节点记为right。
-
把head的左孩子和右孩子分别设置left和right，返回head，过程结束。
你肯定一脸懵逼
看看例子
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
-
首先，根节点 是
{ 1 }；
左子树是：前序{ 2,4,7 }，中序{ 4,7,2 }；
右子树是：前序{ 3,5,6,8 }，中序{ 5,3,8,6 }； -
这时，如果我们把左子树和右子树分别作为新的二叉树(即左子树是：前序
{ 2,4,7 }，中序{ 4,7,2 }看成新的需要重构的二叉树)，一直递归，则可以求出其根节点，左子树和右子树。 -
这样，一直用这个方式，就可以实现重建二叉树。
假设有如下图二叉树
肉眼可得它的
前序:
1,2,4,7,3,5,6,8中序:
4,7,2,1,5,3,8,6后序:
7,4,2,5,8,6,3,1核心测试代码
//主功能函数重构二叉树 根据前中序 返回根节点
public static TreeNode CreateTreeByPreAndIn(int [] pre,int [] in) {
if(pre == null || in == null){
return null;
}
TreeNode root = PreAndIn(pre, in, 0, pre.length-1, 0, in.length-1);
return root;
}
//核心递归
public static TreeNode PreAndIn(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
TreeNode tree = new TreeNode(pre[preStart]);
if (preStart == preEnd && inStart == inEnd) {
return tree;
}
int root = 0;//root表示根节点在中序的位置
//找到前序的第一个元素(即根元素)在中序的位置
for(root= inStart; root <= inEnd; root++){
if (pre[preStart] == in[root]) {
break;
}
}
//左子树的长度
int leftLength = root - inStart;
//右子树的长度
int rightLength = inEnd - root;
if (leftLength > 0) {
tree.setLefTreeNode(PreAndIn(pre, in, preStart+1, preStart+leftLength, inStart, root-1));
}
if (rightLength > 0) {
tree.setRightNode(PreAndIn(pre, in, preStart+1+leftLength, preEnd, root+1, inEnd));
}
return tree;
}
已知中序和后序一样思路
只不过后序是根节点在最后
例如输入后序遍历序列{7,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6}。
- 首先，根节点 是
{ 1 }；
左子树是：后序{ 7,4,2 }，中序{ 4,7,2 }；
右子树是：后序{ 5,8,6,3 }，中序{ 5,3,8,6 }；
核心测试代码
//主功能函数重构二叉树 根据中后序 返回根节点
public static TreeNode CreateTreeByPrInAndEnd(int [] end,int [] in) {
if(end == null || in == null){
return null;
}
TreeNode root = EndAndIn(end, in, 0, end.length-1, 0, in.length-1);
return root;
}
//核心递归
public static TreeNode EndAndIn(int[] end, int[] in, int endStart, int endEnd, int inStart, int inEnd) {
TreeNode tree = new TreeNode(end[endEnd]);
if (endStart == endEnd && inStart == inEnd) {
return tree;
}
int root = 0;//root表示根节点在中序的位置
//找到前序的第一个元素(即根元素)在中序的位置
for(root= inStart; root <= inEnd; root++){
if (end[endEnd] == in[root]) {
break;
}
}
//左子树的长度
int leftLength = root - inStart;
//右子树的长度
int rightLength = inEnd - root;
System.out.println(leftLength+" wg "+rightLength);
if (leftLength > 0) {
tree.setLefTreeNode(EndAndIn(end, in, endStart, endStart+leftLength-1, inStart, root-1));
}
if (rightLength > 0) {
tree.setRightNode(EndAndIn(end, in, endStart+leftLength, endEnd-1, root+1, inEnd));
}
return tree;
}
懵逼学习，有错欢迎指正！Thanks
文章参考:https://juejin.im/post/5ab5a01d518825555c1d9a24#heading-8
