树形结构说明及使用java实现二叉树

一、树形结构的必要性

1.数组列表和链表优势与劣势的比较
数据结构名称 优势 劣势
数组(包括数组列表) 访问数据快 插入节点或删除节点慢(移动节点代价大)
链表 插入节点或删除节点快(修改指针即可) 访问数据慢(需要遍历)
2.树的优势
  • 插入或删除节点快
  • 访问元素快

它只是将插入或删除节点和访问节点的性能要求做了一个平衡

二、树形结构概述

1.树形结构

树形结构

根据日常生活中的树,我们可以得出树的逻辑结构,和一个倒着的树是一样的

2.树形结构相关的概念

树形结构相关概念

(1)根节点:如果一颗树有树根一样,树形结构就根节点,它是树的最顶端的节点,是一个超级父节点
(2)父节点:拥有子节点的节点就是父节点(根节点是一个特殊的子节点)
(3)子节点:父节点下面的孩子节点就是子节点
(4)叶子节点:没有孩子节点的子节点即为叶子节点,它和树木一样,一颗树主为根、枝和叶,根类似于根节点,枝就如果父节点,叶就是叶子节点,叶子是最后一层,而树枝上可能有叶子,也可能没有叶子
(5)层:也称为树的深度,如上图所示,树的层为3
(6)兄弟节点:同一层的其他节点,称为兄弟节点

三、树的分类

  • 二叉树:二叉树是每个节点最多有两个子树的树结构。
    • 满二叉树:高度为h,并且由2{h} –1个结点的二叉树,被称为满二叉树(所有节点都有两个子树的二叉树)
    • 完全二叉树:一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下一层的叶结点集中在靠左的若干位置上
    • 二叉查找树:二叉搜索树
  • B树
  • B+树

四、使用java实现二叉树

二叉树的特点:

  • (1)二叉树节点的子节点至多有2个节点
  • (2)二叉树节点插入是有序的,一点来说,比当前根节点小的,则插入根节点的左子树;比当前根节点大的,则插入根节点的右子树
1.二叉树组成部分
  • 二叉树主体
  1. /**
  2. * 树的节点个数
  3. */
  4. private int size;
  5. /**
  6. * 根节点
  7. */
  8. private TreeNode<T> root;
  9. /**
  10. * 前序
  11. */
  12. private static final int PRE_ORDER = 1;
  13. /**
  14. * 后序
  15. */
  16. private static final int POST_ORDER = 2;
  17. /**
  18. * 中序
  19. */
  20. private static final int IN_ORDER = 3;
  • 二叉树节点
  1. private class TreeNode<T> {
  2. //节点元素索引值
  3. private Long index;
  4. //节点元素数据值
  5. private T data;
  6. //左子树节点
  7. private TreeNode<T> leftChild;
  8. //右子树节点
  9. private TreeNode<T> rightChild;
  10. public TreeNode(Long index, T data) {
  11. this.index = index;
  12. this.data = data;
  13. }
  14. public TreeNode(Long index, T data, TreeNode<T> leftChild, TreeNode<T> rightChild) {
  15. this.index = index;
  16. this.data = data;
  17. this.leftChild = leftChild;
  18. this.rightChild = rightChild;
  19. }
  20. public Long getIndex() {
  21. return index;
  22. }
  23. public void setIndex(Long index) {
  24. this.index = index;
  25. }
  26. public T getData() {
  27. return data;
  28. }
  29. public void setData(T data) {
  30. this.data = data;
  31. }
  32. public TreeNode<T> getLeftChild() {
  33. return leftChild;
  34. }
  35. public void setLeftChild(TreeNode<T> leftChild) {
  36. this.leftChild = leftChild;
  37. }
  38. public TreeNode<T> getRightChild() {
  39. return rightChild;
  40. }
  41. public void setRightChild(TreeNode<T> rightChild) {
  42. this.rightChild = rightChild;
  43. }
  44. }
2.二叉树插入节点

插入步骤如图:

二叉树节点插入步骤

  1. public void insert(Long index, T value) {
  2. //1.生成新节点
  3. TreeNode node = new TreeNode(index, value, null, null);
  4. //2.定义临时节点parent,表示当前节点父节点
  5. TreeNode parent;
  6. //3.定义昨时节点current,表示当前指针节点
  7. TreeNode current = root;
  8. //4.如果根节点为null即是空树,那么新节点就是根节点,直接返回
  9. if (root == null) {
  10. root = node;
  11. size++;
  12. return;
  13. } else {
  14. //5.循环依次找到当前插入节点的父节点,进入插入
  15. while (true) {
  16. parent = current;
  17. //插入的元素比当前元素小,则遍历左子树
  18. if (current.getIndex() > node.getIndex()) {
  19. current = current.getLeftChild();
  20. //如果节点为null(即当前节点的父节点的左子树为null,直接的将当前节点当成左子树的节点)
  21. if (current == null) {
  22. size++;
  23. parent.setLeftChild(node);
  24. return;
  25. }
  26. } else {
  27. //插入的元素比当前元素大,则遍历右子树
  28. current = current.getRightChild();
  29. //如果节点为null(即当前节点的父节点的右子树为null,直接将当前节点当成右子树的节点)
  30. if (current == null) {
  31. size++;
  32. parent.setRightChild(node);
  33. return;
  34. }
  35. }
  36. }
  37. }
  38. }
3.二叉树遍历节点

遍历分为3种:

以下3种遍历都是以根节点为参考物

  • 前序遍历:遍历顺序是:根节点->左子树->右子树
  • 中序遍历:遍历顺序是:左子树->根节点->右子树
  • 后序遍历:遍历顺序是:左子树->右子树->根节点
  1.   /**
  2. * 前序遍历
  3. */
  4. public void preOrderTraversal() {
  5. traversal(root, PRE_ORDER);
  6. }
  7. /**
  8. * 后续遍历
  9. */
  10. public void postOrderTraversal() {
  11. traversal(root, POST_ORDER);
  12. }
  13. /**
  14. * 中序遍历
  15. */
  16. public void inOrderTraversal() {
  17. traversal(root, IN_ORDER);
  18. }
  19. /**
  20. * 遍历方法
  21. */
  22. private void traversal(TreeNode<T> node, int order) {
  23. //1.定义两个临时节点变量,current表示当前节点指针,parent表示当前指针的父节点
  24. TreeNode<T> current = node;
  25. TreeNode<T> parent;
  26. //1.如果是空树,直接返回
  27. if (node == null) {
  28. return;
  29. } else {
  30. //前序遍历
  31. if (order == PRE_ORDER) {
  32. //打印根节点
  33. System.out.println(node.getIndex() + ":" +node.getData());
  34. //遍历左子树(从根节点的左子树的根节点开始)
  35. traversal(node.getLeftChild(), order);
  36. //遍历右子树(林根节点的右子树的根节点开始)
  37. traversal(node.getRightChild(), order);
  38. //后序遍历
  39. } else if (order == POST_ORDER) {
  40. //遍历左子树(从根节点的左子树的根节点开始)
  41. traversal(node.getLeftChild(), order);
  42. //遍历右子树(林根节点的右子树的根节点开始)
  43. traversal(node.getRightChild(), order);
  44. //打印根节点
  45. System.out.println(node.getIndex() + ":" +node.getData());
  46. //中序遍历
  47. } else {
  48.    //遍历左子树(从根节点的左子树的根节点开始) 
  49. traversal(node.getLeftChild(), order);
  50. System.out.println(node.getIndex() + ":" +node.getData());
  51. //打印根节点
  52. //遍历右子树(林根节点的右子树的根节点开始)
  53. traversal(node.getRightChild(), order);
  54. }
  55. }
  56. }
4.二叉树删除节点
(1)二叉树删除节点思路说明:

删除的节点一般分为以下4种情况:

  • 第一种情况:被删除的节点是叶子节点,即这没有子节点,那么的它的删除过程如下:

    • 清除节点本身的数据
    • 删除当前节点的父节点的子节点指向

删除叶子节点

  • 第二种情况:被删除的节点有左子树节点
    • 获取当前删除节点的父节点和左子树节点,并清除删除节点的数据和其左子树节点的指向
    • 将原父节点的右子树(或左子树,具体看删除节点是原父节点的左子树还是右子树)指向删除节点的左子树节点

删除只有左子树节点的节点

  • 第三种情况:被删除的节点有右子树节点
    • 获取当前删除节点的父节点和右子树节点,并清除删除节点的数据和右子树节点的指向
    • 将原父节点的左子树 (或左子树,具体看删除节点是原父节点的左子树还是右子树)指向删除节点的右子树节点

删除只有右子树节点的节点

  • 第四种情况:被删除的节点有左右子树节点
    • 从当前删除节点的右子树开始查找其中序后继节点,并将后继节点的父节点的左子树节点指向为null
    • 清除原删除节点的数据
    • 修改当删除节点的父节点的子节点指向(根据原删除节点是左子树还是右子树来修改其子树指向),指向为后继节点,并将后继节点的左子树节点指向原删除节点的左子树,将后继节点的右子树指向原删除节点的右子树

删除有左子树也有右子树节点的节点

(2)实现二叉树节点的删除

如图:有这种一颗树:

要删除的节点树

  1. /**
  2. * 获取中序后继节点
  3. * @param deleteNode 被删除的节点
  4. * @return
  5. */
  6. private TreeNode<T> getSuccessor(TreeNode<T> deleteNode) {
  7. //后继节点
  8. TreeNode<T> successorNode = deleteNode;
  9. //后继节点的父节点
  10. TreeNode<T> parent = deleteNode;
  11. //当前查找的节点指针
  12. TreeNode<T> current = deleteNode.getRightChild();
  13. while (current != null) {
  14. //后继节点父节点为上一次的后继节点
  15. parent = successorNode;
  16. //后继节点为当前节点
  17. successorNode = current;
  18. //当前指针往左子树继续查找
  19. current = current.getLeftChild();
  20. }
  21. //如果后继节点不是删除节点的右子树节点
  22. if (successorNode != deleteNode.getRightChild()) {
  23. //设置后继节点的父节点的左子节点为后继节点的右子节点
  24. parent.setLeftChild(successorNode.getRightChild());
  25. //设置后续节点的右子节点为原删除节点的右子节点
  26. successorNode.setRightChild(deleteNode.getRightChild());
  27. }
  28. return successorNode;
  29. }
  30.    //删除节点 
  31. public boolean remove(Long index) {
  32. //1.从根节点开始
  33. if (root == null) {
  34. return false;
  35. }
  36. //2.定义两个节点,一个当前指针节点,一个当前指针的父节点
  37. TreeNode<T> current = root;
  38. TreeNode<T> parent = root;
  39. //要删除的节点是左子树节点
  40. boolean isLeftChild = true;
  41. //3.查找节点,一直查到删除节点与循环的节点值一样为止
  42. while (current.getIndex() != index) {
  43. if (current.getIndex() < index) {
  44. parent = current;
  45. current = current.getRightChild();
  46. isLeftChild = false;
  47. } else {
  48. parent = current;
  49. current = current.getLeftChild();
  50. isLeftChild = true;
  51. }
  52. //未查找到相应的节点
  53. if (current == null) {
  54. return false;
  55. }
  56. }
  57. //4.根据被删除节点的位置,来进行相应的删除操作
  58. //第一种情况:被删除的节点是一个叶子节点,直接删除
  59. if (current.getLeftChild() == null && current.getRightChild() == null) {
  60. //被删除的节点是左子树节点
  61. //如果删除的节点是根节点,那么根节点root为null
  62. if (current == root) {
  63. root = null;
  64. }else if (isLeftChild) {
  65. //如果删除的节点是左子树上,那么删除节点的父节点的左子树就为null
  66. parent.setLeftChild(null);
  67. } else {
  68. //被删除的节点是右子树节点上,那么删除节点的父节点的右子树就为null
  69. parent.setRightChild(null);
  70. }
  71. current = null;
  72. } else if (current.getRightChild() == null) {
  73. //第二种情况:被删除的节点只有左子树
  74. //如果删除的节点是根节点,那么删除节点的左子树节点变成新的根节点
  75. if (current == root) {
  76. root = current.getLeftChild();
  77. } else if (isLeftChild) {
  78. //如果删除的节点在左子树上,那么删除节点的左子树节点变成原删除节点父节点的左子树节点
  79. parent.setLeftChild(current.getLeftChild());
  80. } else {
  81. //如果删除的节点在右子树上,那么删除节点的左子树节点变成原删除节点父节点的右子树节点
  82. parent.setRightChild(current.getLeftChild());
  83. }
  84. current = null;
  85. } else if (current.getLeftChild() == null) {
  86. //第三种情况:被删除的节点只有右子树
  87. //如果删除的节点是根节点,那么删除节点的右子树节点变成新的根节点
  88. if (current == root) {
  89. root = current.getRightChild();
  90. } else if (isLeftChild) {
  91. //如果删除节点在左子树上,那么删除节点的右子树节点变成新的删除节点父节点的左子树节点
  92. parent.setLeftChild(current.getRightChild());
  93. } else {
  94. //如果删除节点在右子树上,那么删除节点的左子树节点变成新的删除节点父节点的右子树节点
  95. parent.setRightChild(current.getRightChild());
  96. }
  97. current = null;
  98. } else {
  99. //第四种情况:被删除的节点既有左子树,又有右子树
  100. //查找中序后续节点
  101. TreeNode<T> successorNode = getSuccessor(current);
  102. //如果要删除的节点为根节点,那么后序中继节点为新的根节点
  103. if (current == root) {
  104. root = successorNode;
  105. }else if (isLeftChild) {
  106. //如果删除节点在左子树上,那么后续节点为新的删除节点的父节点的左子树节点
  107. parent.setLeftChild(successorNode);
  108. } else {
  109. //如果删除节点在右子树上,那么后继节点为新的删除节点的父节点的右子树节点
  110. parent.setRightChild(successorNode);
  111. }
  112. successorNode.setLeftChild(current.getLeftChild());
  113. current = null;
  114. }
  115. //树节点个数减1
  116. size --;
  117. return true;
  118. }