首页 > 代码库 > Java与算法之(7) - 完全二叉树

Java与算法之(7) - 完全二叉树

 

下图是一“棵”树的样子。树这个名称起的很形象,整个数据结构由根、枝、叶组成,其中1为根节点,2、3是1的子节点,4、5、6、8、9、10这几个没有子节点的节点称为叶节点。

技术分享

节点的度:一个节点的子树的数量称为该节点的度。例如,图中节点2的度为3,节点3的度为2。

树的度:一棵树的度是指该树中节点的最大度数。如图中树的度是3。

节点的层数:每个节点都处在一定的层次上,图中根节点在第1层,2、3节点在第二层。

树的深度:一棵树中节点的最大层数称为树的深度。如中所示的树的深度为4。

 

  • 二叉树

 

二叉树是一种特殊的树,特点是每个节点最多有两个子节点。上图中的树去掉节点4就符合二叉树的定义了,如下图:

技术分享

 

  • 完全二叉树

 

除二叉树最后一层外,其他各层的节点数都达到最大个数,且最后一层从左向右的叶节点连续存在,只缺右侧若干节点,就是完全二叉树。

如下图,每一层都是从左向右摆放节点,每个节点都是摆满两个子节点后才向右移动到下一个节点,一层摆满后向下移动一层,直到摆放完所有数字。这样得到的二叉树就是完全二叉树,中间有任何缺失的节点就不能称为完全二叉树。

技术分享

完全二叉树的一个重要特性就是节点编号的规律,这是理解完全二叉树构建程序的根本。看上图,仍然按照从左到右、从上到下的规律从1开始为节点编号,图中节点上的数字正好与节点编号相同,可以看出:

如果一个父节点的编号是x,那么它左子节点的编号就是2x,右子节点的编号就是2x+1。

在程序中,二叉树通常采用链式结构存储,链中的每一个节点由节点数据、左子节点指针、右子节点指针组成

 

[java] view plain copy
 
 print?技术分享技术分享
  1. class Node {  
  2.     Node leftChild;  
  3.     Node rightChild;  
  4.     int data;  
  5.   
  6.     public Node(int data) {  
  7.         this.data = data;  
  8.     }  
  9. }  

有时候为了查找父节点方便,还可以为节点定义增加一个指向父节点的指针。

 

假设要用1-9这九个数字构建二叉树,那么先创建好九个节点,然后设置这些节点的左右子节点指针。观察多个节点数不等的完全二叉树可以得出规律,对于x个节点组成的二叉树,只有前x / 2(取整)个节点具有子节点,且第x / 2个节点可能只有左子节点。

理解了这些后,代码就很简单了

 

[java] view plain copy
 
 print?技术分享技术分享
  1. import java.util.LinkedList;  
  2. import java.util.List;  
  3.   
  4. /** 
  5.  * Created by autfish on 2016/9/13. 
  6.  */  
  7. public class BinTreeByList {  
  8.   
  9.     List<Node> nodes = null;  
  10.     private int[] datas = null;  
  11.     private int number;  
  12.   
  13.     public BinTreeByList(int[] datas) {  
  14.         this.datas = datas;  
  15.         this.number = this.datas.length;  
  16.     }  
  17.   
  18.     public void create() {  
  19.         nodes = new LinkedList<>();  
  20.         for(int i = 0; i < this.number; i++) {  
  21.             nodes.add(new Node(datas[i]));  
  22.         }  
  23.         //如果父节点编号为x, 那么左子节点的编号是2x, 右子节点的编号是2x+1  
  24.         for(int noteId = 1; noteId <= this.number / 2; noteId++) {  
  25.             //索引从0开始, 需要在节点编号上减1  
  26.             nodes.get(noteId - 1).leftChild = nodes.get(noteId * 2 - 1);  
  27.             if(noteId * 2 < this.number)  
  28.                 nodes.get(noteId - 1).rightChild = nodes.get(noteId * 2);  
  29.         }  
  30.     }  
  31.   
  32.     private static class Node {  
  33.         Node leftChild;  
  34.         Node rightChild;  
  35.         int data;  
  36.   
  37.         public Node(int data) {  
  38.             this.data = data;  
  39.         }  
  40.     }  
  41. }  

接下来的问题是,二叉树是非线性结构,如果拿到一个已经构建好的二叉树结构,如何遍历其全部节点呢。遍历的定义是按一定的规则和顺序走遍二叉树的所有节点,使每一个节点都被访问一次,而且只被访问一次。

 

先看概念:

先序遍历(DLR):称为先根次序遍历,即先访问根节点,再按先序遍历左子树,最后按先序遍历右子树。
中序遍历(LDR):称为中根次序遍历,即先按中序遍历左子树,再访问根节点,最后按中序遍历右子树。
后序遍历(LRD):称为后根次序遍历,即先按后序遍历左子树,再按后序遍历右子树,最后访问根节点。

三种方式遍历的代码如下:

 

[java] view plain copy
 
 print?技术分享技术分享
  1. public void preOrder(Node node) {  
  2.      if(node == null) {  
  3.          return;  
  4.      }  
  5.      System.out.print(node.data + " ");  
  6.      preOrder(node.leftChild);  
  7.      preOrder(node.rightChild);  
  8.  }  
  9.   
  10.  public void inOrder(Node node) {  
  11.      if(node == null) {  
  12.          return;  
  13.      }  
  14.      inOrder(node.leftChild);  
  15.      System.out.print(node.data + " ");  
  16.      inOrder(node.rightChild);  
  17.  }  
  18.   
  19.  public void postOrder(Node node) {  
  20.      if(node == null) {  
  21.          return;  
  22.      }  
  23.      postOrder(node.leftChild);  
  24.      inOrder(node.rightChild);  
  25.      System.out.print(node.data + " ");  
  26.  }  

测试代码:

 

 

[java] view plain copy
 
 print?技术分享技术分享
  1. public static void main(String[] args) {  
  2.     int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
  3.   
  4.     BinTreeByList tree = new BinTreeByList(numbers);  
  5.     tree.create();  
  6.     System.out.print("先序遍历");  
  7.     tree.preOrder(tree.nodes.get(0));  
  8.     System.out.println();  
  9.     System.out.print("中序遍历");  
  10.     tree.inOrder(tree.nodes.get(0));  
  11.     System.out.println();  
  12.     System.out.print("后续遍历");  
  13.     tree.postOrder(tree.nodes.get(0));  
  14. }  

输出:

 

 

[java] view plain copy
 
 print?技术分享技术分享
  1. 先序遍历7   
  2. 中序遍历7   
  3. 后续遍历1   

其实,完全二叉树还有一种更简单的存储方式,即一维数组。也就是说int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}本身就是一个完全二叉树了。

 

根据数字在数组中的索引即可以计算出数字的节点位置,而且仍然可以对这个二叉树做三种方式的遍历。

 

[java] view plain copy
 
 print?技术分享技术分享
  1. /** 
  2.  * 完全二叉树 
  3.  * Created by autfish on 2016/9/8. 
  4.  */  
  5. public class BinTreeByArray {  
  6.     private int[] numbers;  
  7.   
  8.     public BinTreeByArray(int[] numbers) {  
  9.         this.numbers = numbers;  
  10.     }  
  11.   
  12.     /** 
  13.      * 先序遍历 
  14.      * 根节点 -> 遍历左子树 -> 遍历右子树 
  15.      * @param nodeId 
  16.      */  
  17.     public void preOrder(int nodeId) {  
  18.         if(nodeId <= numbers.length) {  
  19.             System.out.print(numbers[nodeId - 1] + "  ");  
  20.             preOrder(nodeId * 2);  
  21.             preOrder(nodeId * 2 + 1);  
  22.         }  
  23.     }  
  24.   
  25.     /** 
  26.      * 中序遍历 
  27.      * 左子树 -> 父节点 -> 右子树 
  28.      * @param nodeId 
  29.      */  
  30.     public void inOrder(int nodeId) {  
  31.         if(nodeId <= numbers.length) {  
  32.             inOrder(nodeId * 2);  
  33.             System.out.print(numbers[nodeId - 1] + "  ");  
  34.             inOrder(nodeId * 2 + 1);  
  35.         }  
  36.     }  
  37.   
  38.     /** 
  39.      * 后续遍历 
  40.      * 左子树 -> 右子树 -> 父节点 
  41.      * @param nodeId 
  42.      */  
  43.     public void postOrder(int nodeId) {  
  44.         if(nodeId <= numbers.length) {  
  45.             postOrder(nodeId * 2);  
  46.             inOrder(nodeId * 2 + 1);  
  47.             System.out.print(numbers[nodeId - 1] + "  ");  
  48.         }  
  49.     }  
  50.   
  51.     public static void main(String[] args) {  
  52.         int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
  53.         for(int x = 0; x < numbers.length; x++) {  
  54.             System.out.print(numbers[x] + "  ");  
  55.         }  
  56.         System.out.println();  
  57.   
  58.         BinTreeByArray tree = new BinTreeByArray(numbers);  
  59.         System.out.print("先序遍历");  
  60.         tree.preOrder(1);  
  61.         System.out.println();  
  62.         System.out.print("中序遍历");  
  63.         tree.inOrder(1);  
  64.         System.out.println();  
  65.         System.out.print("后续遍历");  
  66.         tree.postOrder(1);  
  67.     }  
  68. }  

用数组存储二叉树的一个常见应用就是堆排序,下文分解。

Java与算法之(7) - 完全二叉树