数据结构-二叉搜索树

二叉搜索树（BST）是一棵树，其中所有节点都遵循以下属性 -

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

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

这样，BST将其所有子树分为两段；左子树和右子树可以定义为 -

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

表示

BST 是按维护 BST 属性的方式排列的节点的集合。每个节点都有一个键和一个关联的值。搜索时，将所需的键与 BST 中的键进行比较，如果找到，则检索关联的值。

以下是 BST 的图示 -

我们观察到根节点键（27）在左子树上具有所有较低值的键，在右子树上具有较高值的​​键。

基本操作

以下是树的基本操作 -

• 搜索- 搜索树中的元素。

• 插入- 在树中插入一个元素。

• 预序遍历- 以预序方式遍历树。

• In-order Traversal - 以有序方式遍历树。

• 后序遍历- 以后序方式遍历树。

定义节点

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

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

搜索操作

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

算法

1. START
2. Check whether the tree is empty or not
3. If the tree is empty, search is not possible
4. Otherwise, first search the root of the tree.
5. If the key does not match with the value in the root, search its subtrees.
6. If the value of the key is less than the root value, search the left subtree
7. If the value of the key is greater than the root value, search the right subtree.
8. If the key is not found in the tree, return unsuccessful search.
9. END

例子

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

#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 tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   printf("\nVisiting elements: ");
   while(current->data != data) {
      if(current != NULL) {
         printf("%d ",current->data);
         
         //go to left tree
         if(current->data > data) {
            current = current->leftChild;
         }//else go to right tree
         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\n");
   printTree(root);
   struct node* k;
   k = search(35);
   if(k != NULL)
      printf("\nElement %d found", k->data);
   else
      printf("\nElement not found");
   return 0;
}

Insertion done
 --15 --20 --35 --50 --55 --65 --90
Visiting elements: 55 20 50 
Element 35 found

#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 tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   printf("\nVisiting elements: ");
   while(current->data != data) {
      if(current != NULL) {
         printf("%d ",current->data);
         
         //go to left tree
         if(current->data > data) {
            current = current->leftChild;
         }//else go to right tree
         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\n");
   printTree(root);
   struct node* k;
   k = search(35);
   if(k != NULL)
      printf("\nElement %d found", k->data);
   else
      printf("\nElement not found");
   return 0;
}

Insertion done
 --15 --20 --35 --50 --55 --65 --90
Visiting elements: 55 20 50 
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.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, " ");
      System.out.println("Element found = " + bst.search(root, 80));
   }
}

--15
  --20--35
   --50
 --55
    --65
   --80
  --90
Element found = true

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

# Insert method to create nodes
   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
# search method to compare the value with nodes
   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

插入操作

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

算法

1 – START
2 – If the tree is empty, insert the first element as the root node of the tree. The following elements are added as the leaf nodes.
3 – If an element is less than the root value, it is added into the left subtree as a leaf node.
4 – If an element is greater than the root value, it is added into the right subtree as a leaf node.
5 – The final leaf nodes of the tree point to NULL values as their child nodes.
6 – END

例子

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

#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 tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            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\n");
   printTree(root);
   return 0;
}

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

#include <iostream>
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 tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;
         
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            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\n");
   printTree(root);
   return 0;
}

Insertion done
 --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.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, " ");
   }
}

--15
  --20
--35
   --50
 --55
    --65
   --80
  --90

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

# Insert method to create nodes
   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
root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Insertion Done")

Insertion Done

中序遍历

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

• 首先，我们遍历根节点/当前节点的左子节点（如果有）。

• 接下来，遍历当前节点。

• 最后，遍历当前节点的右子节点（如果有）。

算法

1. START
2. Traverse the left subtree, recursively
3. Then, traverse the root node
4. Traverse the right subtree, recursively.
5. END

例子

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

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

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

// Insertion operation
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;
}

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

// Insertion operation
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("\nInorder 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

# Insert method to create nodes
   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

# Print the tree
   def Inorder(self):
      if self.left:
         self.left.Inorder()
         print(self.data)
      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 of Binary Search Tree: ")
root.Inorder()

Inorder Traversal of Binary Search Tree: 
12
34
54

预序遍历

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

算法

1. START
2. Traverse the root node first.
3. Then traverse the left subtree, recursively
4. Later, traverse the right subtree, recursively.
5. END

例子

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

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

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

// Insertion operation
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;
}

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

// Insertion operation
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("\nPreorder 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

# Insert method to create nodes
   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

# Print the tree
   def Preorder(self):
      print(self.data)
      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 of Binary Search Tree: ")
root.Preorder()

Preorder Traversal of Binary Search Tree: 
54
34
12
5
23
46

后序遍历

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

算法

1. START
2. Traverse the left subtree, recursively
3. Traverse the right subtree, recursively.
4. Then, traverse the root node
5. END

例子

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

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

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

// Insertion operation
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;
}

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

// Insertion operation
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("\nPostorder 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

# Insert method to create nodes
   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

# Print the tree
   def Postorder(self):
      if self.left:
         self.left.Postorder()
      if self.right:
         self.right.Postorder()
      print(self.data)

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

Postorder Traversal of Binary Search Tree: 
5
23
12
46
34
54

例子

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

#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 tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;

            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   printf("\n\nVisiting elements: ");
   while(current->data != data) {
      if(current != NULL) {
         printf("%d ",current->data);

         //go to left tree
         if(current->data > data) {
            current = current->leftChild;
         }//else go to right tree
         else {
            current = current->rightChild;
         }

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

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

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

// Postorder Traversal
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\n");
   printf("\nPreorder Traversal: ");
   preorder(root);
   printf("\nInorder Traversal: ");
   inorder(root);
   printf("\nPostorder Traversal: ");
   postorder(root);
   struct node* k;
   k = search(35);
   if(k != NULL)
      printf("\nElement %d found", k->data);
   else
      printf("\nElement 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 -> 
Visiting elements: 55 20 50 
Element 35 found

#include <iostream>
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 tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1) {
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;

            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}
struct node* search(int data){
   struct node *current = root;
   printf("\n\nVisiting elements: ");
   while(current->data != data) {
      if(current != NULL) {
         printf("%d ",current->data);
         
         //go to left tree
         if(current->data > data) {
            current = current->leftChild;
         }//else go to right tree
         else {
            current = current->rightChild;
         }
         
         //not found
         if(current == NULL) {
            return NULL;
         }
      }
   }
   return current;
}

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

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

// Postorder Traversal
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\n");
   printf("\nPreorder Traversal: ");
   preorder(root);
   printf("\nInorder Traversal: ");
   inorder(root);
   printf("\nPostorder Traversal: ");
   postorder(root);
   struct node* k;
   k = search(35);
   if(k != NULL)
      printf("\nElement %d found", k->data);
   else
      printf("\nElement 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 -> 

Visiting elements: 55 20 50 
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

# Insert method to create nodes
   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

# search method to compare the value with nodes
   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')

# Print the tree
   def Inorder(self):
     if self.left:
       self.left.Inorder()
     print(self.data)
     if self.right:
       self.right.Inorder()

# Print the tree
   def Preorder(self):
     print(self.data)
     if self.left:
       self.left.Preorder()
     if self.right:
       self.right.Preorder()

# Print the tree
   def Postorder(self):
     if self.left:
       self.left.Postorder()
     if self.right:
       self.right.Postorder()
     print(self.data)

root = Node(54)
root.insert(34)
root.insert(46)
root.insert(12)
root.insert(23)
root.insert(5)
print("Preorder Traversal of Binary Search Tree: ")
root.Preorder()
print("Inorder Traversal of Binary Search Tree: ")
root.Inorder()
print("Postorder Traversal of Binary Search Tree: ")
root.Postorder()
print(root.search(17))
print(root.search(12))

Preorder Traversal of Binary Search Tree: 
54
34
12
5
23
46
Inorder Traversal of Binary Search Tree: 
5
12
23
34
46
54
Postorder Traversal of Binary Search Tree: 
5
23
12
46
34
54
17 Not Found
12 is found
None