二叉搜索樹中的插入方法

當我將節點插入二叉樹并通過列印在主樹中對其進行測驗以確保輸出總是錯誤時錯誤的順序我檢查了顯示是否完美，但問題在于插入方法（插入方法插入非重復鍵）。

class BSTNode<T> {
    public int key;
    public T data;
    public BSTNode<T> left, right;

    
    public BSTNode(int k, T val) {
        key = k;
        data = val;
        left = right = null;
    }

    public BSTNode(int k, T val, BSTNode<T> l, BSTNode<T> r) {
        key = k;
        data = val;
        left = l;
        right = r;
    }
}

public class BST<T> {
    BSTNode<T> root, current;

    public BST() {
        root = current = null;
    }

    public boolean empty() {
        return root == null;
    }

    public boolean full() {
        return false;
    }

    public T retrieve() {
        return current.data;
    }

    public boolean findkey(int tkey) {
        BSTNode<T> p = root, q = root;

        if (empty())
            return false;
        int nb = 0;
        while (p != null) {
            q = p;
            nb  ;
            if (p.key == tkey) {
                current = p;
                return true;
            } else if (tkey < p.key)
                p = p.left;
            else
                p = p.right;
        }

        current = q;
        return false;
    }
    
    public boolean insert(int key, T val) {
        BSTNode<T> p = current, q = current;

        while (p != null) {
            q = p;
            if (p.key == key) {
                return false;
            } else if (key < p.key)
                p = p.left;
            else
                p = p.right;
        }

        p = new BSTNode<T>(key, val);
        if (empty()) {
            root = current = p;
            return true;
        } else {
            // current is pointing to parent of the new key
            if (key < current.key)
                current.left = p;
            else
                current.right = p;
            current = p;
            return true;
        }
    }

    public void display() {
        if (root == null)
            System.out.println("BST IS EMPTY");
        else
            displayin(root);
        System.out.println();
    }

    private void displayin(BSTNode<T> p) {
        if (p != null) {
            displayin(p.left);
            System.out.print(p.key   " "   p.data   " ,  ");
            displayin(p.right);
        }
    }
}

uj5u.com熱心網友回復：

在您的insert方法中，第一個代碼部分：

        while (p != null) {
            q = p;
            if (p.key == key) {
                current = p;
                return true;
            } else if (key < p.key)
                p = p.left;
            else
                p = p.right;
        }

true當找到您要寫入的密鑰時，只需回傳即可。然而，它根本不插入val這里。您可以通過在某些樹上呼叫 insert 方法然后列印該樹，將您預期的結果與實際結果進行比較來檢測到這一點。在自動化形式中，您可以使用 JUnit 測驗來做到這一點。

uj5u.com熱心網友回復：

我想我知道你想要（現在）。我已將“顯示”方法更改為 toString，重寫插入并為 toString實作了一種bfs形式。

import java.util.ArrayList;

class BSTNode<T> {

    public int key;
    public T data;
    public BSTNode<T> left, right;

    public BSTNode(int k, T val) {
        key = k;
        data = val;
        left = right = null;
    }

    public BSTNode(int k, T val, BSTNode<T> l, BSTNode<T> r) {
        key = k;
        data = val;
        left = l;
        right = r;
    }

    @Override
    public String toString() {
        return "["   key   ":"   data   "]";
    }
}

public class BST<T> {

    BSTNode<T> root, current;

    public BST() {
        root = current = null;
    }

    public boolean empty() {
        return root == null;
    }

    public T retrieve() {
        return current.data;
    }

    public boolean findkey(int tkey) {
        BSTNode<T> current = root;
        while (current != null) {
            if (current.key == tkey)
                return true;
            if (tkey < current.key)
                current = current.left;
            else
                current = current.right;
        }
        return false;
    }
    
    public boolean insert(int key, T val) {
        BSTNode<T> node = new BSTNode<>(key, val);
        if (root == null) {
            root = node;
        } else {
            BSTNode<T> current = root;
            while (current != null) {
                if (key == current.key)
                    return false;
                if (key < current.key) {
                    if (current.left == null) {
                        current.left = node;
                        return true;
                    }
                    current = current.left;
                } else {
                    if (current.right == null) {
                        current.right = node;
                        return true;
                    }
                    current = current.right;
                }
            }
        }
        return false;
    }

    public String toString() {
        if (root == null)
            return "BST IS EMPTY";
        ArrayList<BSTNode<T>> visited = new ArrayList<>();
        ArrayList<BSTNode<T>> queue = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            BSTNode<T> vertex = queue.remove(0);
            if (vertex != null) {
                queue.add(vertex.left);
                queue.add(vertex.right);
            }
            visited.add(vertex);
        }
        return visited.toString();
    }
}

標籤：爪哇 数据结构 插入 二叉搜索树

上一篇：將具有相同IP的在線玩家聚集到一個串列中

下一篇：如何執行Mono序列的串列