二叉排序树BST代码(JAVA)

 
 
  1. publicclassTest{
  2.     publicstaticvoid main(String[] args){
  3.         int[] r =newint[]{5,1,3,4,6,7,2,8,9,0};
  4.         BST binarySearchTree =new BST(r);
  5.         binarySearchTree.inOrder();
  6.         System.out.println();
  7.         binarySearchTree.searchBST(6);//查找成功
  8.         System.out.println();
  9.         binarySearchTree.searchBST(10);//查找失败->插入
  10.         System.out.println();
  11.     }
  12.  
  13. }
 
 
  1. publicclass BST {
  2.  
  3.     //二叉树结点
  4.     publicclassBiNode{
  5.         int data;
  6.         BiNode left;
  7.         BiNode right;
  8.  
  9.         BiNode(int data,BiNode left,BiNode right){
  10.             this.data = data;
  11.             this.left = left;
  12.             this.right = right;
  13.         }
  14.     }
  15.  
  16.     privateBiNode root = null;
  17.  
  18.     BST(int[] r)
  19.     {
  20.         for(int i =0; i < r.length; i++)
  21.         {
  22.             BiNode s =newBiNode(r[i],null,null);
  23.             root = insertBST(root, s);
  24. //            insertBST1(s);
  25.         }
  26.     }
  27.  
  28.     //插入(递归)
  29.     publicBiNode insertBST(BiNode head,BiNode s)
  30.     {
  31.         if(head == null){
  32.             head = s;
  33.             return head;
  34.         }
  35.  
  36.         if(s.data < head.data)
  37.             head.left = insertBST(head.left, s);
  38.         else
  39.            head.right = insertBST(head.right,s);
  40.  
  41.         return  head;
  42.     }
  43.  
  44.     //插入(非递归:循环、用临时变量保存过程)
  45.     publicvoid insertBST1(BiNode s)
  46.     {
  47.         if(root == null){
  48.             root = s;
  49.             return;
  50.         }
  51.  
  52.         BiNode temp = root;//需要临时结点记录
  53.  
  54.         while(true)
  55.         {
  56.             if(s.data < temp.data)
  57.             {
  58.                 if(temp.left == null)
  59.                 {
  60.                     temp.left = s;
  61.                     return;
  62.                 }
  63.                 temp = temp.left;
  64.             }
  65.             else
  66.             {
  67.                 if(temp.right == null)
  68.                 {
  69.                     temp.right = s;
  70.                     return;
  71.                 }
  72.                 temp = temp.right;
  73.             }
  74.         }
  75.     }
  76.  
  77.  
  78.     //查找:成功->返回;失败:插入
  79.     publicBiNode searchBST(int a)
  80.     {
  81.         BiNode s1 = searchBST(root,a);
  82.         if(s1 == null){
  83.             BiNode s2 =newBiNode(a,null,null);
  84.             insertBST1(s2);
  85.             System.out.println("search fail ; insert success: "+ s2.data);
  86.             inOrder();
  87.             return s2;
  88.         }else{
  89.             System.out.println("search success: "+ s1.data);
  90.             return s1;
  91.         }
  92.     }
  93.     //查找
  94.     privateBiNode searchBST(BiNode head,int a)
  95.     {
  96.         if(head == null)
  97.             return null;
  98.  
  99.         if(a < head.data)
  100.             return searchBST(head.left, a);
  101.         elseif(a > head.data)
  102.             return searchBST(head.right, a);
  103.         else
  104.             return head;
  105.     }
  106.  
  107. //    删除
  108. //    删除f的孩子p
  109.     publicvoid deleteLeftBST(BiNode f,BiNode p)
  110.     {
  111.         if(p.left == null && p.right == null)    //p为叶子
  112.         {
  113.             f.left = null;
  114.             p = null;
  115.         }
  116.         elseif(p.right == null)                  //p只有左子树
  117.         {
  118.             f.left = p.left;
  119.             p = null;
  120.         }
  121.         elseif(p.left == null)                  //p只有右子树
  122.         {
  123.             f.left = p.right;
  124.             p = null;
  125.         }
  126.         else                                       //p的左右子树均不空
  127.         {
  128.             BiNode par = p, s = par.right;          //用par s 去查找p的右子树的最左下结点
  129.             while(s.left != null)
  130.             {
  131.                 par = s;
  132.                 s = par.left;
  133.             }
  134.             p.data = s.data;                       //交换最左下结点s与p结点数据
  135.  
  136.                                                     //剪枝(删除s结点)
  137.             if(par == p)                          //处理特殊情况
  138.             {
  139.                 par.right = s.right;
  140.                 s = null;
  141.             }
  142.             else                                   //处理一般情况
  143.             {
  144.                 par.left = s.right;
  145.                 s = null;
  146.             }
  147.  
  148.         }
  149.     }
  150.  
  151.     //先序遍历
  152.     publicvoid preOrder(){
  153.         System.out.print("preOrder traversal with recursion:");
  154.         preOrder(root);
  155.         System.out.println();
  156.     }
  157.     //递归
  158.     privatevoid preOrder(BiNode root){
  159.         if(root == null)return;
  160.  
  161.         System.out.print(root.data);       //访问结点
  162.         preOrder(root.left);
  163.         preOrder(root.right);
  164.     }
  165.  
  166.     //中序遍历
  167.     publicvoid inOrder(){
  168.         System.out.print("inOrder traversal with recursion:");
  169.         inOrder(root);
  170.         System.out.println();
  171.     }
  172.     //递归
  173.     privatevoid inOrder(BiNode root){
  174.         if(root == null)//访问结点
  175.             return;
  176.  
  177.         inOrder(root.left);
  178.         System.out.print(root.data);      //访问结点
  179.         inOrder(root.right);
  180.     }
  181.  
  182.     //后序遍历
  183.     publicvoid postOrder(){
  184.         System.out.print("postOrder traversal with recursion:");
  185.         postOrder(root);
  186.         System.out.println();
  187.     }
  188.     //递归
  189.     privatevoid postOrder(BiNode root){
  190.         if(root == null)return;
  191.  
  192.         postOrder(root.left);
  193.         postOrder(root.right);
  194.         System.out.print(root.data);     //访问结点
  195.     }
  196. }
 
输出:
  1. inOrder traversal with recursion:0123456789
  2.  
  3. search success:6
  4.  
  5. search fail ; insert success:10
  6. inOrder traversal with recursion:012345678910
 
 
 
上一篇:【面试题】GC Root都有哪些?


下一篇:TCP连接建立和关闭中的疑难点