二分探索木アルゴリズムの Java 実装の詳細コード説明 (写真)-＆＃＆チュートリアル-php.cn

二分探索木は、次のように再帰的に定義できます。二分探索木は、空の二分木、または次の特性を満たす二分木です:

(1) 左のサブツリーが空でない場合、その左のサブツリー。 subtree ノード上の任意のノードのキーワードの値が、ルートノードのキーワードの値より小さい。

(2) 右のサブツリーが空でない場合、その右のサブツリー上のいずれかのノードのキーワードの値は、ルートノードのキーワードの値より大きくなります。

(3) その左右の部分木自体が二分探索木です。

パフォーマンスの観点から見ると、二分探索木のすべての非葉ノードの左右のサブツリーのノード数がほぼ同じ (バランスが取れている) 場合、二分探索木の検索パフォーマンスは次のようになります。二分探索に近いですが、連続メモリ空間での二分探索よりも優れている点は、二分探索ツリー構造の変更 (ノードの挿入と削除) に、メモリデータの大きなセグメントの移動や一定のオーバーヘッドさえ必要ないことです。二分探索木は、連続した順序で配置されたデータセットの組み合わせを表すことができるため、二分探索木は二分ソートツリーとも呼ばれ、同じデータセットを異なる二分探索木として表すことができます。二分探索木のノードのデータ構造は次のように定義されます。

struct celltype{

    records data; 

    celltype * lchild, * rchild;

}

typedef celltype * BST;

ログイン後にコピー

Java では、ノードのデータ構造は次のように定義されます。

package wx.algorithm.search.bst;

/**

 * Created by apple on 16/7/29.

 */

/**

 * @function 二叉搜索树中的节点

 */

public class Node {

    //存放节点数据

    int data;

    //指向左子节点

    Node left;

    //指向右子节点

    Node right;

    /**

     * @function 默认构造函数

     * @param data 节点数据

     */

    public Node(int data) {

        this.data = data;

        left = null;

        right = null;

    }

}

ログイン後にコピー

Search

そして、二分探索木の検索プロセスは、 root ノード、if クエリのキーワードがノードのキーワードと等しい場合、ヒットします。そうでない場合、クエリキーワードがノードキーワードより小さい場合、左の子に入力されます。ノードキーワードより大きい場合は、右側の息子に入ります。左側の息子または右側の息子のポインタが null の場合は、対応するキーワードが見つからないことが報告されます。

BST Search(keytype k, BST F){

    //在F所指的二叉查找树中查找关键字为k的记录。若成功，则返回响应结点的指针，否则返回空

    if(F == NULL) //查找失败

        return NULL;

    else if(k == F -> data.key){ //查找成功

        return F;

    }

    else if (k < F -> data.key){ //查找左子树

        return Search(k,F -> lchild);    

    }

    else if (k > F -> data.key){ //查找右子树

        return Search(k,F -> rchild);

    }

}

ログイン後にコピー

挿入

新しいレコード R を二分探索ツリーに挿入します。挿入後に二分探索ツリーの構造プロパティが破壊されないことを確認する必要があります。したがって、挿入操作を実行するには、まず R がどこにあるかを調べる必要があります。検索時には、前述の再帰アルゴリズムが引き続き使用されます。検索が失敗した場合、R を含むノードが空のサブツリーの位置に挿入されます。検索が成功した場合、挿入は実行されず、操作は終了します。

void Insert(records R, BST &F){

        //在F所指的二叉查找树中插入一个新纪录R

        if(F == NULL){

             F = new celltype;

             F -> data = R;

             F -> lchild = NULL;

             F -> rchild = NULL;

        }

        else if (R.key < F -> data.key){

             Insert(R,F -> lchild);

            }else if(R.key > F -> data.key){

             Insert(R,F -> rchild);

        }

        //如果 R.key == F -> data.key 则返回

    }

ログイン後にコピー

削除

リーフノードを削除

子ノードが1つだけある内部ノードを削除する

子ノードが2つある内部ノードを削除する

単純な置換を行うと、次のようなことが起こる可能性があります次の状況:

したがって、サブツリー内で適切な置換ノードを選択する必要があります。置換ノードは通常、正しいサブツリー内の最小のノードになります:

BinarySearchTree Java バージョンコード参照 BinarySearchTree:

package wx.algorithm.search.bst;

/**
 * Created by apple on 16/7/29.
 */

/**
 * @function 二叉搜索树的示范代码
 */
public class BinarySearchTree {

    //指向二叉搜索树的根节点
    private Node root;

    //默认构造函数
    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * @param id 待查找的值
     * @return
     * @function 默认搜索函数
     */
    public boolean find(int id) {

        //从根节点开始查询
        Node current = root;

        //当节点不为空
        while (current != null) {

            //是否已经查询到
            if (current.data == id) {
                return true;
            } else if (current.data > id) {
                //查询左子树
                current = current.left;
            } else {
                //查询右子树
                current = current.right;
            }
        }
        return false;
    }

    /**
     * @param id
     * @function 插入某个节点
     */
    public void insert(int id) {

        //创建一个新的节点
        Node newNode = new Node(id);

        //判断根节点是否为空
        if (root == null) {
            root = newNode;
            return;
        }

        //设置current指针指向当前根节点
        Node current = root;

        //设置父节点为空
        Node parent = null;

        //遍历直到找到第一个插入点
        while (true) {

            //先将父节点设置为当前节点
            parent = current;

            //如果小于当前节点的值
            if (id < current.data) {

                //移向左节点
                current = current.left;

                //如果当前节点不为空,则继续向下一层搜索
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {

                //否则移向右节点
                current = current.right;

                //如果当前节点不为空,则继续向下一层搜索
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    /**
     * @param id
     * @return
     * @function 删除树中的某个元素
     */
    public boolean delete(int id) {

        Node parent = root;
        Node current = root;

        //记录被找到的节点是父节点的左子节点还是右子节点
        boolean isLeftChild = false;

        //循环直到找到目标节点的位置,否则报错
        while (current.data != id) {
            parent = current;
            if (current.data > id) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return false;
            }
        }

        //如果待删除的节点没有任何子节点
        //直接将该节点的原本指向该节点的指针设置为null
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }

        //如果待删除的节点有一个子节点,且其为左子节点
        else if (current.right == null) {

            //判断当前节点是否为根节点
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {

                //挂载到父节点的左子树
                parent.left = current.left;
            } else {

                //挂载到父节点的右子树
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }

        //如果待删除的节点有两个子节点
        else if (current.left != null && current.right != null) {

            //寻找右子树中的最小值
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    /**
     * @param deleleNode
     * @return
     * @function 在树种查找最合适的节点
     */
    private Node getSuccessor(Node deleleNode) {
        Node successsor = null;
        Node successsorParent = null;
        Node current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

    /**
     * @function 以中根顺序遍历树
     */
    public void display() {
        display(root);
    }

    private void display(Node node) {

        //判断当前节点是否为空
        if (node != null) {

            //首先展示左子树
            display(node.left);

            //然后展示当前根节点的值
            System.out.print(" " + node.data);

            //最后展示右子树的值
            display(node.right);
        }
    }

}

ログイン後にコピー

テスト関数:

package wx.algorithm.search.bst;

import org.junit.Before;
import org.junit.Test;

/**
 * Created by apple on 16/7/30.
 */
public class BinarySearchTreeTest {

    BinarySearchTree binarySearchTree;

    @Before
    public void setUp() {
        binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(3);
        binarySearchTree.insert(8);
        binarySearchTree.insert(1);
        binarySearchTree.insert(4);
        binarySearchTree.insert(6);
        binarySearchTree.insert(2);
        binarySearchTree.insert(10);
        binarySearchTree.insert(9);
        binarySearchTree.insert(20);
        binarySearchTree.insert(25);
        binarySearchTree.insert(15);
        binarySearchTree.insert(16);
        System.out.println("原始的树 : ");
        binarySearchTree.display();
        System.out.println("");

    }

    @Test
    public void testFind() {

        System.out.println("判断4是否存在树中 : " + binarySearchTree.find(4));

    }

    @Test
    public void testInsert() {

    }

    @Test
    public void testDelete() {

        System.out.println("删除值为2的节点 : " + binarySearchTree.delete(2));
        binarySearchTree.display();

        System.out.println("\n 删除有一个子节点值为4的节点 : " + binarySearchTree.delete(4));
        binarySearchTree.display();

        System.out.println("\n 删除有两个子节点的值为10的节点 : " + binarySearchTree.delete(10));
        binarySearchTree.display();

    }

}

ログイン後にコピー

以上が二分探索木アルゴリズムの Java 実装の詳細コード説明 (写真)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。