Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation chain store binary search tree (recursive method)     - Share and show your code on GitHub (Linux)

- Linux OOM killer mechanism (Linux)

- ImageMagick Tutorial: How to cut images in Linux command line (Linux)

- Comparison of C # and Java (Programming)

- 20 Linux commands interview questions and answers (Linux)

- MongoDB upgrade from 2.4.9 to 2.6.0 and PHP record of mongo extension upgrade from 1.4.5 to 1.5.1 (Database)

- AngularJS notes --- Scope and controller (Programming)

- IOwait Linux system monitoring diagnostic tools (Linux)

- Awk include binding capacity larger than the specified size of all files directory (Linux)

- Linux file and directory permissions settings (Linux)

- What is a logical partition management LVM, how to use in Ubuntu (Linux)

- Installation and configuration of phpMyAdmin under CentOS (Database)

- Firewall Configuration Red Hat Enterprise Linux 4 (Linux)

- Nginx Performance Tuning Guidelines (Server)

- OpenResty load balancing MySQL (Database)

- Android Delete project useless resource file (Programming)

- Talk about the Linux folder permissions issue again (Linux)

- Wireless LAN security solutions (Linux)

- I use the desktop environment in GNU / Linux combination tool (Linux)

- Manually generate AWR reports (Database)

 
         
  Java implementation chain store binary search tree (recursive method)
     
  Add Date : 2017-08-31      
         
       
         
  The definition of a binary search tree:

Binary search tree or an empty tree, or a non-empty binary tree with the following characteristics:

1. If the left subtree is not empty, the left subtree of any node key values are less than the root keywords;

2. If the right subtree is not empty, all the nodes in the right subtree are greater than the value of the root keywords keywords;

3. Left and right subtrees themselves are a binary search tree.

Implement a binary search tree, the features are:

1. Use an array to build a binary search tree

2. binary search tree hierarchy traversal and preorder

3. Insert node

4. Find the node

5. Find the maximum and minimum values of a binary tree

6. get the direct parent node

7. get immediate predecessor and immediate successor of node

8. Remove the node

import java.lang.Integer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/ *
 * Binary sort tree (binary search tree) implementation
 * /
public class BinarySearchTree {
    private TreeNode < Integer> root; // root node
    
    public BinarySearchTree () {
        root = null;
    }
    
    // Use an array to build a binary search tree
    public TreeNode < Integer> buildBST (Integer [] array) {
        if (array.length == 0) {
            return null;
        } Else {
            root = null; // initialize the tree is empty tree
            for (int i = 0; i < array.length; i ++) {// insert each element in turn
                root = insertNode (root, array [i]);
            }
            return root;
        }
    }
    
    // Insert a data field in a binary search tree for node data, the new node must be inserted into a leaf node
    public TreeNode < Integer> insertNode (TreeNode < Integer> node, Integer data) {
        if (node == null) {// original tree is empty, a new record is inserted into the root
            node = new TreeNode < Integer> (data, null, null);
        } Else {
            if (node.getData () == data) {// the presence of the tree nodes the same keywords, do nothing
                
            } Else {
                if (node.getData ()> data) {// root node> insert data into the left subtree
                    node.setLchild (insertNode (node.getLchild (), data));
                } Else {// root node < insert data inserted into the right subtree
                    node.setRchild (insertNode (node.getRchild (), data));
                }
            }
        }
        return node;
    }
    
    // Binary search tree traversal, you can get a number of columns in ascending order
    public void inOrder (TreeNode < Integer> node) {
        if (node! = null) {
            inOrder (node.getLchild ());
            System.out.print (node.getData () + "");
            inOrder (node.getRchild ());
        }
    }
    // Binary search tree hierarchy traversal
    public void levelOrder (TreeNode < Integer> root) {
        Queue < TreeNode < Integer >> nodeQueue = new LinkedList < TreeNode < Integer >> ();
        TreeNode < Integer> node = null;
        nodeQueue.add (root); // root node into the team
        while (! nodeQueue.isEmpty ()) {// queue is not empty cycle
            node = nodeQueue.peek ();
            System.out.print (node.getData () + "");
            nodeQueue.poll (); // team head element from the team
            if (node.getLchild ()! = null) {// the left sub-tree is not empty, then the left subtree into the queue
                nodeQueue.add (node.getLchild ());
            }
            if (node.getRchild ()! = null) {// right subtree is not empty, then the right subtree into the queue
                nodeQueue.add (node.getRchild ());
            }
        }
    }
    
    // Find the data field is the junction point data, if not exists, returns null
    public TreeNode < Integer> searchNode (TreeNode < Integer> node, Integer data) {
        while (node! = null && node.getData ()! = data) {
            if (node.getData ()> data) {
                node = node.getLchild (); // root node> Data, left
            } Else {
                node = node.getRchild (); // root node < data right away
            }
        }
        return node;
    }
    
    // Find the maximum: constantly looking for the right child
    public TreeNode < Integer> getMaxData (TreeNode < Integer> node) {
        if (node.getRchild () == null) {
            return node;
        } Else {
            return getMaxData (node.getRchild ());
        }
    }
    
    // Find the minimum: keep looking left child
    public TreeNode < Integer> getMinData (TreeNode < Integer> node) {
        if (node.getLchild () == null) {
            return node;
        } Else {
            return getMinData (node.getLchild ());
        }
    }
    
    // Get the data domain node data of the immediate parent node parentNode
    public TreeNode < Integer> getParentNode (TreeNode < Integer> root, Integer data) {
        TreeNode < Integer> parentNode = root;
        if (parentNode.getData () == data) {// root parent node returns null
            return null;
        }
        while (parentNode! = null) {
            // Find the parent of the current node's left and right child nodes, if equal, the parent returns
            if ((parentNode.getLchild ()! = null && parentNode.getLchild (). getData () == data) ||
                    (ParentNode.getRchild ()! = Null && parentNode.getRchild (). GetData () == data)) {
                return parentNode;
            } Else {
                if (parentNode.getData ()> data) {// Find the parent left
                    parentNode = parentNode.getLchild ();
                } Else {
                    parentNode = parentNode.getRchild (); // Find the right parent node
                }
            }
        }
        return null;
    }
    
    / **
    * Obtained directly before junction node chemotaxis
    . * A node of the left subtree is not empty: its predecessor node to its left subtree largest element
    * B The node the left subtree is empty: its predecessor node to its ancestor node (recursively), and the right child node is also the ancestor of its ancestor node
    * (That has to find its parent, ancestor node that appears after the left)
    * /
    public TreeNode < Integer> getPrecessor (TreeNode < Integer> root, TreeNode < Integer> node) {
        if (node == null) {
            return null;
        }
        . // A node of the left subtree is not empty: its predecessor node to its left subtree largest element
        if (node.getLchild ()! = null) {
            return getMaxData (node.getLchild ());
        } Else {// b left subtree of the node is empty: its predecessor node to its ancestor node (recursively)
            TreeNode < Integer> parentNode = getParentNode (root, node.getData ());
            while (parentNode! = null && node == parentNode.getLchild ()) {
                node = parentNode;
                parentNode = getParentNode (root, parentNode.getData ());
            }
            return parentNode;
        }
    }
    
    / **
    * Get immediate successor node node (successor node is the node to be removed than the critical value of the larger node-set minimum value)
    * A. The right child node tree is not empty, its successor node to its right subtree smallest element
    * B. The right child node is empty then its successor node to its ancestor node (recursively), and the left child node of this ancestor is the ancestor of that node,
  * That has been up to find their ancestral node, the ancestor node until the turn right after:
    * /
    public TreeNode < Integer> getSuccessor (TreeNode < Integer> root, TreeNode < Integer> node) {
        if (node == null) {
            return null;
        }
        // A. The nodes in the right subtree is not empty, its successor node to its right subtree smallest element
        if (node.getRchild ()! = null) {
            return getMinData (node.getRchild ());
        } Else {// b. The node right subtree is empty, its successor node to its highest ancestor node (recursively)
            TreeNode < Integer> parentNode = getParentNode (root, node.getData ());
            while (parentNode! = null && node == parentNode.getRchild ()) {
                node = parentNode;
                parentNode = getParentNode (root, parentNode.getData ());
            }
            return parentNode;
        }
    }
    
    / **
    * Delete data field to the node data
    * In one of three circumstances:
    * A. If the deleted node z is a leaf node, delete, does not destroy the nature of a binary search tree
    * B. If only one node z left subtree or right subtree, then let z become subtree subtree z parent node, instead of the z position
    * C. If the node z with left and right two sub-tree, then let the direct successor (or predecessor) z z alternative,
    * Then deleting the immediate successor (or predecessor) from a binary search tree, which is converted to the first or second case
    * @param Node binary search tree root node
    * @param Data to be deleted node data field
    * @return
    * /
    public boolean deleteNode (TreeNode < Integer> node, Integer data) {
        if (node == null) {// tree is empty
            throw new RuntimeException ( "tree is empty!");
        }
        TreeNode < Integer> delNode = searchNode (node, data); // search node to be deleted
        TreeNode < Integer> parent = null;
        if (delNode == null) {// If the tree does not exist to be deleted keywords
            throw new RuntimeException ( "tree does not exist in your keywords to delete!");
        } Else {
            parent = getParentNode (node, data); // get the direct parent node is deleted
            // A. If the deleted node z is a leaf node, delete, does not destroy the nature of a binary search tree
            if (delNode.getLchild () == null && delNode.getRchild () == null) {
                if (delNode == parent.getLchild ()) {// is deleted node left child of its parent node
                    parent.setLchild (null);
                } Else {// delete the node is a right child of its parent
                    parent.setRchild (null);
                }
                return true;
            }
            // B1. If only one node z left subtree, then let z become subtree subtree z parent node, instead of the position z
            if (delNode.getLchild ()! = null && delNode.getRchild () == null) {
                if (delNode == parent.getLchild ()) {// is deleted node left child of its parent node
                    parent.setLchild (delNode.getLchild ());
                } Else {// delete the node is a right child of its parent
                    parent.setRchild (delNode.getLchild ());
                }
                delNode.setLchild (null); // setting is deleted nodes left child is null
                return true;
            }
            // B2. If the node z only a right subtree, then let z become subtree subtree z parent node, instead of the position z
            if (delNode.getLchild () == null && delNode.getRchild ()! = null) {
                if (delNode == parent.getLchild ()) {// is deleted node left child of its parent node
                    parent.setLchild (delNode.getRchild ());
                } Else {// delete the node is a right child of its parent
                    parent.setRchild (delNode.getRchild ());
                }
                delNode.setRchild (null); // set the nodes are deleted right child is null
                return true;
            }
            // C. If the node z with left and right two subtrees, delete successor node of the node, the node and replace with the successor node
            if (delNode.getLchild ()! = null && delNode.getRchild ()! = null) {
                TreeNode < Integer> successorNode = getSuccessor (node, delNode); // get the node is removed successor node
                deleteNode (node, successorNode.getData ()); // delete successor node of the node
                delNode.setData (successorNode.getData ()); // replace with the successor node of the node
                return true;
            }
        }
        return false;
    }
    
    
    public static void main (String args []) {
        Scanner input = new Scanner (System.in);
        Integer [] array = {8,3,10,1,6,14,4,7,13};
        BinarySearchTree bst = new BinarySearchTree ();
        TreeNode < Integer> root = bst.buildBST (array);
        System.out.print ( "traverse the level:");
        bst.levelOrder (root);
        System.out.print ( "\ n" + "preorder:");
        bst.inOrder (root);
        System.out.println ();
        System.out.print ( "get Max:");
        System.out.println (bst.getMaxData (root) .getData ());
        System.out.print ( "get Min:");
        System.out.println (bst.getMinData (root) .getData ());
        System.out.print ( "binary search tree to insert a node, enter the node to be inserted in the data field:");
        int data = input.nextInt ();
        System.out.print ( "insert node" + data + "after traversal results:");
        root = bst.insertNode (root, data);
        bst.inOrder (root);
        System.out.println ( "\ n" + "Find in a binary search tree of elements," + "Please input node values you want to find:");
        data = input.nextInt ();
        if (bst.searchNode (root, data) == null) {
            System.out.println ( "false");
        } Else {
            System.out.println ( "true");
        }
        System.out.println ( "Finding the immediate parent node of" + "Please enter the desired node values to find:");
        data = input.nextInt ();
        System.out.print ( "node" + data + "parent node is:");
        if (bst.getParentNode (root, data) == null) {
            System.out.println ( "null");
        } Else {
            System.out.println (bst.getParentNode (root, data) .getData ());
        }
        System.out.println ( "delete node" + "Please enter the need to remove the node values:");
        data = input.nextInt ();
        if (bst.deleteNode (root, data)) {
            System.out.print ( "Delete hierarchy node after traversing:");
            bst.levelOrder (root);
            System.out.print ( "\ n" + "delete node after preorder:");
            bst.inOrder (root);
        }
    }
}

Hierarchy traversal: 831016144713
Preorder: 134678101314
Get Max: 14
Get the minimum: 1
Find a binary tree to insert a node, enter the node you want to insert data fields: 15
After insertion node 15, the results of traversal: 13467810131415
Find elements in a binary search tree, enter the value you want to find nodes:
true
Find the direct parent node, input node values need to find:
Node is the parent node 10: 8
Delete nodes, enter the value you want to delete the node:
Remove traverse the hierarchy node after: 8310161471315
Preorder delete nodes after: 1367810131415

Some non-recursive implementation of the method:

1. Insert node insertNode ():

// Insert a data field in a binary search tree for node data, the new node must be inserted into a leaf node
    public TreeNode < Integer> insertNode (TreeNode < Integer> node, Integer data) {
        TreeNode < Integer> newNode = new TreeNode < Integer> (data, null, null);
        TreeNode < Integer> tmpNode = node; // node traversal
        TreeNode < Integer> pnode = null; // record the current node's parent
        
        if (node == null) {// original tree is empty, a new record is inserted into the root
            node = newNode;
            return node;
        }
        while (tmpNode! = null) {
            pnode = tmpNode;
            if (tmpNode.getData () == data) {// the presence of the tree nodes the same keywords, do nothing
                return node;
            } Else {
                if (tmpNode.getData ()> data) {// root node> insert data into the left subtree
                    tmpNode = tmpNode.getLchild ();
                } Else {// root node < insert data inserted into the right subtree
                    tmpNode = tmpNode.getRchild ();
                }
            }
        }
        if (pnode.getData ()> data) {
            pnode.setLchild (newNode);
        } Else {
            pnode.setRchild (newNode);
        }
        return node;
    }

2. binary search tree preorder:

// Binary search tree traversal LNR, you can get a number of columns in ascending order
    public void inOrder (TreeNode < Integer> node) {
        Stack < TreeNode < Integer >> nodeStack = new Stack < TreeNode < Integer >> ();
        TreeNode < Integer> tempNode = node; // pointer traversal
        while (tempNode! = null ||! nodeStack.isEmpty ()) {
            if (tempNode! = null) {
                nodeStack.push (tempNode);
                tempNode = tempNode.getLchild ();
            } Else {
                tempNode = nodeStack.pop ();
                System.out.print (tempNode.getData () + "");
                tempNode = tempNode.getRchild ();
            }
        }
    }

3. To obtain a binary search tree of maximum and minimum values:

// Find the maximum: constantly looking for the right child
    public TreeNode < Integer> getMaxData (TreeNode < Integer> node) {
        TreeNode < Integer> tempNode = node;
        while (tempNode.getRchild ()! = null) {
            tempNode = tempNode.getRchild ();
        }
        return tempNode;
    }
    
    // Find the minimum: keep looking left child
    public TreeNode < Integer> getMinData (TreeNode < Integer> node) {
        TreeNode < Integer> tempNode = node;
        while (tempNode.getLchild ()! = null) {
            tempNode = tempNode.getLchild ();
        }
        return tempNode;
    }
     
         
       
         
  More:      
 
- Python Django model within the class meta Detailed (Programming)
- Oracle set and remove columns unavailable (Database)
- namespace mechanism Linux kernel analysis (Linux)
- Linux dynamic libraries and Guide (Programming)
- Java implementation chain store binary tree (Programming)
- Install Ubuntu text editor KKEdit 0.2.10 (Linux)
- Into the Java keyword instanceof (Programming)
- Android judgment toward camera pictures (Programming)
- Linux firewall settings instance (Linux)
- Shell Scripting Basics (Linux)
- The SVN installation, configuration and start - up under Linux (CentOS 6.5) (Server)
- Type Linux commands (Linux)
- Installation and configuration of phpMyAdmin under CentOS (Database)
- Automatic Clear date directory shell script (Linux)
- Kubernetes cluster deployment (Server)
- Python console achieve progress bar (Programming)
- Use Git in Eclipse (Linux)
- Linux user login and IP restrictions (Linux)
- Docker Private Registry Installation Guide at CentOS6.X (Linux)
- Ubuntu Install OpenSSL (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.