欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java創(chuàng)建二叉搜索樹,實現(xiàn)搜索,插入,刪除的操作實例

 更新時間:2017年12月04日 10:05:02   作者:Marksinoberg  
下面小編就為大家分享一篇Java創(chuàng)建二叉搜索樹,實現(xiàn)搜索,插入,刪除的操作實例,具有很好的參考價值,希望對大家有所幫助

Java實現(xiàn)的二叉搜索樹,并實現(xiàn)對該樹的搜索,插入,刪除操作(合并刪除,復制刪除)

首先我們要有一個編碼的思路,大致如下:

1、查找:根據(jù)二叉搜索樹的數(shù)據(jù)特點,我們可以根據(jù)節(jié)點的值得比較來實現(xiàn)查找,查找值大于當前節(jié)點時向右走,反之向左走!

2、插入:我們應(yīng)該知道,插入的全部都是葉子節(jié)點,所以我們就需要找到要進行插入的葉子節(jié)點的位置,插入的思路與查找的思路一致。

3、刪除:

1)合并刪除:一般來說會遇到以下幾種情況,被刪節(jié)點有左子樹沒右子樹,此時要讓當前節(jié)點的父節(jié)點指向當前節(jié)點的左子樹;當被刪節(jié)點有右子樹沒有左子樹,此時要讓當前節(jié)點的父節(jié)點指向該右子樹;當被刪節(jié)點即有左子樹又有右子樹時,我們可以找到被刪節(jié)點的左子樹的最右端的節(jié)點,然后讓這個節(jié)點的右或者左“指針”指向被刪節(jié)點的右子樹

2)復制刪除:復制刪除相對而言是比較簡單的刪除操作,也是最為常用的刪除操作。大致也有以下三種情況:當前節(jié)點無左子樹有右子樹時,讓當前右子樹的根節(jié)點替換被刪節(jié)點;當前節(jié)點無右子樹有左子樹時,讓當前左子樹的根節(jié)點替換被刪除節(jié)點;當前被刪節(jié)點既有左子樹又有右子樹時,我們就要找到被刪節(jié)點的替身,可以在被刪節(jié)點的左子樹中找到其最右端的節(jié)點,并讓這個節(jié)點的值賦給被刪節(jié)點,然后別忘了讓此替身節(jié)點的父節(jié)點指向替身的“指針”為空,(其實在Java中無關(guān)緊要了,有垃圾處理機制自動進行處理)。你也可以在當前被刪節(jié)點的右子樹的最左端的節(jié)點作為替身節(jié)點來實現(xiàn)這一過程。

接下來就上代碼吧。

首先是## 二叉搜索樹節(jié)點類 ##

package SearchBinaryTree;

public class SearchBinaryTreeNode<T> {
  T data;
  public SearchBinaryTreeNode<T> leftChild;
  public SearchBinaryTreeNode<T> rightChild;

  public SearchBinaryTreeNode(){
    this.data=null;
    this.leftChild=this.rightChild=null;
  }

  public SearchBinaryTreeNode(T da){
    this.data=da;
    this.leftChild=this.rightChild=null;
  }

  public SearchBinaryTreeNode(T da,SearchBinaryTreeNode<T> left,SearchBinaryTreeNode<T>right){
    this.data=da;
    this.leftChild=left;
    this.rightChild=right;
  }

  public T getData() {
    return data;
  }
  public void setData(T data) {
    this.data = data;
  }
  public SearchBinaryTreeNode<T> getLeftChild() {
    return leftChild;
  }
  public void setLeftChild(SearchBinaryTreeNode<T> leftChild) {
    this.leftChild = leftChild;
  }
  public SearchBinaryTreeNode<T> getRightChild() {
    return rightChild;
  }
  public void setRightChild(SearchBinaryTreeNode<T> rightChild) {
    this.rightChild = rightChild;
  }

  public boolean isLeaf(){
    if(this.leftChild==null&&this.rightChild==null){
      return true;
    }
    return false;
  }


}

實現(xiàn)二叉搜索樹

package SearchBinaryTree;


public class SearchBinaryTree<T> {
  SearchBinaryTreeNode<T> root;

  public boolean isEmpty(){
    if(root==null){
      return true;
    }
    return false;
  }

  public void Visit(SearchBinaryTreeNode<T> root){
    if(root==null){
      System.out.println("this tree is empty!");
    }
    System.out.println(root.getData());
  }

  public SearchBinaryTreeNode<T> getRoot(){
    if(root==null){
      root=new SearchBinaryTreeNode<T>();
    }
    return root;
  }

  public SearchBinaryTree(){
    this.root=null;
  }

  /*
   * 創(chuàng)造一顆二叉樹
   */
  public void CreateTree(SearchBinaryTreeNode<T> node, T data) {
    if (root == null) {
      root = new SearchBinaryTreeNode<T>();
    } else {
      if (Math.random() > 0.5) {          //采用隨機方式創(chuàng)建二叉樹
        if (node.leftChild == null) {
          node.leftChild = new SearchBinaryTreeNode<T>(data);
        } else {
          CreateTree(node.leftChild, data);
        }
      } else {
        if (node.rightChild == null) {
          node.rightChild = new SearchBinaryTreeNode<T>(data);
        } else {
          CreateTree(node.rightChild, data);
        }
      }
    }
  }

  /*
   * 在二查搜索樹中進行搜索
   */
  public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
    SearchBinaryTreeNode<T> current=root;
    while((root!=null)&&(current.getData()!=value)){
      //需要注意的是java中泛型無法比較大小,在實際的使用時我們可以使用常見的數(shù)據(jù)類型來替代這個泛型,這樣就不會出錯了
      current=(value<current.getData()?search(current.leftChild,value):search(current.rightChild,value));
    }
    return current;
  }

  public SearchBinaryTreeNode<T> insertNode( T value){
    SearchBinaryTreeNode<T> p=root,pre=null;
    while(p!=null){
      pre=p;
      //需要注意的是java中泛型無法比較大小,在實際的使用時我們可以使用常見的數(shù)據(jù)類型來替代這個泛型,這樣就不會出錯了
      if(p.getData()<value){
        p=p.rightChild;
      }else{
        p=p.leftChild;
      }
    }
    if(root==null){
      root=new SearchBinaryTreeNode<T>(value);
    }else if(pre.getData()<value){
      pre.rightChild=new SearchBinaryTreeNode<T>(value);
    }else{
      pre.leftChild=new SearchBinaryTreeNode<T>(value);
    }
  }

  /*
   * 合并刪除
   */
  public void deleteByMerging(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> temp=node;
    if(node!=null){
      //若被刪除節(jié)點沒有右子樹,用其左子樹的根節(jié)點來代替被刪除節(jié)點
      if(node.rightChild!=null){
        node=node.leftChild;
      }else if(node.leftChild==null){
        //若被刪節(jié)點沒有左子樹,用其有字數(shù)的最左端的節(jié)點代替被刪除的節(jié)點
        node=node.rightChild;
      }else{
        //如果被刪節(jié)點左右子樹均存在
        temp=node.leftChild;
        while(temp.rightChild!=null){
          temp=temp.rightChild;   //一直查找到左子樹的右節(jié)點
        }

        //將查找到的節(jié)點的右指針賦值為被刪除節(jié)點的右子樹的根
        temp.rightChild=node.rightChild;
        temp=node;
        node=node.leftChild;
      }
      temp=null;
    }
  }

  /*
   * 復制刪除
   */
  public void deleteByCoping(SearchBinaryTreeNode<T> node){
    SearchBinaryTreeNode<T> pre=null;
    SearchBinaryTreeNode<T> temp=node;
    //如果被刪節(jié)點沒有右子樹,用其左子樹的根節(jié)點來代替被刪除節(jié)點
    if(node.rightChild==null){
      node=node.leftChild;
    }else if(node.leftChild==null){
      node=node.rightChild;
    }else{
      //如果被刪節(jié)點的左右子樹都存在
      temp=node.leftChild;
      pre=node;
      while(temp.rightChild!=null){
        pre=temp;
        temp=temp.rightChild;   //遍歷查找到左子樹的最右端的節(jié)點
      }
      node.data=temp.data;      //進行賦值操作
      if(pre==node){
        pre.leftChild=node.leftChild;
      }else{
        pre.rightChild=node.rightChild;
      }
    }
    temp=null;
  }

}

測試類

package SearchBinaryTree;

public class SearchBinaryTreeTest {

  public static void main(String []args){
    SearchBinaryTree<Integer> tree=new SearchBinaryTree<Integer>();
    for(int i=1;i<10;i++){
      tree.CreateTree(new SearchBinaryTreeNode<Integer>(), i);
    }

    //搜索
    tree.search(tree.root, 7);

    //合并刪除
    tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8));

    //復制刪除
    tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6));
  }

}

好了,就是這樣!

以上這篇Java創(chuàng)建二叉搜索樹,實現(xiàn)搜索,插入,刪除的操作實例就是小編分享給大家的全部內(nèi)容了,希望能給大家一個參考,也希望大家多多支持腳本之家。

相關(guān)文章

  • 全面解析SpringBoot配置文件

    全面解析SpringBoot配置文件

    這篇文章主要為大家全面的解析SpringBoot-配置文件,文中附含詳細的圖文示例代碼,以便同學們能更好的理解,有需要的同學可以借鑒參考下
    2021-09-09
  • SpringSecurity從數(shù)據(jù)庫中獲取用戶信息進行驗證的案例詳解

    SpringSecurity從數(shù)據(jù)庫中獲取用戶信息進行驗證的案例詳解

    這篇文章主要介紹了SpringSecurity從數(shù)據(jù)庫中獲取用戶信息進行驗證的案例詳解,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-01-01
  • Java之Arrays的各種功能和用法總結(jié)

    Java之Arrays的各種功能和用法總結(jié)

    數(shù)組在?Java?中是一種常用的數(shù)據(jù)結(jié)構(gòu),用于存儲和操作大量數(shù)據(jù)。Arrays?是我們在處理數(shù)組時的一把利器。它提供了豐富的方法和功能,使得數(shù)組操作變得更加簡單、高效和可靠。接下來我們一起看看?Arrays?的各種功能和用法,,需要的朋友可以參考下
    2023-05-05
  • Jenkins Host key verification failed問題解決

    Jenkins Host key verification failed問題解決

    這篇文章主要介紹了Jenkins Host key verification failed問題解決,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-11-11
  • 通過實例解析spring bean之間的關(guān)系

    通過實例解析spring bean之間的關(guān)系

    這篇文章主要介紹了通過實例解析spring bean之間的關(guān)系,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-01-01
  • 學習Java之IO流的基礎(chǔ)概念詳解

    學習Java之IO流的基礎(chǔ)概念詳解

    這篇文章主要給大家介紹了Java中的IO流,我們首先要搞清楚一件事,就是為什么需要IO流這個東西,但在正式學習IO流的使用之前,小編有必要帶大家先了解一下IO流的基本概念,需要的朋友可以參考下
    2023-09-09
  • 一文帶你搞懂什么是BIO

    一文帶你搞懂什么是BIO

    BIO英文全名是 blocking IO,也叫做 阻塞IO,是最容易理解、最容易實現(xiàn)的IO工作方式,本文就來通過一些簡單的示例為大家講講什么是BIO吧
    2023-06-06
  • MybatisPlus代碼生成器的使用方法詳解

    MybatisPlus代碼生成器的使用方法詳解

    在這里我將展示如何自動生成實體類、控制層、服務(wù)層、mapper等代碼,這些基礎(chǔ)的代碼全部不需要我們手動創(chuàng)建,由MybatisPlus自動幫我們完成,我們只需要告訴MybatisPlus怎么生成這些代碼就可以了,在此之前我們需要配置好測試的環(huán)境,數(shù)據(jù)庫和表數(shù)據(jù) ,需要的朋友可以參考下
    2021-06-06
  • Java使用JDK與Cglib動態(tài)代理技術(shù)統(tǒng)一管理日志記錄

    Java使用JDK與Cglib動態(tài)代理技術(shù)統(tǒng)一管理日志記錄

    這篇文章主要介紹了Java使用JDK與Cglib動態(tài)代理技術(shù)統(tǒng)一管理日志記錄,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-05-05
  • Java基礎(chǔ)之命名規(guī)范的詳解

    Java基礎(chǔ)之命名規(guī)范的詳解

    這篇文章主要介紹了Java基礎(chǔ)之命名規(guī)范的詳解,文中有非常詳細的代碼示例,對正在學習Java基礎(chǔ)的小伙伴們有很好地幫助,需要的朋友可以參考下
    2021-05-05

最新評論