一,樹
E為根節點,BCD互稱為兄弟節點,G、H、I、J、K、L互稱為葉子節點(沒有子節點)
樹的高度,深度,層數.
高度從下往上數(0開始),深度從上往下數(0開始).
二,二叉樹
2為滿二叉樹,二叉樹中除了葉子結點，每個結點的度都為 2.
3為完全二叉樹,如果二叉樹中除去最後一層節點為滿二叉樹，且最後一層的結點依次從左到右分布
# 實作一個二叉樹
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.nexts = []
root_node = TreeNode(1)
node_2 = TreeNode(2)
node_3 = TreeNode(3)
node_4 = TreeNode(4)
node_5 = TreeNode(5)
node_6 = TreeNode(6)
node_7 = TreeNode(7)
node_8 = TreeNode(8)
node_9 = TreeNode(9)
node_10 = TreeNode(10)
def littleTree(root, left, right):
root.left = left
root.right = right
if root.left:
root.nexts.append(root.left)
if root.right:
root.nexts.append(root.right)
# print(root.left)
# print(root.right)
# print(root.nexts)
littleTree(root_node, node_2, node_3)
littleTree(node_2, node_4, node_5)
littleTree(node_5, node_10, None)
print('===root_node:', root_node.left)
print('===root_node:', root_node.right)
print('===root_node:', root_node.nexts)
print('===root_node.left.left:', root_node.left.left)
print('===root_node.left.right:', root_node.left.right)
print('===root_node.left.nexts:', root_node.left.nexts)
三,存儲二叉樹
3.1鍊式存儲
大部分二叉樹采用這種結果存儲.
每個節點有三個字段，其中一個存儲資料，另外兩個是指向左右子節的指針.
3.2順序存儲
根節點存儲在i=1,左子節點存儲在2*i,右子節點存儲在2*i+1
由上可看出,對于完全二叉樹,順序存儲相比鍊式存儲節約空間,其他的話就浪費空間了.
四,二叉樹周遊
4.1前序周遊
對樹中的任意節點,先列印節點,在列印左子樹,最後列印右子樹.
對于根節點開始：
先周遊根節點；
随後遞歸地周遊左子樹；
最後遞歸地周遊右子樹。
4.2中序周遊
對樹中的任意節點,先列印左子樹,在列印節點,最後列印右子樹．
先遞歸地周遊左子樹；
随後周遊根節點；
最後遞歸地周遊右子樹。
4.3後序周遊
對樹中的任意節點,先列印左子樹,在列印右子樹,最後列印節點．
先遞歸地周遊左子樹；
最後遞歸地周遊右子樹。
随後周遊根節點；
二叉樹前序周遊的順序為：
二叉樹中序周遊的順序為：
前序周遊的遞推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序周遊的遞推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
後序周遊的遞推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
可看出每個節點最多會被通路兩次，是以周遊操作的時間複雜度，跟節點的個數n成正比,時間複雜度是O(n).
例1:二叉樹的建立和周遊
class BTNode(object):
def __init__(self, key=None, lchild=None, rchild=None):
self.key = key
print('self.key',self.key)
self.lchild = lchild
print('self.lchild',self.lchild)
self.rchild = rchild
print('self.rchild',self.rchild)
class BiTree(object):
def __init__(self, data_list):
#初始化即将傳入的清單的疊代器
self.it = iter(data_list)
print('self.it',self.it)
def createBiTree(self, bt=None):
try:
#步進擷取下一個元素
next_data = next(self.it)
print('next_data=',next_data)
#如果目前清單元素為'#', 則認為其為 None
if next_data is "#":
bt = None
else:
bt = BTNode(next_data)
bt.lchild = self.createBiTree(bt.lchild)
bt.rchild = self.createBiTree(bt.rchild)
except Exception as e:
print(e)
return bt
#先序周遊函數
def preOrderTrave(self, bt):
if bt is not None:
print(bt.key, end=" ")
self.preOrderTrave(bt.lchild)
self.preOrderTrave(bt.rchild)
#中序周遊函數
def inOrderTrave(self, bt):
if bt is not None:
self.inOrderTrave(bt.lchild)
print(bt.key, end=" ")
self.inOrderTrave(bt.rchild)
#後序周遊函數
def postOrderTrave(self, bt):
if bt is not None:
self.postOrderTrave(bt.lchild)
self.postOrderTrave(bt.rchild)
print(bt.key, end=" ")
#綜合列印
def printTrave(self, bt):
print("先序周遊: ", end="")
self.preOrderTrave(bt)
print('\n')
print("中序周遊: ", end="")
self.inOrderTrave(bt)
print('\n')
print("後序周遊: ", end="")
self.postOrderTrave(bt)
print('\n')
# data = input("Please input the node value: ")
# data_list = list(data)
data_list=['a', 'b', 'd', '#', 'g', '#', '#', 'c', 'e', '#', '#', 'f', 'h', '#', '#', '#']
print(data_list)
#建構二叉樹
btree = BiTree(data_list)
root = btree.createBiTree()
btree.printTrave(root)
例2:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
class BTNode(object):
def __init__(self, key=None, lchild=None, rchild=None):
self.key = key
print('self.key',self.key)
self.lchild = lchild
print('self.lchild',self.lchild)
self.rchild = rchild
print('self.rchild',self.rchild)
class BiTree(object):
def __init__(self, data_list):
#初始化即将傳入的清單的疊代器
self.it = iter(data_list)
print('self.it',self.it)
def createBiTree(self, bt=None):
try:
#步進擷取下一個元素
next_data = next(self.it)
print('next_data=',next_data)
#如果目前清單元素為'#', 則認為其為 None
if next_data is "#":
bt = None
else:
bt = BTNode(next_data)
bt.lchild = self.createBiTree(bt.lchild)
bt.rchild = self.createBiTree(bt.rchild)
except Exception as e:
print(e)
return bt
#先序周遊函數
def preOrderTrave(self, bt):
if bt is not None:
print(bt.key, end=" ")
self.preOrderTrave(bt.lchild)
self.preOrderTrave(bt.rchild)
#中序周遊函數
def inOrderTrave(self, bt):
if bt is not None:
self.inOrderTrave(bt.lchild)
print(bt.key, end=" ")
self.inOrderTrave(bt.rchild)
#後序周遊函數
def postOrderTrave(self, bt):
if bt is not None:
self.postOrderTrave(bt.lchild)
self.postOrderTrave(bt.rchild)
print(bt.key, end=" ")
#綜合列印
def printTrave(self, bt):
print("先序周遊: ", end="")
self.preOrderTrave(bt)
print('\n')
print("中序周遊: ", end="")
self.inOrderTrave(bt)
print('\n')
print("後序周遊: ", end="")
self.postOrderTrave(bt)
print('\n')
def TreeDepth(self, pRoot):
# write code here
if pRoot == None:
return 0
return max(self.TreeDepth(pRoot.lchild), self.TreeDepth(pRoot.rchild)) + 1
# data = input("Please input the node value: ")
# data_list = list(data)
# data_list=['a', 'b', 'd', '#', 'g', '#', '#', 'c', 'e', '#', '#', 'f', 'h', '#', '#', '#']
data_list=[3,9,'#','#',20,15,'#','#',7,'#','#']
print(data_list)
#建構二叉樹
btree = BiTree(data_list)
root = btree.createBiTree()
btree.printTrave(root)
res=btree.TreeDepth(root)
print('res',res)
五,二叉查找樹
其支援動态資料集合的快速插入、删除、查找操作.
插入、删除、查找操作的時間複雜度也比較穩定，是 O(logn).
二叉查找樹要求，在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值.
示例如下:
5.1 二叉查找樹的查找操作
首先，我們看如何在二叉查找樹中查找一個節點。我們先取根節點，如果等于就傳回,根節點大的話就往左子樹查找,否則往右子樹查找.
5.2 二叉查找樹的插入操作
新插入的資料一般在葉子節點,從根節點開始,比較插入資料和節點的大小關系.
如果插入的資料比節點資料大,并且節點的右子樹為空,就将新資料插入到右子樹空的位置,如果不為空就繼續遞歸周遊右子樹,查找插入位置.插入資料比節點資料小也是同理.
5.3 二叉查找樹的删除操作
分三種情況:
1.例如55,沒有子節點,隻需要将父節點中,指向要删除子節點的指針置為null.
2.例如13,隻有左子節點或者右子節點,我們隻需要更新父節點中指針的指向,16的指針指向15.
3,例如18,有兩個節點,需要找到這個節點的右子樹最小節點19,把它替換到要删除的節點上,然後再删除這個最小節點19.