---
# System prepended metadata

title: BTS CRUD 完整版

---

# BTS CRUD 完整版

# ＢＴＳ_ＣＲＵＤ完整程式碼 
[toc]

## 和二元樹的比較 
1. preorder 相同
2. BST search 部分 需要多一個和父節點比大小去判斷是不是要繼續recursive(同時也要保有原本的是否存在左右子樹)，也因此造就筆BT 更快速的search 
3. 

```python!
class Node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None #smaller
        self.right_child = None #greater
        self.parent = None # pointer to parent node in tree


class Binary_search_tree:
    def __init__(self):
        self.root = None


    def insert(self, value):
        #判斷tree是否為空
        if self.root == None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)


    def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = Node(value)
                cur_node.left_child.parent = cur_node #set parent
            else:
                self._insert(value, cur_node.left_child)


        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = Node(value)
                
                # 為什麼要回頭設parent  是因為這個example 是雙向鏈結嗎？
                cur_node.right_child.parent = cur_node #set parent
            else:
                self._insert(value, cur_node.right_child)


        # value == cur_node.value
        else:
            print("This value has existed")


    def print_tree(self):
        if self.root!=None:
        	self._print_tree(self.root)


    def _print_tree(self,cur_node):
    	if cur_node!=None:
        	self._print_tree(cur_node.left_child)
        	print(str(cur_node.value))
        	self._print_tree(cur_node.right_child)






    def height(self):
        if self.root != None:
            return self._height(self.root,0)
        else:
            return


    # 我們要在每一次遞迴呼叫時傳入cur_height，如果沒有像parameter
    # 樣傳入或儲存成global variable會造成 無法儲存cur_height
    def _height(self, cur_node, cur_height):
        if cur_node == None:
            return cur_height #0
        # 找一個最高的子樹
        left_height = self._height(cur_node.left_child,cur_height+1)
        right_height = self._height(cur_node.right_child,cur_height+1)


        return max(left_height, right_height)


    # returns the node with specified input value
    def find(self, value):
        if self.root != None:
            return self._find(value, self.root)
        else:
            return None


    def _find(self, value, cur_node):
        if value == cur_node.value:
            return cur_node
        elif value < cur_node.value and cur_node.left_child != None:
            return self._find(value, cur_node.left_child)
        elif value > cur_node.value and cur_node.right_child != None:
            return self._find(value, cur_node.right_child)


    def delete_value(self, value):
        return self.delete_node(self.find(value))


    def delete_node(self, node):
        #returns the node with min value in tree rooted at input Node
        #we will pass the single node to treat as the root of a binary search fill_tree
        def min_value_node(n):
            current = n
            # traverse down to the left of the tree until it finds the smallest element returning this value
            while current.left_child != None:
                current = current.left_child
            return current

            #returns the number of children for the specified node
            # return the number of the children and attach the input node either 0,1 or two
        def num_children(n):
            num_children = 0
            if n.left_child != None:
                num_children +=1
            if n.right_child != None:
                num_children += 1
            return num_children


        #create variable to hold both the parent of the node to delete as well as
        #the number of children get the parent of the node to be deleted
        node_parent = node.parent


        #get the number of children of the node to be deleted
        node_children = num_children(node)


        #break operation into different cases based on the
        #structure of the tree & node to be delete


        #CASE 1 (node has no children)
        if node_children == 0:
            #remove reference to the node from the node_parent
            if node_parent.left_child == node:
                node_parent.left_child = None
            else:
                node_parent.right_child = None


        #CASE 2 (node has a single child)
        if node_children == 1:


            # get the single child node
            if node.left_child != None:
                child = node.left_child
            else:
                child = node.right_child

            # 把目前節點的父節點連到子節點 越過它，所已前面才需要有parent linked 
            #replace the node to be deleted with its child
            if node_parent.left_child == node:
                node_parent.left_child = child
            else:
                node_parent.right_child = child


            #correct the parent pointer in node
            child.parent = node_parent


        #CASE 3 (node has two children)
        if node_children == 2:


            # get the inorder successor of the deleted 
            # 找右邊子樹的左子樹最底層leaf(整個右邊子樹中最小的)，
            #所以我們才要放入right_child  然後在min_value_node中卻是travel left_child
            successor = min_value_node(node.right_child)


            #copy the inorder successor's value to the node formerly
            #holding the value we wished th delete
            
            node.value = successor.min_value_node
            


            #delete the inorder successor now that it's value was
            #copied into the other node
            self.delete_node(successor)
    def search(self, value):
        if self.root != None:
            return self._search(value, self.root)
        else:
            return False


    def _search(self, value, cur_node):
        if value == cur_node.value:
            return True
        elif value < cur_node.value and cur_node.left_child != None:
            return self._search(value, cur_node.left_child)
        elif value > cur_node.value and cur_node.right_child != None:
            return self._search(value, cur_node.right_child)
        else:
            return False


def fill_tree(tree, num_elems=10, max_int=50):
    from random import randint
    for _ in range(num_elems): #10個 value
        cur_elem = randint(0, max_int) #隨機0~50(不含50)的值
        tree.insert(cur_elem)
    return tree


#============================================================
#建立1~9的樹
tree = Binary_search_tree()
for num in range(10):
    tree.insert(num)


#delete node 5
tree.delete_value(5)

#印出樹
tree.print_tree()
```