*****
## 二叉樹的節點表示以及樹的創建
通過使用Node類中定義三個屬性，分別為item本身的值，還有litem和ritem
```
class Node(object):
def __init__(self, item, litem=None, ritem=None):
self.item = item
self.litem = litem
self.ritem = ritem
```
樹的創建,創建一個樹的類，并給一個root根節點，一開始為空，隨后添加節點
```
class Tree(object):
"""樹類"""
def __init__(self, root=None):
self.root = root
def add(self, elem):
"""為樹添加節點"""
node = Node(elem)
# 如果樹是空的，則對根節點賦值
if self.root == None:
self.root = node
else:
queue = []
queue.append(self.root)
# 對已有的節點進行層次遍歷
while queue:
# 彈出隊列的第一個元素
cur = queue.pop(0)
if cur.litem == None:
cur.litem = node
return
elif cur.ritem == None:
cur.ritem = node
return
else:
# 如果左右子樹都不為空，加入隊列繼續判斷
queue.append(cur.litem)
queue.append(cur.ritem)
```
## 二叉樹的遍歷
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次，我們把這種對所有節點的訪問稱為遍歷（traversal）。那么樹的兩種重要的遍歷模式是深度優先遍歷和廣度優先遍歷,深度優先一般用遞歸，廣度優先一般用隊列。一般情況下能用遞歸實現的算法大部分也能用堆棧來實現。
### 深度優先遍歷
對于一顆二叉樹，深度優先搜索(Depth First Search)是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。
<br>那么深度遍歷有重要的三種方法。這三種方式常被用于訪問樹的節點，它們之間的不同在于訪問每個節點的次序不同。這三種遍歷分別叫做先序遍歷（preorder），中序遍歷（inorder）和后序遍歷（postorder）。我們來給出它們的詳細定義，然后舉例看看它們的應用。
- 先序遍歷 在先序遍歷中，我們先訪問根節點，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹
根節點->左子樹->右子樹
```
def preorder(self, node):
"""遞歸實現先序遍歷"""
if node == None:
return
print(node.item, end=" ")
self.preorder(node.litem)
self.preorder(node.ritem)
```
- 中序遍歷 在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節點，最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節點->右子樹
```
def inorder(self, node):
"""遞歸實中序遍歷"""
if node == None:
return
self.inorder(node.litem)
print(node.item, end=" ")
self.inorder(node.ritem)
```
- 后序遍歷 在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節點
左子樹->右子樹->根節點
```
def postorder(self, node):
"""遞歸實現后序遍歷"""
if node == None:
return
self.postorder(node.litem)
self.postorder(node.ritem)
print(node.item, end=" ")
```
### 廣度優先遍歷(層次遍歷)
從樹的root開始，從上到下從從左到右遍歷整個樹的節點
```
def breadth_travel(self):
"""利用隊列實現樹的層次遍歷"""
if self.root == None:
return
queue = []
queue.append(self.root)
while queue:
node = queue.pop(0)
print(node.item)
if node.litem != None:
queue.append(node.litem)
if node.ritem != None:
queue.append(node.ritem)
```
### 思考：哪兩種遍歷方式能夠唯一的確定一顆樹？？？
