عملیات در درخت جستجوی دودویی: جستجو و درج — به زبان ساده

1// C function to search a given key in a given BST 
2struct node* search(struct node* root, int key) 
3{ 
4    // Base Cases: root is null or key is present at root 
5    if (root == NULL || root->key == key) 
6       return root; 
7     
8    // Key is greater than root's key 
9    if (root->key < key) 
10       return search(root->right, key); 
11  
12    // Key is smaller than root's key 
13    return search(root->left, key); 
14}

1# A utility function to search a given key in BST 
2def search(root,key): 
3      
4    # Base Cases: root is null or key is present at root 
5    if root is None or root.val == key: 
6        return root 
7  
8    # Key is greater than root's key 
9    if root.val < key: 
10        return search(root.right,key) 
11    
12    # Key is smaller than root's key 
13    return search(root.left,key) 
14  
15# This code is contributed by Bhavya Jain

1// A utility function to search a given key in BST 
2public Node search(Node root, int key) 
3{ 
4    // Base Cases: root is null or key is present at root 
5    if (root==null || root.key==key) 
6        return root; 
7  
8    // val is greater than root's key 
9    if (root.key > key) 
10        return search(root.left, key); 
11  
12    // val is less than root's key 
13    return search(root.right, key); 
14}

1// C program to demonstrate insert operation in binary search tree 
2#include<stdio.h> 
3#include<stdlib.h> 
4   
5struct node 
6{ 
7    int key; 
8    struct node *left, *right; 
9}; 
10   
11// A utility function to create a new BST node 
12struct node *newNode(int item) 
13{ 
14    struct node *temp =  (struct node *)malloc(sizeof(struct node)); 
15    temp->key = item; 
16    temp->left = temp->right = NULL; 
17    return temp; 
18} 
19   
20// A utility function to do inorder traversal of BST 
21void inorder(struct node *root) 
22{ 
23    if (root != NULL) 
24    { 
25        inorder(root->left); 
26        printf("%d \n", root->key); 
27        inorder(root->right); 
28    } 
29} 
30   
31/* A utility function to insert a new node with given key in BST */
32struct node* insert(struct node* node, int key) 
33{ 
34    /* If the tree is empty, return a new node */
35    if (node == NULL) return newNode(key); 
36  
37    /* Otherwise, recur down the tree */
38    if (key < node->key) 
39        node->left  = insert(node->left, key); 
40    else if (key > node->key) 
41        node->right = insert(node->right, key);    
42  
43    /* return the (unchanged) node pointer */
44    return node; 
45} 
46   
47// Driver Program to test above functions 
48int main() 
49{ 
50    /* Let us create following BST 
51              50 
52           /     \ 
53          30      70 
54         /  \    /  \ 
55       20   40  60   80 */
56    struct node *root = NULL; 
57    root = insert(root, 50); 
58    insert(root, 30); 
59    insert(root, 20); 
60    insert(root, 40); 
61    insert(root, 70); 
62    insert(root, 60); 
63    insert(root, 80); 
64   
65    // print inoder traversal of the BST 
66    inorder(root); 
67   
68    return 0; 
69}

1# Python program to demonstrate insert operation in binary search tree  
2  
3# A utility class that represents an individual node in a BST 
4class Node: 
5    def __init__(self,key): 
6        self.left = None
7        self.right = None
8        self.val = key 
9  
10# A utility function to insert a new node with the given key 
11def insert(root,node): 
12    if root is None: 
13        root = node 
14    else: 
15        if root.val < node.val: 
16            if root.right is None: 
17                root.right = node 
18            else: 
19                insert(root.right, node) 
20        else: 
21            if root.left is None: 
22                root.left = node 
23            else: 
24                insert(root.left, node) 
25  
26# A utility function to do inorder tree traversal 
27def inorder(root): 
28    if root: 
29        inorder(root.left) 
30        print(root.val) 
31        inorder(root.right) 
32  
33  
34# Driver program to test the above functions 
35# Let us create the following BST 
36#      50 
37#    /      \ 
38#   30     70 
39#   / \    / \ 
40#  20 40  60 80 
41r = Node(50) 
42insert(r,Node(30)) 
43insert(r,Node(20)) 
44insert(r,Node(40)) 
45insert(r,Node(70)) 
46insert(r,Node(60)) 
47insert(r,Node(80)) 
48  
49# Print inoder traversal of the BST 
50inorder(r) 
51  
52# This code is contributed by Bhavya Jain

1// Java program to demonstrate insert operation in binary search tree 
2class BinarySearchTree { 
3  
4    /* Class containing left and right child of current node and key value*/
5    class Node { 
6        int key; 
7        Node left, right; 
8  
9        public Node(int item) { 
10            key = item; 
11            left = right = null; 
12        } 
13    } 
14  
15    // Root of BST 
16    Node root; 
17  
18    // Constructor 
19    BinarySearchTree() {  
20        root = null;  
21    } 
22  
23    // This method mainly calls insertRec() 
24    void insert(int key) { 
25       root = insertRec(root, key); 
26    } 
27      
28    /* A recursive function to insert a new key in BST */
29    Node insertRec(Node root, int key) { 
30  
31        /* If the tree is empty, return a new node */
32        if (root == null) { 
33            root = new Node(key); 
34            return root; 
35        } 
36  
37        /* Otherwise, recur down the tree */
38        if (key < root.key) 
39            root.left = insertRec(root.left, key); 
40        else if (key > root.key) 
41            root.right = insertRec(root.right, key); 
42  
43        /* return the (unchanged) node pointer */
44        return root; 
45    } 
46  
47    // This method mainly calls InorderRec() 
48    void inorder()  { 
49       inorderRec(root); 
50    } 
51  
52    // A utility function to do inorder traversal of BST 
53    void inorderRec(Node root) { 
54        if (root != null) { 
55            inorderRec(root.left); 
56            System.out.println(root.key); 
57            inorderRec(root.right); 
58        } 
59    } 
60  
61    // Driver Program to test above functions 
62    public static void main(String[] args) { 
63        BinarySearchTree tree = new BinarySearchTree(); 
64  
65        /* Let us create following BST 
66              50 
67           /     \ 
68          30      70 
69         /  \    /  \ 
70       20   40  60   80 */
71        tree.insert(50); 
72        tree.insert(30); 
73        tree.insert(20); 
74        tree.insert(40); 
75        tree.insert(70); 
76        tree.insert(60); 
77        tree.insert(80); 
78  
79        // print inorder traversal of the BST 
80        tree.inorder(); 
81    } 
82} 
83// This code is contributed by Ankur Narain Verma