(一)二元搜尋樹說明：
參考：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文字編輯器按Ｆ５可儲存編寫的程式碼並執行之：
中序: [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)
|