Code666 (代码贴、代码片段)

[Java] java二叉树查找、遍历、添加与删除 →→→→→进入此内容的聊天室

来自 , 2019-03-21, 写在 Java, 查看 165 次.
URL http://www.code666.cn/view/11dd08ef
  1. package com.structures.tree;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.NoSuchElementException;
  5. import java.util.Stack;
  6.  
  7. /*
  8.  * Binary Search Tree
  9.  */
  10. public class Searchtree {
  11.         public Integer data;
  12.         public Searchtree left;
  13.         public Searchtree right;
  14.  
  15.         public void setData(Integer data) {
  16.                 this.data = data;
  17.         }
  18.  
  19.         public Searchtree(Integer number) {
  20.                 this.data = number;
  21.         }
  22.  
  23.         public void setLeft(Searchtree left) {
  24.                 this.left = left;
  25.         }
  26.  
  27.         public void setRight(Searchtree right) {
  28.                 this.right = right;
  29.         }
  30.  
  31.         // add
  32.         public void add(int number) {
  33.                 if (number <= this.data)
  34.                         add(number, this, this.left, 0);
  35.                 else
  36.                         add(number, this, this.right, 1);
  37.         }
  38.  
  39.         private void add(int number, Searchtree father, Searchtree child, int tag) {
  40.                 if (child == null) {
  41.                         child = new Searchtree(number);
  42.                         if (tag == 0)
  43.                                 father.setLeft(child);
  44.                         else
  45.                                 father.setRight(child);
  46.                 } else {
  47.                         // attention: here must be child
  48.                         if (number <= child.data)// add to left
  49.                                 add(number, child, child.left, 0);
  50.                         else
  51.                                 // add to right
  52.                                 add(number, child, child.right, 1);
  53.  
  54.                 }
  55.         }
  56.  
  57.         // find
  58.         public Searchtree find(int number) {
  59.                 if (number < data) {
  60.                         return find(number, this);
  61.                 } else if (number > data) {
  62.                         return find(number, this);
  63.                 } else {
  64.                         return find(number, this);
  65.                 }
  66.         }
  67.  
  68.         private Searchtree find(int number, Searchtree tree) {
  69.                 if (tree == null)
  70.                         throw new NoSuchElementException(
  71.                                         "no such element in the binary search tree");
  72.                 if (number < tree.data) {
  73.                         return find(number, tree.left.left);
  74.                 } else if (number > tree.data) {
  75.                         return find(number, tree.right);
  76.                 } else
  77.                         return tree;
  78.         }
  79.  
  80.         // findPrevious
  81.         private ArrayList<Searchtree> trees = new ArrayList<Searchtree>();
  82.  
  83.         private Searchtree findPrevious(int number, Searchtree tree) {
  84.                 if (tree == null)
  85.                         throw new NoSuchElementException(
  86.                                         "no such element in the binary search tree");
  87.                 trees.add(tree);
  88.                 if (number < tree.data) {
  89.                         return findPrevious(number, tree.left);
  90.                 } else if (number > tree.data) {
  91.                         return findPrevious(number, tree.right);
  92.                 } else {
  93.                         Searchtree pre = trees.get(trees.size() - 2);
  94.                         trees = null;
  95.                         return pre;
  96.                 }
  97.         }
  98.  
  99.         // min
  100.         public Searchtree findMin(Searchtree tree) {
  101.                 if (tree == null)
  102.                         throw new NoSuchElementException(
  103.                                         "no such element in the binary search tree");
  104.                 else if (tree.left == null)
  105.                         return tree;
  106.                 else
  107.                         return findMin(tree.left);
  108.  
  109.         }
  110.  
  111.         // max
  112.         public Searchtree findMax(Searchtree tree) {
  113.                 if (tree == null)
  114.                         throw new NoSuchElementException(
  115.                                         "no such element in the binary search tree");
  116.                 else if (tree.right == null)
  117.                         return tree;
  118.                 else
  119.                         return findMax(tree.right);
  120.         }
  121.        
  122.         public Searchtree remove(int number) {
  123.                 return remove(number, this);
  124.         }
  125.         /*remove
  126.          *  是最困难的，请大家参考一下，递归有点晕。大家阅读书理解吧。
  127.          *  参考代码：《数据结构与算法分析》-C语言描述 英文版
  128.          *  第102-103页
  129.          * ISBN: 9787115139849
  130.          * detail：http://book.douban.com/subject/1444648/
  131.          */
  132.         public Searchtree remove(int number, Searchtree tree) {
  133.                 Searchtree delete = null;
  134.                 if (tree == null)
  135.                         throw new IndexOutOfBoundsException("tree size is 0");
  136.                 else if (number < tree.data) {
  137.                         // go left
  138.                         tree.left = remove(number, tree.left);
  139.                 } else if (number > tree.data) {
  140.                         // go right
  141.                         tree.right = remove(number, tree.right);
  142.                         // found element to be remove
  143.                 } else if (tree.left != null && tree.right != null) {
  144.                         // two children
  145.                         // replace with the smallest in right tree
  146.                         delete = findMin(tree.right);
  147.                         tree.setData(delete.data);
  148.                         tree.setRight(remove(tree.data, tree.right));
  149.                         delete = null;
  150.                 } else {
  151.                         // one or zero child
  152.                         delete = tree;
  153.                         if (delete.left == null) {
  154.                                 tree = tree.right;
  155.                         } else if (delete.right == null) {
  156.                                 tree = tree.left;
  157.                         }
  158.                         delete = null;
  159.                 }
  160.  
  161.                 return tree;
  162.         }
  163.  
  164.         // 先序遍历 preorder traversal
  165.         public void preorder() {
  166.                 System.out.print(data + " ");
  167.                 if (left != null)
  168.                         left.preorder();
  169.                 if (right != null)
  170.                         right.preorder();
  171.  
  172.         }
  173.  
  174.         // 中序遍历 inorder traversal
  175.         public void inorder() {
  176.                 if (left != null)
  177.                         left.inorder();
  178.                 System.out.print(data + " ");
  179.                 if (right != null)
  180.                         right.inorder();
  181.  
  182.         }
  183.  
  184.         // 后序遍历 postorder traversal
  185.         public void postorder() {
  186.                 if (left != null)
  187.                         left.postorder();
  188.  
  189.                 if (right != null)
  190.                         right.postorder();
  191.                 System.out.print(data + " ");
  192.         }
  193.  
  194.         public int getDepth(Searchtree root) {
  195.                 int depth;
  196.                 if (root == null)
  197.                         return 0;
  198.                 else {
  199.                         depth = 1 + Math.max(getDepth(root.left), getDepth(root.right));
  200.                         return depth;
  201.                 }
  202.         }
  203.  
  204.         public static void main(String[] args) {
  205.                 Searchtree tree = new Searchtree(5);
  206.                 tree.add(3);
  207.                 tree.add(7);
  208.                 tree.add(2);
  209.                 tree.add(4);
  210.                 tree.add(6);
  211.                 tree.add(8);
  212.                 tree.add(1);
  213.                 tree.add(1);
  214.                 tree.remove(1);
  215.                 // tree.remove(2, tree);
  216.                 //tree.remove(tree.data);
  217.                 tree.preorder();
  218.                 System.out.println();
  219.                 tree.inorder();
  220.                 System.out.println();
  221.                 System.out.println(tree.getDepth(tree));
  222.                 System.out.println(tree.find(7).data);
  223.                 System.out.println(tree.findPrevious(8, tree).data);
  224.                
  225.         }
  226.  
  227. }
  228.  
  229. //java/5567

回复 "java二叉树查找、遍历、添加与删除"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666