이진 검색 트리(BST) - 삽입

2541 단어
BST에 노드를 삽입하려면 다음 4번 항목을 클릭하세요.
  • Các 노드 mới luôn được chèn vào 리프 노드.
  • Bắt đầu từ node root và gọi đệ quy cho đến khi pointer left, hoặc right == null.
  • Nếu value của node hiện tại nhỏ hơn value của node mới, thì chuyển sang node bên phải của node hiện tại, còn lại chuyển sang node bên trái.
  • Nếu 노드 hiện tại là null, hãy 삽입 노드 mới đó bằng cách gán 노드 hiện tại = 노드 mới

  • <script>
    
    // javascript program to demonstrate insert 
    // operation in binary search tree
    // BST node
    class Node
    {
        constructor()
        {
            this.key = 0;
            this.left = null;
            this.right = null;
        }
    };
    
    // Utility function to create a new node
    function newNode(data)
    {
        var temp = new Node();
        temp.key = data;
        temp.left = null;
        temp.right = null;
        return temp;
    }
    
    // A utility function to insert a new
    // Node with given key in BST
    function insert(root, key)
    {
    
        // Create a new Node containing
        // the new element
        var newnode = newNode(key);
    
        // Pointer to start traversing from root and
        // traverses downward path to search
        // where the new node to be inserted
        var x = root;
    
        // Pointer y maintains the trailing
        // pointer of x
        var y = null;
    
        while (x != null)
        {
            y = x;
            if (key < x.key)
                x = x.left;
            else
                x = x.right;
        }
    
        // If the root is null i.e the tree is empty
        // The new node is the root node
        if (y == null)
            y = newnode;
    
        // If the new key is less than the leaf node key
        // Assign the new node to be its left child
        else if (key < y.key)
            y.left = newnode;
    
        // else assign the new node its right child
        else
            y.right = newnode;
    
        // Returns the pointer where the
        // new node is inserted
        return y;
    }
    
    // A utility function to do inorder
    // traversal of BST
    function Inorder(root)
    {
        if (root == null)
            return;
        else
        {
            Inorder(root.left);
            document.write( root.key +" ");
            Inorder(root.right);
        }
    }
    
    // Driver code
    /* Let us create following BST
            50
        / \
        30 70
        / \ / \
    20 40 60 80 */
    var root = null;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    // Print inorder traversal of the BST
    Inorder(root);
    
    // This code is contributed by itsok.
    </script>
    


    산출20 30 40 50 60 70 80

    좋은 웹페이지 즐겨찾기