二叉搜索树

更新于 2025/10/16 16:21:06

二叉树表示
基本操作
定义节点
搜索操作
插入操作
中序遍历
前序遍历
后序遍历

A二叉搜索树 (BST) 是一种所有节点都遵循以下属性 −

节点的左子树的键小于或等于其父节点的键。
节点的右子树的键大于或等于其父节点的键。

因此，BST 将其所有子树分为两部分：左子树和右子树，可以定义为 −

left_subtree (keys) ≤ 节点 (key) ≤ right_subtree (keys)

二叉树表示

BST 是以保持 BST 属性的方式排列的节点集合。每个节点都有一个键和一个关联的值。搜索时，会将所需的键与二叉搜索树 (BST) 中的键进行比较，如果找到，则检索关联的值。

以下是二叉搜索树 (BST) 的图示 −

我们观察到，根节点键 (27) 的所有较低值键都在左子树上，而较高值键都在右子树上。

基本操作

以下是二叉搜索树 (BST) 的基本操作 −

搜索 − 在树中搜索元素。
插入 −在树中插入一个元素。
前序遍历 − 以前序方式遍历树。
中序遍历 − 以中序方式遍历树。
后序遍历 − 以后序方式遍历树。

定义节点

定义一个节点，用于存储一些数据以及对其左右子节点的引用。

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

搜索操作

每当要搜索元素时，都从根节点开始搜索。然后，如果数据小于键值，则在左子树中搜索元素。否则，在右子树中搜索元素。每个节点都遵循相同的算法。

算法

1. 开始
2. 检查树是否为空
3. 如果树为空，则无法搜索
4. 否则，首先搜索树的根节点。
5. 如果键与根节点中的值不匹配，
则搜索其子树。
6. 如果键的值小于根节点的值，
则搜索左子树
7. 如果键的值大于根节点的值，
则搜索右子树。
8. 如果在树中未找到键，则返回搜索失败。
9. 结束

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct node {
   int data;
   struct node *leftChild, *rightChild;
};
struct node *root = NULL;
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
}
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   
   //如果树为空
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //去树的左边
         if(data < parent->data) {
            current = current->leftChild;
            
            //插入到左侧
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//去树的右边
         else {
            current = current->rightChild;
            
            //插入到右侧
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   while(current->data != data) {
         //去左边的树
         if(current->data > data) {
            current = current->leftChild;
         }//否则转到右边的树
         else {
            current = current->rightChild;
         }
         
         //not found
         if(current == NULL) {
            return NULL;
         }
      }
   return current;
}
void printTree(struct node* Node){
   if(Node == NULL)
      return;
   printTree(Node->leftChild);
   printf(" --%d", Node->data);
   printTree(Node->rightChild);
}
int main(){
   insert(55);
   insert(20);
   insert(90);
   insert(50);
   insert(35);
   insert(15);
   insert(65);
   printf("Insertion done");
   printf("
BST: 
");
   printTree(root);
   struct node* k;
   int ele = 35;
   printf("
Element to be searched: %d", ele);
   k = search(35);
   if(k != NULL)
      printf("
Element %d found", k->data);
   else
      printf("
Element not found");
   return 0;
}

输出

Insertion done
BST: 
 --15 --20 --35 --50 --55 --65 --90
Element to be searched: 35
Element 35 found

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
Node *root = NULL;
Node *newNode(int item){
   Node *temp = (Node *)malloc(sizeof(Node));
   temp->data = item;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
}
void insert(int data){
   Node *tempNode = (Node*) malloc(sizeof(Node));
   Node *current;
   Node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   
   //如果树为空
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //去树的左边
         if(data < parent->data) {
            current = current->leftChild;
            
            //插入到左侧
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//去树的右边
         else {
            current = current->rightChild;
            
            //插入到右侧
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
Node* search(int data){
   Node *current = root;
   while(current->data != data) {
         //去左边的树
         if(current->data > data) {
            current = current->leftChild;
         }//否则转到右边的树
         else {
            current = current->rightChild;
         }
         
         //not found
         if(current == NULL) {
            return NULL;
         }
   }
   return current;
}
void printTree(Node* Node) {
    if (Node == nullptr)
        return;
    printTree(Node->leftChild);
    cout << " --" << Node->data;
    printTree(Node->rightChild);
}
int main(){
   insert(55);
   insert(20);
   insert(90);
   insert(50);
   insert(35);
   insert(15);
   insert(65);
   cout<<"Insertion done";
   cout<<"
BST: "<<endl;
   printTree(root);
   struct node* k;
   int ele = 35;
   cout<<"
Element to be searched: "<<ele;
   Node* result = search(35);
   if(k != NULL)
      cout<<"
Element "<<result->data<<" found ";
   else
      cout<<"
Element not found";
   return 0;
}

输出

Insertion done
BST: 
 --15 --20 --35 --50 --55 --65 --90
Element to be searched: 35
Element 35 found

import java.util.Scanner;
class BSTNode {
   BSTNode left, right;
   int data;
   public BSTNode(int n) {
      left = null;
      right = null;
      data = n;
   }
}
public class BST {
   static BSTNode root;
   public BST() {
      root = null;
   }
   private BSTNode insert(BSTNode node, int data) {
      if(node == null)
         node = new BSTNode(data);
      else {
         if(data <= node.data)
            node.left = insert(node.left, data);
         else
            node.right = insert(node.right, data);
      }
      return node;
   }
   private boolean search(BSTNode r, int val) {
      boolean found = false;
      while ((r != null) && !found) {
         int rval = r.data;
         if(val < rval)
            r = r.left;
         else if (val > rval)
            r = r.right;
         else {
            found = true;
            break;
         }
         found = search(r, val);
      }
      return found;
   }
   void printTree(BSTNode node, String prefix) {
      if(node == null)
         return;
      printTree(node.left , " " + prefix);
      System.out.print(prefix + "--" + node.data + " ");
      printTree(node.right , prefix);
   }
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      BST bst = new BST();
      root = bst.insert(root, 55);
      root = bst.insert(root, 20);
      root = bst.insert(root, 90);
      root = bst.insert(root, 80);
      root = bst.insert(root, 50);
      root = bst.insert(root, 35);
      root = bst.insert(root, 15);
      root = bst.insert(root, 65);
      System.out.print("Insertion Done");
	  System.out.print("
BST:
");
      bst.printTree(root, "");
      int ele = 80;
      System.out.print("
Element to be searched: " + ele);
      System.out.println("
Element found: " + bst.search(root, 80));
   }
}

输出

Insertion Done
BST:  
--15  --20   --35  --50 --55   --65  --80 --90 
Element to be searched: 80
Element found: true

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

# 插入方法创建节点
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
         else:
            self.data = data
# 搜索方法将值与节点进行比较
   def search(self, key):
      if key < self.data:
         if self.left is None:
            return str(key)+" Not Found"
         return self.left.search(key)
      elif key > self.data:
         if self.right is None:
            return str(key)+" Not Found"
         return self.right.search(key)
      else:
         print(str(self.data) + ' is found')

root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print(root.search(17))
print(root.search(12))

输出

17 Not Found
12 is found
None

插入操作

每当要插入元素时，首先找到其正确的位置。从根节点开始搜索，如果数据小于键值，则在左子树中搜索空位置并插入数据。否则，在右子树中搜索空位置并插入数据。

算法

1. 开始
2. 如果树为空，则插入第一个元素作为树的根节点。
树的后续元素将作为叶子节点添加。
3. 如果元素小于根值，则将其作为叶子节点添加到左子树。
4. 如果元素大于根值，则将其作为叶子节点添加到右子树。
5. 树的最后一个叶子节点指向 NULL 值作为其子节点。
6. 结束

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct node {
   int data;
   struct node *leftChild, *rightChild;
};
struct node *root = NULL;
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
}
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   
   //如果树为空
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //去树的左边
         if(data < parent->data) {
            current = current->leftChild;
            
            //插入到左侧
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//去树的右边
         else {
            current = current->rightChild;
            
            //插入到右侧
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
void printTree(struct node* Node){
   if(Node == NULL)
      return;
   printTree(Node->leftChild);
   printf(" --%d", Node->data);
   printTree(Node->rightChild);
}
int main(){
   insert(55);
   insert(20);
   insert(90);
   insert(50);
   insert(35);
   insert(15);
   insert(65);
   printf("Insertion done
");
   printf("BST: 
");
   printTree(root);
   return 0;
}

输出

Insertion done
BST: 
 --15 --20 --35 --50 --55 --65 --90

#include <iostream>
using namespace std;
struct node {
   int data;
   struct node *leftChild, *rightChild;
};
struct node *root = NULL;
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
}
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   
   //如果树为空
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //去树的左边
         if(data < parent->data) {
            current = current->leftChild;
            
            //插入到左侧
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//去树的右边
         else {
            current = current->rightChild;
            
            //插入到右侧
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
void printTree(struct node* Node){
   if(Node == NULL)
      return;
   printTree(Node->leftChild);
   cout<<" --"<<Node->data;
   printTree(Node->rightChild);
}
int main(){
   insert(55);
   insert(20);
   insert(90);
   insert(50);
   insert(35);
   insert(15);
   insert(65);
   cout<<"Insertion done
";
   cout<<"BST:"<<endl;
   printTree(root);
   return 0;
}

输出

Insertion done
BST:
 --15 --20 --35 --50 --55 --65 --90

import java.util.Scanner;
class BSTNode {
   BSTNode left, right;
   int data;
   public BSTNode(int n) {
      left = null;
      right = null;
      data = n;
   }
}
public class BST {
   static BSTNode root;
   public BST() {
      root = null;
   }
   private BSTNode insert(BSTNode node, int data) {
      if(node == null)
         node = new BSTNode(data);
      else {
         if(data <= node.data)
            node.left = insert(node.left, data);
         else
            node.right = insert(node.right, data);
      }
      return node;
   }
   void printTree(BSTNode node, String prefix) {
      if(node == null)
         return;
      printTree(node.left , " " + prefix);
      System.out.print(prefix + "--" + node.data);
      printTree(node.right , prefix + " ");
   }
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      BST bst = new BST();
      root = bst.insert(root, 55);
      root = bst.insert(root, 20);
      root = bst.insert(root, 90);
      root = bst.insert(root, 80);
      root = bst.insert(root, 50);
      root = bst.insert(root, 35);
      root = bst.insert(root, 15);
      root = bst.insert(root, 65);
      System.out.print("Insertion done
");
      System.out.print("BST:
");
      bst.printTree(root, " ");
   }
}

输出

Insertion done
BST:
   --15  --20    --35   --50 --55    --65   --80  --90

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

# 插入方法创建节点
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
         else:
            self.data = data
   def printTree(self, prefex):
       if self is None:
           return
       self.left.printTree(prefex + "") if self.left else None
       print(prefex + "--", str(self.data),"", end = "")
       self.right.printTree(prefex + "") if self.right else None
root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Insertion Done")
print("BST: ")
root.printTree('')

输出

Insertion Done
BST: 
-- 5 -- 12 -- 23 -- 34 -- 46 -- 54

中序遍历

二叉搜索树中的中序遍历操作按以下顺序访问其所有节点 −

首先，遍历根节点/当前节点的左子树（如果有）。
接下来，遍历当前节点。
最后，遍历当前节点的右子树（如果有）。

算法

1. 开始
2. 递归遍历左子树
3. 然后，遍历根节点
4. 递归遍历右子树。
5. 结束

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct node {
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

// 中序遍历
void inorder(struct node *root){
   if (root != NULL) {
      inorder(root->left);
      printf("%d -> ", root->key);
      inorder(root->right);
   }
}

// 插入操作
struct node *insert(struct node *node, int key){
   if (node == NULL) return newNode(key);
   if (key < node->key)
      node->left = insert(node->left, key);
   else
      node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 55);
   root = insert(root, 20);
   root = insert(root, 90);
   root = insert(root, 50);
   root = insert(root, 35);
   root = insert(root, 15);
   root = insert(root, 65);
   printf("Inorder traversal: ");
   inorder(root);
}

输出

Inorder traversal: 15 -> 20 -> 35 -> 50 -> 55 -> 65 -> 90 ->

#include <iostream>
struct node {
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

// 中序遍历
void inorder(struct node *root){
   if (root != NULL) {
     inorder(root->left);
     printf("%d -> ", root->key);
     inorder(root->right);
   }
}

// 插入操作
struct node *insert(struct node *node, int key){
   if (node == NULL) return newNode(key);
   if (key < node->key)
     node->left = insert(node->left, key);
   else
     node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 55);
   root = insert(root, 20);
   root = insert(root, 90);
   root = insert(root, 50);
   root = insert(root, 35);
   root = insert(root, 15);
   root = insert(root, 65);
   printf("Inorder traversal: ");
   inorder(root);
}

输出

Inorder traversal: 15 -> 20 -> 35 -> 50 -> 55 -> 65 -> 90 ->

class Node {
   int data;
   Node leftChild;
   Node rightChild;
   public Node(int key) {
      data = key;
      leftChild = rightChild = null;
   }
}
public class TreeDataStructure {
   Node root = null;
   void inorder_traversal(Node node) {
      if(node != null) {
         inorder_traversal(node.leftChild);
         System.out.print(node.data + " ->");
         inorder_traversal(node.rightChild);
      }
   }
   public static void main(String args[]) {
      TreeDataStructure tree = new TreeDataStructure();
      tree.root = new Node(27);
      tree.root.leftChild = new Node(12);
      tree.root.rightChild = new Node(30);
      tree.root.leftChild.leftChild = new Node(4);
      tree.root.leftChild.rightChild = new Node(17);
      tree.root.rightChild.leftChild = new Node(56);
      System.out.println("Inorder traversal: ");
      tree.inorder_traversal(tree.root);
   }
}

输出

Inorder traversal: 
4 ->12 ->17 ->27 ->56 ->30 ->

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

# 插入方法创建节点
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
         else:
            self.data = data

# 打印树
   def Inorder(self):
      if self.left:
         self.left.Inorder()
         print(self.data, "->", end = " ")
      if self.right:
         self.right.Inorder()

root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Inorder Traversal: ")
root.Inorder()

输出

Inorder Traversal: 
12 -> 34 -> 54 ->

前序遍历

二叉搜索树中的前序遍历操作会访问其所有节点。但是，首先打印根节点，然后打印其左子树，最后打印其右子树。

算法

1. 开始
2. 首先遍历根节点。
3. 然后递归遍历左子树。
4. 最后递归遍历右子树。
5. 结束

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct node {
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

// 先序遍历
void preorder(struct node *root){
   if (root != NULL) {
      printf("%d -> ", root->key);
      preorder(root->left);
      preorder(root->right);
   }
}

// 插入操作
struct node *insert(struct node *node, int key){
   if (node == NULL) return newNode(key);
   if (key < node->key)
      node->left = insert(node->left, key);
   else
      node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 55);
   root = insert(root, 20);
   root = insert(root, 90);
   root = insert(root, 50);
   root = insert(root, 35);
   root = insert(root, 15);
   root = insert(root, 65);
   printf("Preorder traversal: ");
   preorder(root);
}

输出

Preorder traversal: 55 -> 20 -> 15 -> 50 -> 35 -> 90 -> 65 ->

#include <iostream>
struct node {
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

// 先序遍历
void preorder(struct node *root){
   if (root != NULL) {
      printf("%d -> ", root->key);
      preorder(root->left);
      preorder(root->right);
   }
}

// 插入操作
struct node *insert(struct node *node, int key){
   if (node == NULL) return newNode(key);
   if (key < node->key)
      node->left = insert(node->left, key);
   else
      node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 55);
   root = insert(root, 20);
   root = insert(root, 90);
   root = insert(root, 50);
   root = insert(root, 35);
   root = insert(root, 15);
   root = insert(root, 65);
   printf("Preorder traversal: ");
   preorder(root);
}

输出

Preorder traversal: 55 -> 20 -> 15 -> 50 -> 35 -> 90 -> 65 ->

class Node {
    int data;
    Node leftChild;
    Node rightChild;
    public Node(int key) {
        data = key;
        leftChild = rightChild = null;
    }
}
public class TreeDataStructure {
    Node root = null;
    void preorder_traversal(Node node) {
        if(node != null) {
            System.out.print(node.data + " ->");
            preorder_traversal(node.leftChild);
            preorder_traversal(node.rightChild);
        }
    }
    public static void main(String args[]) {
        TreeDataStructure tree = new TreeDataStructure();
        tree.root = new Node(27);
        tree.root.leftChild = new Node(12);
        tree.root.rightChild = new Node(30);
        tree.root.leftChild.leftChild = new Node(4);
        tree.root.leftChild.rightChild = new Node(17);
        tree.root.rightChild.leftChild = new Node(56);
        System.out.println("Preorder traversal: ");
        tree.preorder_traversal(tree.root);
    }
}

输出

Preorder traversal: 
27 ->12 ->4 ->17 ->30 ->56 ->

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# 插入方法创建节点
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
         else:
            self.data = data

# 打印树
   def Preorder(self):
      print(self.data, "->", end = "")
      if self.left:
         self.left.Preorder()
      if self.right:
         self.right.Preorder()
root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Preorder Traversal: ")
root.Preorder()

输出

Preorder Traversal: 
54 ->34 ->12 ->5 ->23 ->46 ->

后序遍历

与其他遍历类似，后序遍历也会访问二叉搜索树中的所有节点并显示它们。但是，先打印左子树，然后打印右子树，最后打印根节点。

算法

1. 开始
2. 递归遍历左子树
3. 递归遍历右子树。
4. 然后，遍历根节点
5. 结束

示例

以下是此操作在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct node {
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

// 后序遍历
void postorder(struct node *root){
   if (root != NULL) {
      printf("%d -> ", root->key);
      postorder(root->left);
      postorder(root->right);
   }
}

// 插入操作
struct node *insert(struct node *node, int key){
   if (node == NULL) return newNode(key);
   if (key < node->key)
      node->left = insert(node->left, key);
   else
      node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 55);
   root = insert(root, 20);
   root = insert(root, 90);
   root = insert(root, 50);
   root = insert(root, 35);
   root = insert(root, 15);
   root = insert(root, 65);
   printf("Postorder traversal: ");
   postorder(root);
}

输出

Postorder traversal: 55 -> 20 -> 15 -> 50 -> 35 -> 90 > 65 ->

#include <iostream>
struct node {
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

// 后序遍历
void postorder(struct node *root){
   if (root != NULL) {
      printf("%d -> ", root->key);
      postorder(root->left);
      postorder(root->right);
   }
}

// 插入操作
struct node *insert(struct node *node, int key){
   if (node == NULL) return newNode(key);
   if (key < node->key)
      node->left = insert(node->left, key);
   else
      node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 55);
   root = insert(root, 20);
   root = insert(root, 90);
   root = insert(root, 50);
   root = insert(root, 35);
   root = insert(root, 15);
   root = insert(root, 65);
   printf("Postorder traversal: ");
   postorder(root);
}

输出

Postorder traversal: 55 -> 20 -> 15 -> 50 -> 35 -> 90 -> 65 ->

class Node {
    int data;
    Node leftChild;
    Node rightChild;
    public Node(int key) {
        data = key;
        leftChild = rightChild = null;
    }
}
public class TreeDataStructure {
    Node root = null;
    void postorder_traversal(Node node) {
        if(node != null) {
            postorder_traversal(node.leftChild);
            postorder_traversal(node.rightChild);
            System.out.print(node.data + " ->");
        }
    }
    public static void main(String args[]) {
        TreeDataStructure tree = new TreeDataStructure();
        tree.root = new Node(27);
        tree.root.leftChild = new Node(12);
        tree.root.rightChild = new Node(30);
        tree.root.leftChild.leftChild = new Node(4);
        tree.root.leftChild.rightChild = new Node(17);
        tree.root.rightChild.leftChild = new Node(56);
        System.out.println("Postorder traversal: ");
        tree.postorder_traversal(tree.root);
    }
}

输出

Postorder traversal: 
4 ->17 ->12 ->56 ->30 ->27 ->

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

# 插入方法创建节点
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
      else:
         self.data = data

# 打印树
   def Postorder(self):
      if self.left:
         self.left.Postorder()
      if self.right:
         self.right.Postorder()
      print(self.data, "->", end = "")

root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Postorder Traversal: ")
root.Postorder()

输出

Postorder Traversal: 
5 ->23 ->12 ->46 ->34 ->54 ->

完整实现

以下是二叉搜索树在各种编程语言中的完整实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
struct node {
   int data;
   struct node *leftChild, *rightChild;
};
struct node *root = NULL;
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
}
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //如果树为空
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;

         //去树的左边
         if(data < parent->data) {
            current = current->leftChild;

            //插入到左侧
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//去树的右边
         else {
            current = current->rightChild;
            
            //插入到右侧
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   while(current->data != data) {
      if(current != NULL) {
         //去左边的树
         if(current->data > data) {
            current = current->leftChild;
         }//否则转到右边的树
         else {
            current = current->rightChild;
         }

         //not found
         if(current == NULL) {
            return NULL;
         }
      }
   }
   return current;
}

// 中序遍历
void inorder(struct node *root){
   if (root != NULL) {
      inorder(root->leftChild);
      printf("%d -> ", root->data);
      inorder(root->rightChild);
   }
}

// 先序遍历
void preorder(struct node *root){
   if (root != NULL) {
      printf("%d -> ", root->data);
      preorder(root->leftChild);
      preorder(root->rightChild);
   }
}

// 后序遍历
void postorder(struct node *root){
   if (root != NULL) {
      printf("%d -> ", root->data);
      postorder(root->leftChild);
      postorder(root->rightChild);
   }
}
int main(){
   insert(55);
   insert(20);
   insert(90);
   insert(50);
   insert(35);
   insert(15);
   insert(65);
   printf("Insertion done");
   printf("
Preorder Traversal: ");
   preorder(root);
   printf("
Inorder Traversal: ");
   inorder(root);
   printf("
Postorder Traversal: ");
   postorder(root);
   struct node* k;
   int ele = 35;
   printf("
Element to be searched: %d", ele);
   k = search(35);
   if(k != NULL)
      printf("
Element %d found", k->data);
   else
      printf("
Element not found");
   return 0;
}

输出

Insertion done
Preorder Traversal: 55 -> 20 -> 15 -> 50 -> 35 -> 90 -> 65 -> 
Inorder Traversal: 15 -> 20 -> 35 -> 50 -> 55 -> 65 -> 90 -> 
Postorder Traversal: 55 -> 20 -> 15 -> 50 -> 35 -> 90 -> 65 -> 
Element to be searched: 35
Element 35 found

#include <iostream>
using namespace std;
struct node {
   int data;
   struct node *leftChild, *rightChild;
};
struct node *root = NULL;
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = item;
   temp->leftChild = temp->rightChild = NULL;
   return temp;
}
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   
   //如果树为空
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;

         //去树的左边
         if(data < parent->data) {
            current = current->leftChild;

            //插入到左侧
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//去树的右边
         else {
            current = current->rightChild;
            
            //插入到右侧
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   while(current->data != data) {
         //去左边的树
         if(current->data > data) {
            current = current->leftChild;
         }//否则转到右边的树
         else {
            current = current->rightChild;
         }
         
         //not found
         if(current == NULL) {
            return NULL;
         }
   }
   return current;
}

// 中序遍历
void inorder(struct node *root){
   if (root != NULL) {
      inorder(root->leftChild);
      cout<<root->data<<" ->";
      inorder(root->rightChild);
   }
}

// 先序遍历
void preorder(struct node *root){
   if (root != NULL) {
      cout<<root->data<<" ->";
      preorder(root->leftChild);
      preorder(root->rightChild);
   }
}

// 后序遍历
void postorder(struct node *root){
   if (root != NULL) {
      cout<<" -> "<<root->data;
      postorder(root->leftChild);
      postorder(root->rightChild);
   }
}
int main(){
   insert(55);
   insert(20);
   insert(90);
   insert(50);
   insert(35);
   insert(15);
   insert(65);
   cout<<"Insertion done ";
   cout<<"
Preorder Traversal: ";
   preorder(root);
   cout<<"
Inorder Traversal: ";
   inorder(root);
   cout<<"
Postorder Traversal: ";
   postorder(root);
   struct node* k;
   int ele = 35;
   cout<<"
Element tonbe searched: "<<ele;
   k = search(35);
   if(k != NULL)
      cout<<"
Element "<<k->data<<" found";
   else
      cout<<"
Element not found";
   return 0;
}

输出

Insertion done 
Preorder Traversal: 55 ->20 ->15 ->50 ->35 ->90 ->65 ->
Inorder Traversal: 15 ->20 ->35 ->50 ->55 ->65 ->90 ->
Postorder Traversal:  -> 55 -> 20 -> 15 -> 50 -> 35 -> 90 -> 65
Element tonbe searched: 35
Element 35 found

import java.util.Scanner;
class BSTNode {
   BSTNode left, right;
   int data;
   public BSTNode(int n) {
      left = null;
      right = null;
      data = n;
   }
}
public class BST {
   static BSTNode root;
   public BST() {
      root = null;
   }
   public boolean isEmpty() {
      return root == null;
   }
   private BSTNode insert(BSTNode node, int data) {
      if(node == null)
         node = new BSTNode(data);
      else {
         if(data <= node.data)
            node.left = insert(node.left, data);
         else
            node.right = insert(node.right, data);
      }
      return node;
   }
   public void delete(int k) {
      if(isEmpty ())
         System.out.println("TREE EMPTY");
      else if(search (k) == false)
         System.out.println("SORRY " + k + " IS NOT PRESENT");
      else {
         root=delete(root,k);
         System.out.println(k + " DELETED FROM THE TREE");
      }
   }
   public BSTNode delete(BSTNode root, int k) {
      BSTNode p, p2, n;
      if(root.data == k) {
         BSTNode lt, rt;
         lt = root.left;
         rt = root.right;
         if(lt == null && rt == null) {
            return null;
         } else if(lt == null) {
            p = rt;
            return p;
         } else if(rt == null) {
            p = lt;
            return p;
         } else {
            p2 = rt;
            p = rt;
            while(p.left != null)
               p = p.left;
            p.left = lt;
            return p2;
         }
      }
      if (k < root.data) {
         n = delete(root.left, k);
         root.left = n;
      } else {
         n = delete(root.right, k);
         root.right = n;
      }
      return root;
   }
   public boolean search(int val) {
      return search(root, val);
   }
   private boolean search(BSTNode r, int val) {
      boolean found = false;
      while ((r != null) && !found) {
         int rval = r.data;
         if(val < rval)
            r = r.left;
         else if (val > rval)
            r = r.right;
         else {
            found = true;
            break;
         }
         found = search(r, val);
      }
      return found;
   }
   void printTree(BSTNode node, String prefix) {
      if(node == null)
         return;
      printTree(node.left , " " + prefix);
      System.out.println(prefix + "--" + node.data);
      printTree(node.right , prefix + " ");
   }
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      BST bst = new BST();
      root = bst.insert(root, 55);
      root = bst.insert(root, 20);
      root = bst.insert(root, 90);
      root = bst.insert(root, 80);
      root = bst.insert(root, 50);
      root = bst.insert(root, 35);
      root = bst.insert(root, 15);
      root = bst.insert(root, 65);
      bst.printTree(root, " ");
      bst.delete(55);
      System.out.println("Element found = " + bst.search(80));
      System.out.println("Is Tree Empty? " + bst.isEmpty());
   }
}

输出

--15
  --20--35
   --50
 --55
    --65
   --80
  --90
55 DELETED FROM THE TREE
Element found = true
Is Tree Empty? false

class Node:
   def __init__(self, data):
     self.left = None
     self.right = None
     self.data = data

# 插入方法创建节点
   def insert(self, data):
     if self.data:
       if data < self.data:
         if self.left is None:
            self.left = Node(data)
         else:
            self.left.insert(data)
       elif data > self.data:
         if self.right is None:
            self.right = Node(data)
         else:
            self.right.insert(data)
       else:
         self.data = data

# 搜索方法将值与节点进行比较
   def search(self, key):
     if key < self.data:
       if self.left is None:
         return str(key)+ " Not Found"
       return self.left.search(key)
     elif key > self.data:
       if self.right is None:
         return str(key)+" Not Found"
       return self.right.search(key)
     else:
       print(str(self.data) + ' is found')

# 打印树
   def Inorder(self):
     if self.left:
       self.left.Inorder()
     print(self.data , " ->", end = " ")
     if self.right:
       self.right.Inorder()

# 打印树
   def Preorder(self):
     print(self.data, " ->", end = " ")
     if self.left:
       self.left.Preorder()
     if self.right:
       self.right.Preorder()

# 打印树
   def Postorder(self):
     if self.left:
       self.left.Postorder()
     if self.right:
       self.right.Postorder()
     print(self.data, " ->", end = " ")

root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Insertion Done")
print("Preorder Traversal: ")
root.Preorder()
print("
Inorder Traversal: ")
root.Inorder()
print("
Postorder Traversal: ")
root.Postorder()
ele = 17
print("
Element to be searched: ", ele)
print(root.search(ele))

输出

Insertion Done
Preorder Traversal: 
54  -> 34  -> 12  -> 5  -> 23  -> 46  -> 
Inorder Traversal: 
5  -> 12  -> 23  -> 34  -> 46  -> 54  -> 
Postorder Traversal: 
5  -> 23  -> 12  -> 46  -> 34  -> 54  -> 
Element to be searched:  17
17 Not Found

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

二叉搜索树

二叉树表示

基本操作

定义节点

搜索操作

算法

示例

输出

输出

输出

输出

插入操作

算法

示例

输出

输出

输出

输出

中序遍历

算法

示例

输出

输出

输出

输出

前序遍历

算法

示例

输出

输出

输出

输出

后序遍历

算法

示例

输出

输出

输出

输出

完整实现

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！