樹心幽徑

« 20200525在90.2Fedora LINUX機器昇級PHP | Main | 20200529在LINUX安裝GCC10.1 »

20200526用python設計二元搜尋樹(Binary Search Tree)
2020/05/26,05:02

(一)二元搜尋樹說明:

參考:http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html

(1)樹資料結構由節點及分支所組存,樹由根節點往下生長,每個節點可有多個子樹(分支),二元樹每一個節點至多二個子樹。樹不能有廻路(即所有的分支皆以分開了,不可再相連),

(2)二元搜尋樹:將比根節點值小的數放在左子樹(前方)中,將比根節點值大的數放在右子樹(後方)中。

例如:將如下數字50,19,28,88,93,31,22依序加入一個空的根節點可建立一棵二元搜尋樹如下:

                         50
                        /    \                         
                      19     88
                         \        \
                         28       93
                         /  \
                     22    31                                                

(3)中序走訪法(InOrder Traversal): 先走訪左子樹,再走訪根節點,再走訪右子樹。

用本法走訪(2)中的樹結果如下:19, 22, 28, 31, 50, 88, 95

(4)前序走訪法(PreOrder Traversal):先走訪根節點,再走訪左子樹,再走訪右子樹。

用本法走訪(2)中的樹結果如下:50, 19, 28, 22, 31, 88, 95

(5)後序走訪法(PostOrder Traversal):先走訪左子樹,再走訪右子樹,再走訪根節點。

用本法走訪(2)中的樹結果如下:22, 31, 28, 19, 95, 88, 50

(二)PYTHON程式:

(1)由windows開始功能表執行 IDLE(python 3.7 64bit)

    安裝python請參考:20191014在windows7安裝並使用python3.7.4來剖析數字序列字串

(2)按CTRL+N在PYTHON文字編輯器編寫如下程式碼,並存為 d:\tree.py

class treeNode:
    def __init__(self, val):
         self.val = val
         self.left = None
         self.right = None

    def insertT(self, val):
         if val <= self.val:
             if self.left == None:
                 self.left = treeNode(val)
             else:
                 self.left.insertT(val)
         else:
             if self.right == None:
                 self.right = treeNode(val)
             else:
                 self.right.insertT(val)

    def inorderT(self, root):
        res = []
        if root:
            res = self.inorderT(root.left)
            res.append(root.val)
            res = res + self.inorderT(root.right)
        return res

    def PreorderT(self, root):
        res = []
        if root:
            res.append(root.val)
            res = res + self.PreorderT(root.left)
            res = res + self.PreorderT(root.right)
        return res
   
    def PostorderT(self, root):
        res = []
        if root:
            res = self.PostorderT(root.left)
            res = res + self.PostorderT(root.right)
            res.append(root.val)
        return res


root = treeNode(50)
root.insertT(19)
root.insertT(28)
root.insertT(88)
root.insertT(95)
root.insertT(31)
root.insertT(22)

print('中序:' , root.inorderT(root))
print('前序:' , root.PreorderT(root))
print('後序:' , root.PostorderT(root))


(3)在PYTHON文字編輯器按F5可儲存編寫的程式碼並執行之:

中序: [19, 22, 28, 31, 50, 88, 95]
前序: [50, 19, 28, 22, 31, 88, 95]
後序: [22, 31, 28, 19, 95, 88, 50]

 

 

(4)

a = []

for i in range(5):   

x= input("x=")   

a.append(x)

print(a)

 

迴響

 
Accessible and Valid XHTML 1.0 Strict and CSS Powered by LifeType