目錄:
1.二叉樹(shù)的基本概念
2.二叉樹(shù)的性質(zhì)
3.二叉樹(shù)的創(chuàng)建
4.二叉樹(shù)的遍歷
1.二叉樹(shù)的基本概念
二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)瓜富，通常子樹(shù)被稱(chēng)作“左子樹(shù)”(left subtree)和"右子樹(shù)"(right tree)
2.二叉樹(shù)的性質(zhì)
1. 在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>0)
2.深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)(k>0)
3.對(duì)于任意一棵二叉樹(shù)氏仗，如果其葉結(jié)點(diǎn)數(shù)位N0粱挡，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2馍驯，則N0=N2+1
4.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為log2(n+1)
5.對(duì)完全二叉樹(shù)啊鸭，若從上之下纲酗，從左至右編號(hào)窝趣，則編號(hào)為i的結(jié)點(diǎn)誉裆，其左孩子編號(hào)必為2i推正，其右孩子編號(hào)必為2i+1恍涂；其雙親編號(hào)必為i/2
3.二叉樹(shù)的創(chuàng)建
3.1結(jié)點(diǎn)的創(chuàng)建
通過(guò)使用Node類(lèi)中定義三個(gè)屬性，分別為elem本身的值植榕，還有l(wèi)child左孩子和rchild右孩子
# 樹(shù)結(jié)點(diǎn)的創(chuàng)建
class Node(object):
def __init__(self,item):
self.elem = item
self.lchild = None
self.rchild = None
3.2二叉樹(shù)的創(chuàng)建
樹(shù)的創(chuàng)建再沧，創(chuàng)建一個(gè)樹(shù)類(lèi)，并給一個(gè)root根結(jié)點(diǎn)尊残，一開(kāi)始是空的炒瘸，隨后添加結(jié)點(diǎn)
# 樹(shù)類(lèi)的創(chuàng)建
class Tree(object):
def __init__(self):
self.root = None
# 為樹(shù)添加節(jié)點(diǎn)
def add(self, item):
node = Node(item)
# 如果樹(shù)是空的，則對(duì)根節(jié)點(diǎn)賦值
if self.root is None:
self.root = node
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
4.二叉樹(shù)的遍歷
樹(shù)的遍歷是樹(shù)的一種重要的運(yùn)算寝衫。所謂遍歷是指對(duì)樹(shù)中所有結(jié)點(diǎn)的信息的訪問(wèn)顷扩，即依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)訪問(wèn)
一次且僅訪問(wèn)一次，我們把這種對(duì)所有節(jié)點(diǎn)的訪問(wèn)稱(chēng)為遍歷（traversal）慰毅。那么樹(shù)的兩種重要的遍歷模式
是深度優(yōu)先遍歷和廣度優(yōu)先遍歷,深度優(yōu)先一般用遞歸隘截，廣度優(yōu)先一般用隊(duì)列。一般情況下能用遞歸實(shí)現(xiàn)的
算法大部分也能用堆棧來(lái)實(shí)現(xiàn)。
4.1 廣度優(yōu)先遍歷
從樹(shù)的root開(kāi)始婶芭，從上到下從從左到右遍歷整個(gè)樹(shù)的節(jié)點(diǎn)
廣度優(yōu)先遍歷.jpg
# 廣度遍歷
def breadth_travel(self):
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem,end=' ')
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
4.2 深度優(yōu)先遍歷
對(duì)于一顆二叉樹(shù)东臀，深度優(yōu)先搜索(Depth First Search)是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支雕擂。那么深度遍歷有重要的三種方法啡邑。這三種方式常被用于訪問(wèn)樹(shù)的節(jié)點(diǎn)，它們之間的不同在于訪問(wèn)每個(gè)節(jié)點(diǎn)的次序不同井赌。這三種遍歷分別叫做先序遍歷（preorder）谤逼，中序遍歷（inorder）和后序遍歷（postorder）。我們來(lái)給出它們的詳細(xì)定義仇穗，然后舉例看看它們的應(yīng)用流部。
先序遍歷
先序遍歷.jpg
# 先序遍歷
def preorder(self,node):
if node is None:
return
print(node.elem,end=' ')
self.preorder(node.lchild)
self.preorder(node.rchild)
中序遍歷
中序遍歷.jpg
# 中序遍歷
def inorder(self,node):
if node is None:
return
self.inorder(node.lchild)
print(node.elem,end=' ')
self.inorder(node.rchild)
后序遍歷
后序遍歷.jpg
# 后序遍歷
def postorder(self,node):
if node is None:
return
self.postorder(node.lchild)
self.postorder(node.rchild)
print(node.elem,end=' ')
4.3 結(jié)果演示
if __name__ == "__main__":
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.add(8)
tree.add(9)
tree.breadth_travel()
print(' ')
tree.preorder(tree.root)
print(' ')
tree.inorder(tree.root)
print(' ')
tree.postorder(tree.root)
# 運(yùn)行結(jié)果
0 1 2 3 4 5 6 7 8 9
0 1 3 7 8 4 9 2 5 6
7 3 8 1 9 4 0 5 2 6
7 8 3 9 4 1 5 6 2 0
