一、二叉树的基本概念
平衡二叉树:如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1。(空树是平衡二叉树)
1 //判断二叉树是否为平衡二叉树
2 import java.util.*;
3
4 /*
5 public class TreeNode {
6 int val = 0;
7 TreeNode left = null;
8 TreeNode right = null;
9 public TreeNode(int val) {
10 this.val = val;
11 }
12 }*/
13 public class CheckBalance {
14 public boolean check(TreeNode root) {
15 boolean [] res = new boolean [1] ;
16 res[0] = true ;
17 getHeight(root,1,res) ;
18 return res[0] ;
19 }
20
21 private int getHeight(TreeNode root,int level,boolean [] res){
22 if(root == null){
23 return level ;
24 }
25
26 int lH =getHeight(root.left,level+1,res) ;
27 if(!res[0]){
28 return lH ;
29 }
30 int rH = getHeight(root.right,level+1,res) ;
31 if(!res[0]){
32 return rH ;
33 }
34
35 if(Math.abs(lH - rH) > 1){
36 res[0] = false ;
37 }
38 return (lH > rH ? lH : rH) ;
39 }
40 }
搜索二叉树:每棵子树的头节点的值都比各自左子树上的所有节点的值要大,也比各自右子树上的所有节点的值要小。搜索二叉树按照中序遍历得到的序列,一定是从小到大排列的。像红黑树、平衡搜索二叉树(AVL树)都是搜索二叉树的不同实现。
满二叉树:除了最后一层的节点无任何子节点外,剩下的每一层上的节点都有两个子节点。满二叉树的层数为L层,节点数为N,则 N = 2L -1,L = log2(N+1)
完全二叉树:除了最后一层之外,其他每一层的节点数都是满的,最后一层如果也是满的,则是一棵满二叉树,也是完全二叉树。最后一层如果不满,则缺少的节点也全部都集中在右边,那也是一棵完全二叉树。
判断是否是完全二叉树的步骤:
1 import java.util.*;
2
3 /*
4 public class TreeNode {
5 int val = 0;
6 TreeNode left = null;
7 TreeNode right = null;
8 public TreeNode(int val) {
9 this.val = val;
10 }
11 }*/
12 public class CheckCompletion {
13 public boolean chk(TreeNode root) {
14 Queue<TreeNode> queue = new LinkedList<TreeNode>() ;
15 queue.add(root) ;
16 TreeNode cur = null ;
17 while(!queue.isEmpty()){
18 cur = queue.poll() ;
19 if((cur.right != null) && (cur.left == null)){
20 return false ;
21 }else if((cur.right != null) && (cur.left != null)){
22 queue.add(cur.left) ;
23 queue.add(cur.right) ;
24 }else{
25 if(cur.left != null){
26 queue.add(cur.left) ;
27 }
28 while(!queue.isEmpty()){
29 cur = queue.poll() ;
30 if((cur.right != null) || (cur.left != null)){
31 return false ;
32 }
33 }
34 }
35 }
36 return true ;
37
38 }
39 }
后继节点:指的是这个节点在中序遍历序列中的下一个节点
前驱节点:指的是这个节点在中序遍历序列中的上一个节点
二、二叉树的遍历
二叉树的遍历方法有多种,首先我想先改变这几个遍历的名字(前根序遍历,中根序遍历,后根序遍历);前中后本来就是相对于根结点来说的,少一个字会产生很多不必要的误解。
先简单描述一下这三种遍历方法的区别:
先序遍历:
递归方式:
1 //前序遍历
2 public void PreOrder(BinaryTreeNode<E> root){
3 if(root == null)
4 return ;
5 else{
6 System.out.print(root+" ");
7 PreOrder(root.lchild) ;
8 PreOrder(root.rchild) ;
9 }
10 }
非递归方式:借用栈的结构特点来实现,具体步骤如下:
1 private void preOrder(TreeNode root){
2 Stcak<TreeNode> stack = new Stcak<TreeNode>() ;
3 TreeNode cur = null ;
4 stack.push(root) ;
5 while(!stack.isEmpty()){
6 cur = stack.pop() ;
7 System.out.print(cur.value+" ") ;
8 if(cur.right != null){
9 stack.push(cur.right) ;
10 }
11 if(cur.left != null){
12 stack.push(cur.left) ;
13 }
14 }
15 }
中序遍历:
递归方式:
1 //中序遍历
2 public void MidOrder(BinaryTreeNode<E> root){
3 if(root == null)
4 return ;
5 else{
6 MidOrder(root.lchild) ;
7 System.out.print(root+" ");
8 MidOrder(root.rchild) ;
9 }
10 }
非递归方式:也是借用栈的结构特点来实现,具体步骤如下:
1 private void inOrder(TreeNode root){
2 Stcak<TreeNode> stack = new Stcak<TreeNode>() ;
3 TreeNode cur = root ;
5 while(!stack.isEmpty() || cur != null){
7 while(cur != null){
8 stack.push(cur) ;
9 cur = cur.left ;
10 }
11 TreeNode top = stack.pop() ;
12 System.out.print(top.value + " ");
13
14 cur = top.right ;
15 }
16 }
后序遍历:
递归方式:
1 //后序遍历
2 public void LastOrder(BinaryTreeNode<E> root){
3 if(root == null)
4 return ;
5 else{
6 LastOrder(root.lchild) ;
7 LastOrder(root.rchild) ;
8 System.out.print(root+" ");
9 }
10 }
非递归方式:也是借用栈的结构特点来实现,具体步骤如下:
1 private void postOrder(TreeNode root){
2 Stcak<TreeNode> stack = new Stcak<TreeNode>() ;
3 TreeNode cur = null ;
4 TreeNode last = root ;
5 stack.push(root) ;
6 while(!stack.isEmpty()){
7 cur = stack.peek() ;
8 if((cur.left != null) && (last != cur.left) && (last != cur.right)){
9 stack.push(cur.left) ;
10 }else if((cur.right != null) && (last != cur.right)){
11 stack.push(cur.right) ;
12 }else{
13 last = stack.pop() ;
14 System.out.print(last.value + " ");
15 }
16 }
17 }
层序遍历:按层的顺序打印节点,每一层从左到右打印,上图中的层序遍历结果是:ABCDEFGH
1 public int[][] printTree(TreeNode root) {
2 List<ArrayList<Integer>> layer = new ArrayList<>();
3 TreeNode last = root;
4 TreeNode nextLast = last;
5 Queue<TreeNode> queue = new LinkedList<>();
6 queue.add(last);
7 ArrayList<Integer> arr = new ArrayList<>();
8 while(!queue.isEmpty()){
9 TreeNode head = queue.poll() ;
10 arr.add(head.val) ;
11 if(head.left != null){
12 queue.add(head.left) ;
13 nextLast = head.left ;
14 }
15 if(head.right != null){
16 queue.add(head.right) ;
17 nextLast = head.right ;
18 }
19 if(head == last){
20 layer.add(arr) ;
21 last = nextLast ;
22 arr = new ArrayList<>();
23 }
24 }
25 int [][] res = new int [layer.size()][] ;
26 for(int i = 0 ; i < layer.size(); i++){
27 res[i] = new int [layer.get(i).size()] ;
28 for(int j = 0 ; j < layer.get(i).size() ; j++){
29 res[i][j] = layer.get(i).get(j) ;
30 }
31 }
32
33 return res ;
34 }
根据遍历结果构造二叉树
根据遍历结果我们可以构造出原始的二叉树,在此过程中我们只能通过二叉树的先序+中序或中序+后序来构造:
已知一棵二叉树的先序序列和中序序列,构造该二叉树的过程如下:
已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下: