Java二叉排序树（转）

2022-11-09 21:03:58

一、二叉排序树定义

1.二叉排序树的定义

　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。

上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。

Java二叉排序树（转）

2.二叉排序树的性质
按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

3.二叉排序树的插入
在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。 　　
插入过程：
若二叉排序树为空，则待插入结点*S作为根结点插入到空树中； 　　
当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

4.二叉排序树的查找
假定二叉排序树的根结点指针为 root ，给定的关键字值为 K ，则查找算法可描述为：
　　① 置初值： q ＝ root ；
　　② 如果 K ＝ q －＞ key ，则查找成功，算法结束；
　　③ 否则，如果 K ＜ q －＞ key ，而且 q 的左子树非空，则将 q 的左子树根送 q ，转步骤②；否则，查找失败，结束算法；
　　④ 否则，如果 K ＞ q －＞ key ，而且 q 的右子树非空，则将 q 的右子树根送 q ，转步骤②；否则，查找失败，算法结束。

5.二叉排序树的删除
假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论： 　　
⑴ 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。 　　
⑵ 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。 　　
⑶ 若结点*p的左、右子树均非空，先找到*p的中序前趋(或后继)结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。② 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。

6、二叉树的遍历

二叉树的遍历有三种方式，如下：
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

二、代码编写

1、树节点类的定义

  1. package com.lin;
  2. /**
  3. * 功能概要：
  4. *
  5. * @author linbingwen
  6. * @since  2015年8月29日
  7. */
  8. public class TreeNode {
  9. public Integer data;
  10. /*该节点的父节点*/
  11. public TreeNode parent;
  12. /*该节点的左子节点*/
  13. public TreeNode left;
  14. /*该节点的右子节点*/
  15. public TreeNode right;
  16. public TreeNode(Integer data) {
  17. this.data = data;
  18. }
  19. @Override
  20. public String toString() {
  21. return "TreeNode [data=" + data + "]";
  22. }
  23. }

2、二叉排序树的定义

  1. package com.lin;
  2. /**
  3. * 功能概要：排序/平衡二叉树
  4. *
  5. * @author linbingwen
  6. * @since  2015年8月29日
  7. */
  8. public class SearchTree {
  9. public TreeNode root;
  10. public long size;
  11. /**
  12. * 往树中加节点
  13. * @author linbingwen
  14. * @since  2015年8月29日
  15. * @param data
  16. * @return Boolean 插入成功返回true
  17. */
  18. public Boolean addTreeNode(Integer data) {
  19. if (null == root) {
  20. root = new TreeNode(data);
  21. System.out.println("数据成功插入到平衡二叉树中");
  22. return true;
  23. }
  24. TreeNode treeNode = new TreeNode(data);// 即将被插入的数据
  25. TreeNode currentNode = root;
  26. TreeNode parentNode;
  27. while (true) {
  28. parentNode = currentNode;// 保存父节点
  29. // 插入的数据比父节点小
  30. if (currentNode.data > data) {
  31. currentNode = currentNode.left;
  32. // 当前父节点的左子节点为空
  33. if (null == currentNode) {
  34. parentNode.left = treeNode;
  35. treeNode.parent = parentNode;
  36. System.out.println("数据成功插入到二叉查找树中");
  37. size++;
  38. return true;
  39. }
  40. // 插入的数据比父节点大
  41. } else if (currentNode.data < data) {
  42. currentNode = currentNode.right;
  43. // 当前父节点的右子节点为空
  44. if (null == currentNode) {
  45. parentNode.right = treeNode;
  46. treeNode.parent = parentNode;
  47. System.out.println("数据成功插入到二叉查找树中");
  48. size++;
  49. return true;
  50. }
  51. } else {
  52. System.out.println("输入数据与节点的数据相同");
  53. return false;
  54. }
  55. }
  56. }
  57. /**
  58. * 查找数据
  59. * @author linbingwen
  60. * @since  2015年8月29日
  61. * @param data
  62. * @return TreeNode
  63. */
  64. public TreeNode findTreeNode(Integer data){
  65. if(null == root){
  66. return null;
  67. }
  68. TreeNode current = root;
  69. while(current != null){
  70. if(current.data > data){
  71. current = current.left;
  72. }else if(current.data < data){
  73. current = current.right;
  74. }else {
  75. return current;
  76. }
  77. }
  78. return null;
  79. }
  80. }

这里暂时只放了一个增加和查找的方法

3、前、中、后遍历

  1. package com.lin;
  2. import java.util.Stack;
  3. /**
  4. * 功能概要：
  5. *
  6. * @author linbingwen
  7. * @since  2015年8月29日
  8. */
  9. public class TreeOrder {
  10. /**
  11. * 递归实现前序遍历
  12. * @author linbingwen
  13. * @since  2015年8月29日
  14. * @param treeNode
  15. */
  16. public static void preOrderMethodOne(TreeNode treeNode) {
  17. if (null != treeNode) {
  18. System.out.print(treeNode.data + "  ");
  19. if (null != treeNode.left) {
  20. preOrderMethodOne(treeNode.left);
  21. }
  22. if (null != treeNode.right) {
  23. preOrderMethodOne(treeNode.right);
  24. }
  25. }
  26. }
  27. /**
  28. * 循环实现前序遍历
  29. * @author linbingwen
  30. * @since  2015年8月29日
  31. * @param treeNode
  32. */
  33. public static void preOrderMethodTwo(TreeNode treeNode) {
  34. if (null != treeNode) {
  35. Stack<TreeNode> stack = new Stack<TreeNode>();
  36. stack.push(treeNode);
  37. while (!stack.isEmpty()) {
  38. TreeNode tempNode = stack.pop();
  39. System.out.print(tempNode.data + "  ");
  40. // 右子节点不为null,先把右子节点放进去
  41. if (null != tempNode.right) {
  42. stack.push(tempNode.right);
  43. }
  44. // 放完右子节点放左子节点，下次先取
  45. if (null != tempNode.left) {
  46. stack.push(tempNode.left);
  47. }
  48. }
  49. }
  50. }
  51. /**
  52. * 递归实现中序遍历
  53. * @author linbingwen
  54. * @since  2015年8月29日
  55. * @param treeNode
  56. */
  57. public static void medOrderMethodOne(TreeNode treeNode){
  58. if (null != treeNode) {
  59. if (null != treeNode.left) {
  60. medOrderMethodOne(treeNode.left);
  61. }
  62. System.out.print(treeNode.data + "  ");
  63. if (null != treeNode.right) {
  64. medOrderMethodOne(treeNode.right);
  65. }
  66. }
  67. }
  68. /**
  69. * 循环实现中序遍历
  70. * @author linbingwen
  71. * @since  2015年8月29日
  72. * @param treeNode
  73. */
  74. public static void medOrderMethodTwo(TreeNode treeNode){
  75. Stack<TreeNode> stack = new Stack<TreeNode>();
  76. TreeNode current = treeNode;
  77. while (current != null || !stack.isEmpty()) {
  78. while(current != null) {
  79. stack.push(current);
  80. current = current.left;
  81. }
  82. if (!stack.isEmpty()) {
  83. current = stack.pop();
  84. System.out.print(current.data+"  ");
  85. current = current.right;
  86. }
  87. }
  88. }
  89. /**
  90. * 递归实现后序遍历
  91. * @author linbingwen
  92. * @since  2015年8月29日
  93. * @param treeNode
  94. */
  95. public static void postOrderMethodOne(TreeNode treeNode){
  96. if (null != treeNode) {
  97. if (null != treeNode.left) {
  98. postOrderMethodOne(treeNode.left);
  99. }
  100. if (null != treeNode.right) {
  101. postOrderMethodOne(treeNode.right);
  102. }
  103. System.out.print(treeNode.data + "  ");
  104. }
  105. }
  106. /**
  107. * 循环实现后序遍历
  108. * @author linbingwen
  109. * @since  2015年8月29日
  110. * @param treeNode
  111. */
  112. public static void postOrderMethodTwo(TreeNode treeNode){
  113. if (null != treeNode) {
  114. Stack<TreeNode> stack = new Stack<TreeNode>();
  115. TreeNode current = treeNode;
  116. TreeNode rightNode = null;
  117. while(current != null || !stack.isEmpty()) {
  118. while(current != null) {
  119. stack.push(current);
  120. current = current.left;
  121. }
  122. current = stack.pop();
  123. while (current != null && (current.right == null ||current.right == rightNode)) {
  124. System.out.print(current.data + "  ");
  125. rightNode = current;
  126. if (stack.isEmpty()){
  127. System.out.println();
  128. return;
  129. }
  130. current = stack.pop();
  131. }
  132. stack.push(current);
  133. current = current.right;
  134. }
  135. }
  136. }
  137. }

4、使用方法

  1. package com.lin;
  2. /**
  3. * 功能概要：
  4. *
  5. * @author linbingwen
  6. * @since  2015年8月29日
  7. */
  8. public class SearchTreeTest {
  9. /**
  10. * @author linbingwen
  11. * @since  2015年8月29日
  12. * @param args
  13. */
  14. public static void main(String[] args) {
  15. SearchTree tree = new SearchTree();
  16. tree.addTreeNode(50);
  17. tree.addTreeNode(80);
  18. tree.addTreeNode(20);
  19. tree.addTreeNode(60);
  20. tree.addTreeNode(10);
  21. tree.addTreeNode(30);
  22. tree.addTreeNode(70);
  23. tree.addTreeNode(90);
  24. tree.addTreeNode(100);
  25. tree.addTreeNode(40);
  26. System.out.println("=============================="+"采用递归的前序遍历开始"+"==============================");
  27. TreeOrder.preOrderMethodOne(tree.root);
  28. System.out.println();
  29. System.out.println("=============================="+"采用循环的前序遍历开始"+"==============================");
  30. TreeOrder.preOrderMethodTwo(tree.root);
  31. System.out.println();
  32. System.out.println("=============================="+"采用递归的后序遍历开始"+"==============================");
  33. TreeOrder.postOrderMethodOne(tree.root);
  34. System.out.println();
  35. System.out.println("=============================="+"采用循环的后序遍历开始"+"==============================");
  36. TreeOrder.postOrderMethodTwo(tree.root);
  37. System.out.println();
  38. System.out.println("=============================="+"采用递归的中序遍历开始"+"==============================");
  39. TreeOrder.medOrderMethodOne(tree.root);
  40. System.out.println();
  41. System.out.println("=============================="+"采用循环的中序遍历开始"+"==============================");
  42. TreeOrder.medOrderMethodTwo(tree.root);
  43. }
  44. }

输出结果：

Java二叉排序树（转）

同样，进行查找过程如下：

  1. TreeNode node = tree.findTreeNode(100);
  2. System.out.println(node);
Java二叉排序树（转）

结果是正确的

http://blog.csdn.net/evankaka/article/details/48088241

上一篇：什么是javabean及其用法（转）


下一篇：（九）Javabean与Jsp（来自那些年的笔记）