# 二元樹
[toc]
## binary tree 概念
二元樹(Binary Tree)是最廣泛被使用的樹狀資料結構，簡單來說即為每個節點最多只能有兩個子節點。
## 樹與二元樹不同之處
- 樹不能是空集合，二元樹可以是空集合。
- 樹的分支度是 d ≥ 0，二元樹的分支度是 0 ≤ d ≤ 2。就是最多兩個子樹
- **樹的左右沒有次序關係，二元樹的左右有次序關係 從左到右填入**
**樹的左右沒有次序關係，二元樹的左右有次序關係 從左到右填入**
衍生出complete binary tree and full binary tree
## 三種搜尋方法在binary tree
The main traversal operations of a binary tree are as follows.
**Pre-order traversal** – Traverse the root node first and then the left subtree and right subtree. This process applies to each subtree recursively.
**In order traversal** – Traverse the left subtree first, then the root node and right subtree. This process applies to each subtree recursively.
**Post-order traversal** – Traverse the left subtree, then the right and the root node. This process applies to each subtree recursively.
## 二元樹的種類(most important )
1. **完整二元樹(Complete Binary Tree)一棵二元樹中，除了最後一層不是滿的，其餘層都是滿的。**
2. 非完整二元樹
就是中間不一定都被填滿，所以用array 去儲存會浪費空間，用linked list 比較好。
在非完整二元樹中，可能存在一些浪費空間的情況，這是因為在使用陣列表示樹時，需要為每個節點分配固定大小的空間，即使節點的度數較低或存在空缺的位置也需要保留。這種情況下，部分陣列中的位置被浪費掉，沒有有效地利用起來。
浪費空間的主要原因如下：
1. 空節點：在非完整二元樹中，某些位置可能沒有節點存在，但在陣列中仍然需要保留空間。這樣就導致了一些位置被浪費掉，沒有被實際使用。
2. 低度節點：非完整二元樹中的某些節點的度數可能較低，即該節點的子節點數量較少。然而，在陣列表示中，為了保持結構的一致性，仍然需要為這些節點分配固定大小的空間。這就造成了一些空間的浪費。
浪費空間對於陣列表示的非完整二元樹來說是一種不可避免的情況，因為陣列需要確保節點之間的連續性和結構的一致性。然而，這種浪費通常是可接受的，特別是當樹的大小不是非常龐大時。對於非常大的樹，可能需要考慮其他的數據結構表示方法，以節省空間。
3. 完滿二元樹(Fully Binary Tree)每一層節點數都是最大節點數量。
4. 歪斜樹(Skewed Binary Tree)一棵二元樹中，完全沒有左邊或右邊節點，如果集中左邊為「左歪斜樹」，集中右邊為「右歪斜樹」。
## 常見二元樹的實作方式
1. **陣列表示法**根節點放在陣列索引位置 0。若父節點索引為 i：
- 父節點的左子節點，放在陣列索引位置 (2 * i) + 1。
- 父節點的右子節點，放在陣列索引位置 (2 * i) + 2。
- 若節點不為根節點，節點的父節點放在陣列索引位置 (i - 1) / 2（取商）。
- 每一層的節點數量為 2^(n-1) n=節層數
* 陣列的儲存方法 在左右歪斜 以及delete or insert 時效率比不上Linked list
2. 鏈結串列表示法節點含有兩個指標，左右指標分別指向左邊的子節點與右邊的子節點。
## 二元樹建立程式碼
```python=
class TreeNode:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
new=TreeNode("Drink")
hot=TreeNode("hot")
cold=TreeNode("cold")
new.left=hot
new.right=cold
```
# 二元樹追蹤（前中後序）
**記得前中後序的定義，是以你的中間node的順序為定(中文)**
**記得你travel 的function跟class 是同層級，並不是類別內函數**
**圖二(a)-(c) 依序為： (a)pre-order：VLR、(b)in-order：LVR、(c)post-order：LRV**
**pre-order(VLR)**：當CurrentNode移動到A時，會先對A進行Visiting，接著前往left child進行Visiting，再前往right child進行Visiting。(若child指向NULL則忽略。)
**in-order(LVR)**：當CurrentNode移動到A時，會先對A的left child(B)進行Visiting，接著回到A進行Visiting，再前往right child(C)進行Visiting。(若child指向NULL則忽略。)
**post-order(LRV)**：當CurrentNode移動到A時，會先對A的left child(B)進行Visiting，再前往right child(C)進行Visiting，接著回到A進行Visiting。(若child指向NULL則忽略。)
## pre-order python 實作
```python=
class TreeNode:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
new=TreeNode("Drink")
hot=TreeNode("hot")
cold=TreeNode("cold")
new.left=hot
new.right=cold
def preTravel(node):
if not node : # 到最末端葉子還是會呼叫一次，變成是none 傳入下一次的recursion
return
print(node.data) # 中間先取出了 因為順序是中->左->右
preTravel(node.left)
preTravel(node.right)
preTravel(new)
```
## 三種travel 方式
```python=
class TreeNode:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
new=TreeNode("Drink")
hot=TreeNode("hot")
cold=TreeNode("cold")
lette=TreeNode("lette")
cola=TreeNode("cola")
new.left=hot
new.right=cold
hot.left=lette
cold.left=cola
def preTravel(node):
if not node : # 到最末端葉子還是會呼叫一次，變成是none
return
print(node.data)
preTravel(node.left)
preTravel(node.right)
def inOrder(node):
if not node:
return
inOrder(node.left) # 左邊地回到底
print(node.data)
inOrder(node.right)
def postOrder(node):
if not node:
return
inOrder(node.left) # 走到末端葉子再往下發現沒有東西就回直接return 然後執行下一行
inOrder(node.right)#發現也沒有 所以也return
print(node.data)# 最後就執行這一行
preTravel(new)
print("====")
inOrder(new)
print("====")
postOrder(new)
```
# 二元樹走訪(level order )
就是按照每個階層由左到右印出
1→2→3→4→5
# 二元樹走訪全部code (linked list 版本)
## 簡潔版本
```python=
from collections import deque
class TreeNode:
def __init__(self,data):
self.data=data
self.right=None
self.left=None
root=TreeNode("A")
left_1=TreeNode("B")
right_1=TreeNode("C")
root.left=left_1
root.right=right_1
def preOrder(root):
if not root :
return
print(root.data)
preOrder(root.left)
preOrder(root.right)
def levelOrderTravel(root):
if not root :
return
q=deque()
q.append(root)
while q :
root=q.popleft()
print(root.data)
if root.left:
q.append (root.left)
if root.right:
q.append(root.right)
def searchBT(root,target):
if not root:
return "not exist"
q=deque()
q.append(root)
while q:
root=q.popleft()
if root.data==target:
print("found",root.data)
return root
else:
if root.left:
q.append(root.left)
else:
q.append(root.right)
return "not exist "
def insert(root,new):
if not root :
return
q=deque()
q.append(root)
while q:
root=q.popleft()
if root.left:
q.append(root.left)
else :
root.left=new
#print(root.left.data)
return "insert done "
if root.right:
q.append(root.right)
else:
root.right=new
return "insert done "
return
def getDeepNode(root):
if not root :
return
q=deque()
q.append(root)
while q:
root=q.popleft()
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)
print("deep=",root.data)
return
def deleteLast(root):
if not root :
return
q=deque()
q.append(root)
while q:
root=q.popleft()
if root.right:
if
preOrder(root)
print(" ")
levelOrderTravel(root)
searchBT(root,"B")
insert(root,TreeNode("D"))
insert(root,TreeNode("E"))
levelOrderTravel(root)
getDeepNode(root)
```
**用queue 去完成，因為我們要維持node 先進先出**
```python=
# Created by Elshad Karimov
# Copyright © 2020 AppMillers. All rights reserved.
import QueueLinkedList as queue
class TreeNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
newBT = TreeNode("Drinks") # 自己去設定每個node 的左右子樹
leftChild = TreeNode("Hot")
tea = TreeNode("Tea")
coffee = TreeNode("Coffee")
leftChild.leftChild = tea
leftChild.rightChild = coffee
rightChild = TreeNode("Cold")
newBT.leftChild = leftChild
newBT.rightChild = rightChild
def preOrderTraversal(rootNode):
if not rootNode:
return
print(rootNode.data)
preOrderTraversal(rootNode.leftChild)
preOrderTraversal(rootNode.rightChild)
def inOrderTraversal(rootNode):
if not rootNode:
return
inOrderTraversal(rootNode.leftChild)
print(rootNode.data)
inOrderTraversal(rootNode.rightChild)
def postOrderTraversal(rootNode):
if not rootNode:
return
postOrderTraversal(rootNode.leftChild)
postOrderTraversal(rootNode.rightChild)
print(rootNode.data)
def levelOrderTraversal(rootNode):
if not rootNode:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode) # 把整個樹的最上節點放進queue
while not(customQueue.isEmpty()):
root = customQueue.dequeue() #有點像是慢慢解開這個樹，一層一層剝開
print(root.value.data)
if (root.value.leftChild is not None):# 如果這個樹有左子樹，就再放進queue等待下一次的解析
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None):
customQueue.enqueue(root.value.rightChild)
def searchBT(rootNode, nodeValue):
if not rootNode:
return "The BT does not exist" #如果跟節點不在，就直接return
else:
customQueue = queue.Queue() #使用queue資料型態
customQueue.enqueue(rootNode) #把root 加下這個queue
while not(customQueue.isEmpty()): # 如果這個queue 不為空 就要繼續找下去，代表沒有到底
root = customQueue.dequeue() #把queue 第一個值取出，去比對
if root.value.data == nodeValue:
return "Success"
if (root.value.leftChild is not None):#從目前取出的這個點往下看左右子樹，如果有就在加入
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None):
customQueue.enqueue(root.value.rightChild)
return "Not found"
def insertNodeBT(rootNode, newNode):# 很像上面的search tree 這個插入是指在complete tree的情況下插入 所以不能亂插在中間 不然這個二元樹要重新排列
if not rootNode:
rootNode = newNode
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value.leftChild is not None: #如果又節點沒有東西，我們就插入
customQueue.enqueue(root.value.leftChild)
else:
root.value.leftChild = newNode
return "Successfully Inserted"
if root.value.rightChild is not None:
customQueue.enqueue(root.value.rightChild)
else:
root.value.rightChild = newNode
return "Successfully Inserted"
def getDeepestNode(rootNode):
if not rootNode:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode)
while not(customQueue.isEmpty()):
root = customQueue.dequeue() # 跟上面的差不多，我們把整個樹看成很多個子樹
if (root.value.leftChild is not None): # 如果左子樹不為空，我們就加入queue等待下一次的while
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None):
customQueue.enqueue(root.value.rightChild)
deepestNode = root.value # 最後就會得到，因為是complete tree 所以會從左邊開始，如果左邊沒有子樹他就直接跳離while 不會在執行右邊了子樹判斷
return deepestNode
def deleteDeepestNode(rootNode, dNode):
if not rootNode:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value is dNode:
root.value = None
return
if root.value.rightChild:
if root.value.rightChild is dNode:
root.value.rightChild = None
return
else:
customQueue.enqueue(root.value.rightChild)
if root.value.leftChild:
if root.value.leftChild is dNode:
root.value.leftChild = None
return
else:
customQueue.enqueue(root.value.leftChild)
def deleteNodeBT(rootNode, node):
if not rootNode:
return "The BT does not exist"
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode) # queue 放入目前的樹根
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
if root.value.data == node: #如果樹根就是我們要刪掉的點
dNode = getDeepestNode(rootNode)
root.value.data = dNode.data
deleteDeepestNode(rootNode, dNode)
return "The node has been successfully deleted"
if (root.value.leftChild is not None): #如果還有子樹 就丟進queue 然後下一輪再去訓練一次
customQueue.enqueue(root.value.leftChild)
if (root.value.rightChild is not None):
customQueue.enqueue(root.value.rightChild)
return "Failed to delete"
def deleteBT(rootNode):
rootNode.data = None
rootNode.leftChild = None
rootNode.rightChild = None
return "The BT has been successfully deleted"
inOrderTraversal(newBT)
```
使用到的queue檔案
```python=
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
def __str__(self):
return str(self.value)
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def __iter__(self):
curNode = self.head
while curNode:
yield curNode
curNode = curNode.next
class Queue:
def __init__(self):
self.linkedList = LinkedList()
def __str__(self):
values = [str(x) for x in self.linkedList]
return ' '.join(values)
def enqueue(self, value):
newNode = Node(value)
if self.linkedList.head == None:
self.linkedList.head = newNode
self.linkedList.tail = newNode
else:
self.linkedList.tail.next = newNode
self.linkedList.tail = newNode
def isEmpty(self):
if self.linkedList.head == None:
return True
else:
return False
def dequeue(self):
if self.isEmpty():
return "There is not any node in the Queue"
else:
tempNode = self.linkedList.head
if self.linkedList.head == self.linkedList.tail:
self.linkedList.head = None
self.linkedList.tail = None
else:
self.linkedList.head = self.linkedList.head.next
return tempNode
def peek(self):
if self.isEmpty():
return "There is not any node in the Queue"
else:
return self.linkedList.head
def delete(self):
self.linkedList.head = None
self.linkedList.tail = None
custQueue = Queue()
custQueue.enqueue(1)
custQueue.enqueue(2)
custQueue.enqueue(3)
print(custQueue)
print(custQueue.peek())
print(custQueue)
```
# 用list 實作二元樹
```python=
class BinaryTree:
def __init__(self, size):
self.customList = size * [None] # 因為是陣列，所以我們要預先設定大小
self.lastUsedIndex = 0 # 我們實際有在用的index 會和原本的index 差一 因為第一個index 不使用
self.maxSize = size
def insertNode(self, value):
if self.lastUsedIndex + 1 == self.maxSize: # 判斷是否滿了要+1 印為第一個index 不使用
return "The Binary Tree is full"
self.customList[self.lastUsedIndex+1] = value # 直接插入在陣列最後，
self.lastUsedIndex += 1
return "The value has been successfully inserted"
def searchNode(self, nodeValue):
for i in range(len(self.customList)):
if self.customList[i] == nodeValue: # 幹這個就是直接search 整個list==
# linked list 比較複雜是因為他要遞迴，且他的linked 的連接方式不是線性的
return "Success"
return "Not found"
def preOrderTraversal(self, index):
if index > self.lastUsedIndex:
return
print(self.customList[index]) # 因為是中左右 所以先印出中，然後依照index 印出左子樹 然後右子樹==就這樣
self.preOrderTraversal(index*2)
self.preOrderTraversal(index*2 + 1)
def inOrderTraversal(self, index):
if index > self.lastUsedIndex:
return
self.inOrderTraversal(index*2)
print(self.customList[index])
self.inOrderTraversal(index*2+1)
def postOrderTraversal(self, index):
if index > self.lastUsedIndex:
return
self.postOrderTraversal(index*2)
self.postOrderTraversal(index*2+1)
print(self.customList[index])
def levelOrderTraversal(self, index): # 幹這個更簡單，因為本來二元樹就是造著complete tree 建造的
for i in range(index, self.lastUsedIndex+1):
print(self.customList[i])
def deleteNode(self, value):
if self.lastUsedIndex == 0:
return "There is not any node to delete"
for i in range(1, self.lastUsedIndex+1):
if self.customList[i] == value:
self.customList[i] = self.customList[self.lastUsedIndex]
self.customList[self.lastUsedIndex] = None
self.lastUsedIndex -= 1
return "The node has been successfully deleted"
def deleteBT(self):
self.customList = None
return "The BT has been successfully deleted"
newBT = BinaryTree(8)
newBT.insertNode("Drinks")
newBT.insertNode("Hot")
newBT.insertNode("Cold")
newBT.insertNode("Tea")
newBT.insertNode("Coffee")
print(newBT.deleteBT())
newBT.levelOrderTraversal(1)
```
Sign in with Wallet
Connect another wallet