二叉树的基本概念和遍历

一、二叉树的基本概念

平衡二叉树:如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过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. 层序遍历二叉树;
  2. 如果存在一个节点的右子树存在而左子树不存在,则直接返回false
  3. 如果当前节点的左子树和右子树不同时存在,则其后的节点的左右子树均不存在,如果存在,则直接返回false
  4. 如果顺利遍历结束,则直接返回true
 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. 先序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树。上图中的先序遍历结果是ABDHECFG
  2. 中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树。上图中的中序遍历结果是HDBEAFCG
  3. 后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。上图中的后序遍历结果是HDEBFGCA

先序遍历:

递归方式

 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. 首先申请一个栈,记为stack
  2. 然后将头结点压入stack中
  3. 每次从stack中弹出栈顶元素,记为cur,然后打印cur节点的值。如果cur右孩子不为空的话,将cur的右孩子先压入stack中,最后如果cur的左孩子不为空的话将cur的做孩子压入栈stack中
  4. 不断重复步骤3,直到stack为空,全部过程结束。
 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. 申请一个新的栈,记为stack,申请一个变量cur,初始时令cur等于头结点
  2. 先把cur节点压入栈中,对以cur节点为头的整棵子树来说,依次把整棵树的左子树压入栈stack中,即不断令cur = cur.left,然后重复步骤2
  3. 不断重复步骤2,直到发现cur为空,此时从stack中弹出一个节点,记为node,打印node的值,并让cur = node.right,然后继续重复步骤2。
 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. 申请一个栈,记为stack,将头结点压入stack,同时设置两个变量h和cur,在整个流程中,h代表最近一次弹出并打印的节点,cur代表当前stack的栈顶节点,初始时令h为头结点,cur为null;
  2. 每次令cur等于当前stack的栈顶元素,但是补充stack中弹出节点,此时分为以下三种情况判断是否弹出元素:
    1. 如果cur的做孩子不为null,并且h不等于cur的左孩子,也不等于cur的右孩子,则把cur的左孩子压入栈stack中
    2. 如果情况1不成立,并且cur的右孩子不为null,并且h不等于cur的右孩子,则把cur的右孩子压入栈stack中
    3. 如果情况1和2都不成立,则从stack中弹出cur元素并打印,然后令h等于cur
  3. 一直重复步骤2,直到stack为空并且cur为空,过程停止
 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

  • 用队列作为辅助结构进行输出,然后用变量last表示当前行的最后节点,变量nextLast表示下一行的最后节点
 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 }

根据遍历结果构造二叉树

根据遍历结果我们可以构造出原始的二叉树,在此过程中我们只能通过二叉树的先序+中序中序+后序来构造:

已知一棵二叉树的先序序列和中序序列,构造该二叉树的过程如下:

  1. 根据前根序序列的第一个元素建立根结点;
  2. 在中根序序列中找到该元素,确定根结点的左右子树的中根序序列;
  3. 在前根序序列中确定左右子树的前根序序列;
  4. 由左子树的前根序序列和中根序序列建立左子树;
  5. 由右子树的前根序序列和中根序序列建立右子树。

已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下:

  1. 根据后根序序列的最后一个元素建立根结点;
  2. 在中根序序列中找到该元素,确定根结点的左右子树的中根序序列;
  3. 在后根序序列中确定左右子树的后根序序列;
  4. 由左子树的后根序序列和中根序序列建立左子树;
  5. 由右子树的后根序序列和中根序序列建立右子树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LeetCode

LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie,...

10500
来自专栏我是东东强

常见算法之二叉树遍历

所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

16420
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

538100
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

23490
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

23970
来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

10010
来自专栏互扯程序

Java集合深度解析之TreeMap

红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,红黑树通过一些限制,使其不会出现二叉树排序树中极端的一...

40850
来自专栏王硕

原 B树C语言代码实现

741100
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

20660
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

20320

扫码关注云+社区

领取腾讯云代金券