| |
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;
} |
|
|
|