二叉搜索树

Node:

public Node search(Node root, int key)
{
// Base Cases: root is null or key is present at root
if (root==null || root.key==key)
    return root;
// Key is greater than root's key
if (root.key < key)
   return search(root.right, key);
// Key is smaller than root's key
return search(root.left, key);
}

struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
   return root;

// Key is greater than root's key
if (root->key < key)
   return search(root->right, key);
 
// Key is smaller than root's key
return search(root->left, key);
}

插入节点

class BinarySearchTree {
 
/* Class containing left
   and right child of current node
 * and key value*/
class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
     root = null;
}
// This method mainly calls insertRec()
void insert(int key)
{
     root = insertRec(root, key);
}
/* A recursive function to
   insert a new key in BST */
Node insertRec(Node root, int key)
{
 
    /* If the tree is empty,
       return a new node */
    if (root == null)
    {
        root = new Node(key);
        return root;
    }
 
    /* Otherwise, recur down the tree */
    if (key < root.key)
        root.left = insertRec(root.left, key);
    else if (key > root.key)
        root.right = insertRec(root.right, key);
 
    /* return the (unchanged) node pointer */
    return root;
}
 
// This method mainly calls InorderRec()
void inorder()
{
     inorderRec(root);
}
 
// A utility function to
// do inorder traversal of BST
void inorderRec(Node root)
{
    if (root != null) {
        inorderRec(root.left);
        System.out.println(root.key);
        inorderRec(root.right);
    }
}
// Driver Code
public static void main(String[] args)
{
    BinarySearchTree tree = new BinarySearchTree();
 
    /* Let us create following BST
          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80 */
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);
 
    // print inorder traversal of the BST
    tree.inorder();
    }
}

// C++ program to demonstrate insertion
// in a BST recursively.
#include <iostream>
using namespace std;
class BST
{
int data;
BST *left, *right;
 
public:
// Default constructor.
BST();
 
// Parameterized constructor.
BST(int);
 
// Insert function.
BST* Insert(BST*, int);
 
// Inorder traversal.
void Inorder(BST*);
};
 
// Default Constructor definition.
BST ::BST()
: data(0)
, left(NULL)
, right(NULL)
    {
}
 
// Parameterized Constructor definition.
BST ::BST(int value)
{
data = value;
left = right = NULL;
}
 
// Insert function definition.
BST* BST ::Insert(BST* root, int value)
{
    if (!root)
    {
        // Insert the first node, if root is NULL.
        return new BST(value);
    }
 
// Insert data.
if (value > root->data)
{
    // Insert right node data, if the 'value'
    // to be inserted is greater than 'root' node data.
 
    // Process right nodes.
    root->right = Insert(root->right, value);
}
else
{
    // Insert left node data, if the 'value'
    // to be inserted is greater than 'root' node data.
 
    // Process left nodes.
    root->left = Insert(root->left, value);
}
 
// Return 'root' node, after insertion.
return root;
}

// Inorder traversal function.
// This gives data in sorted order.
void BST ::Inorder(BST* root)
{
    if (!root) {
        return;
    }
    Inorder(root->left);
    cout << root->data << endl;
    Inorder(root->right);
}
 
// Driver code
int main()
{
    BST b, *root = NULL;
    root = b.Insert(root, 50);
    b.Insert(root, 30);
    b.Insert(root, 20);
    b.Insert(root, 40);
    b.Insert(root, 70);
    b.Insert(root, 60);
    b.Insert(root, 80);

    b.Inorder(root);
    return 0;
}