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

2023-01-25 19:53:38

  • 树

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

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

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

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

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

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

  • 二叉树

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

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

  • 完全二叉树

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

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

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

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

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

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

  1. class Node {
  2. Node leftChild;
  3. Node rightChild;
  4. int data;
  5. public Node(int data) {
  6. this.data = data;
  7. }
  8. }

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

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

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

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

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

先看概念：

先序遍历（DLR）：称为先根次序遍历，即先访问根节点，再按先序遍历左子树，最后按先序遍历右子树。
中序遍历（LDR）：称为中根次序遍历，即先按中序遍历左子树，再访问根节点，最后按中序遍历右子树。
后序遍历（LRD）：称为后根次序遍历，即先按后序遍历左子树，再按后序遍历右子树，最后访问根节点。

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

  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. public void inOrder(Node node) {
  10. if(node == null) {
  11. return;
  12. }
  13. inOrder(node.leftChild);
  14. System.out.print(node.data + " ");
  15. inOrder(node.rightChild);
  16. }
  17. public void postOrder(Node node) {
  18. if(node == null) {
  19. return;
  20. }
  21. postOrder(node.leftChild);
  22. inOrder(node.rightChild);
  23. System.out.print(node.data + " ");
  24. }

测试代码：

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

输出：

  1. 先序遍历1 2 4 8 9 5 3 6 7
  2. 中序遍历8 4 9 2 5 1 6 3 7
  3. 后续遍历8 9 4 5 2 6 3 7 1

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

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

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

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

上一篇：Ionic2中集成第三方控件Sweetalert


下一篇：phpmailer 发送邮件(一)