二元搜尋樹（Binary Search Tree）建立的方法

• insert: 新增元素進入樹中
• delete: 從樹中刪除此元素
• preOrderTraversal: 前序走訪
• inOrderTraversal: 中序走訪
• postOrderTraversal: 後序走訪
• search: 搜尋此元素是否在樹中

二元搜尋樹的介紹可以參考此篇。

JavaScript

//BST
class Node{
  constructor(data){
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree{
  constructor(){
    this.root = null;
  }
  //插入元素進入樹中
  insert(data){
    let newNode = new Node(data);
    if(this.root === null)
      this.root = newNode;
    else
      this.insertNode(this.root, newNode);
  }
  insertNode(node, newNode){
    if(newNode.data < node.data){
      if(node.left === null)
        node.left = newNode;
      else
        this.insertNode(node.left, newNode);
    }else{
        if(node.right === null)
          node.right = newNode;
        else
          this.insertNode(node.right,newNode);
    }
  }
  
  //從樹中刪除此元素
  delete(data){
    this.root = this.deleteNode(this.root, data);
  }
  deleteNode(node, data){
      if(node === null){
        return null;
      }else if(data < node.data){
        node.left = this.deleteNode(node.left, data);
        return node;
      }else if(data > node.data){
        node.right = this.deleteNode(node.right, data);
        return node;
      }else{
        if(node.left === null && node.right === null){
          node = null;
          return node;
        }
        if(node.left === null){
          node = node.right;
          return node;
        }
        if(node.right === null){
          node = node.left;
          return node;
        }
        let aux = this.min(node.right);
        node.data = aux.data;
        node.right = this.deleteNode(node.right, aux.data);
        return node;
      }

  }
  
  min(node=this.root){
    if(node){
      while(node && node.left !== null){
        node = node.left
      }
      return node.data
    }
    return null
  }   
  
  //前序走訪
  preOrderTraversal(){
    let res = [];
    let preHelper=(node)=>{
      if (node) {
        res.push(node.data);
        preHelper(node.left);
        preHelper(node.right);
      }
    }   
    preHelper(this.root);
    return res;
  }
 
  //中序走訪
  inOrderTraversal(){
    let res = [];
    let inHelper=(node)=>{
      if (node) {
        inHelper(node.left);
        res.push(node.data);
        inHelper(node.right);
      }
    }    
    inHelper(this.root);
    return res;
  }
  
  //後序走訪
  postOrderTraversal(){
    const res = [];
    let postHelper=(node)=>{
      if (node) {
        postHelper(node.left);
        postHelper(node.right);
        res.push(node.data);
      }
    }   
    postHelper(this.root);
    return res;
  }
  
  //搜尋此元素是否在樹中
  search(data, node=this.root){
    if(!node){
      return false
    }
    if(data < node.data){
      return this.search(data, node.left)
    }else if(data > node.data){
      return this.search(data, node.right)
    }
    if (data === node.data) {
      return true;
    }
  }  

  
}

let tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
console.log("Pre Order Traversal:"+tree.preOrderTraversal())//11,7,5,3,9,15
console.log("In Order Traversal:"+tree.inOrderTraversal())//3,5,7,9,11,15
console.log("Post Order Traversal:"+tree.postOrderTraversal())//3,5,9,7,15,11
tree.delete(9)
console.log(tree.search(9))//false

Python

#BST
class BinarySearchTree:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

    #插入元素進入樹中
    def insert(self, data):
        if not self.data:
            self.data = data
            return

        if self.data == data:
            return

        if data < self.data:
            if self.left:
                self.left.insert(data)
                return
            self.left = BinarySearchTree(data)
            return

        if self.right:
            self.right.insert(data)
            return
        self.right = BinarySearchTree(data)

    #從樹中刪除此元素
    def delete(self, data):
        if self == None:
            return self
        if data < self.data:
            if self.left:
                self.left = self.left.delete(data)
            return self
        if data > self.data:
            if self.right:
                self.right = self.right.delete(data)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        aux = self.right
        while aux.left:
            aux = aux.left
        self.data = aux.data
        self.right = self.right.delete(aux.data)
        return self

    #前序走訪
    def preOrderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.preOrderTraversal(root.left)
            res = res + self.preOrderTraversal(root.right)
        return res

    #中序走訪
    def inOrderTraversal(self,root):
        res = []
        if root:
            res = self.inOrderTraversal(root.left)
            res.append(root.data)
            res = res + self.inOrderTraversal(root.right)
        return res

    #後序走訪
    def postOrderTraversal(self, root):
        res = []
        if root:
            res = self.postOrderTraversal(root.left)
            res = res + self.postOrderTraversal(root.right)
            res.append(root.data)
        return res

    #搜尋此元素是否在樹中
    def search(self, data):
        if not self.data:
            return False

        if data < self.data:
            if self.left == None:
                return False
            return self.left.search(data)

        if data > self.data:
            if self.right == None:
                return False
            return self.right.search(data)

        if data == self.data:
            return True

tree = BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
print(tree.preOrderTraversal(tree))#11, 7, 5, 3, 9, 15
print(tree.inOrderTraversal(tree))#3, 5, 7, 9, 11, 15
print(tree.postOrderTraversal(tree))#3, 5, 9, 7, 15, 11
print(tree.search(9))#True
tree.delete(9)
print(tree.search(9))#False

在各走訪中使用到遞回函式可以參考此篇。