A、树
事物之间的层次关系，例如文件管理，家谱，图书信息等
二叉树(binary tree)
二叉树的遍历
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Queue(object): # 队列结构
def __init__(self): # 使用list模拟队列
self.items = []
def isEmpty(self):
return len(self.items) == 0
def Enqueue(self, item): # 入队
self.items.append(item)
def Dequeue(self): # 出队
return self.items.pop(0)
def Getlength(self): # 获取队列长度
return len(self.items)
def printQue(self):
for item in self.items:
print(item)
class stack(object): # 堆栈,后进先出
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[-1]
def size(self):
return len(self.items)
# 二叉树的遍历，先序、中序、后序、层次
def printTree(head): # 先序遍历,递归算法
if head:
print(head.val) # 头节点
printTree(head.left) # 遍历左子树
printTree(head.right) # 遍历右子树
def printNode(head): # 层序遍历,加入队列
if not head:
return False
q = Queue()
q.Enqueue(head)
while (q.isEmpty() == False):
t=q.Dequeue()
print(t.val)
if t.left:
q.Enqueue(t.left)
if t.right:
q.Enqueue(t.right)
def printStack(head): #采用非递归遍历，二叉树（采用堆栈,中序为例）
p=head
s=stack()
while(s.isEmpty()==False or p):
while(p): #压入左子树
s.push(p)
p=p.left
if (s.isEmpty()==False):
t=s.pop()
print(t.val)
p=t.right
def getDepth(head):
if not head:
return 0
maxleft, maxright = 1, 1
maxleft += getDepth(head.left) # 遍历左子树
maxright += getDepth(head.right) # 遍历右子树
return max(maxleft, maxright)
root = TreeNode(1)
root.left = TreeNode(1)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
printStack(root)
二叉搜索树
搜索树的特征：
二叉搜索数的特征
Find 函数（与树的高度与结构有关）
def find(x,head): #查找效率取决于树高 尾递归方式
if not head:
return False
if x>head.val:
return find(x,head.right)
elif x<head.val:
return find(x,head.left)
else:
return head
def Find(x,head): #非递归方式,查找效率取决于树高
while(head):
if x>head.val:
head=head.right
elif x<head.val:
head=head.left
else:
return head
def Findmin(head): #最小值的查找
if not head:
return False
while(head.left):
head=head.left
return head
def Findmax(head): 最大值的查找
if not head:
return False
while(head.right):
head=head.right
return head
def insert(item,head): #插入
if not head:
head=TreeNode(item)
elif item<head.val:
head.left=insert(item,head.left)
elif item>head.val:
head.right=insert(item,head.right)
return head
def delete(item,head): #删除
if not head:
print('ERROR')
elif item>head.val:
head.right=delete(item,head.right)
elif item<head.val:
head.left=delete(item.head.left)
else:
if head.left and head.right:
temp=Findmin(head.right)
head.val=temp.val
head.riht=delete(head.val,head.right)
elif head.left==None:
head=head.right
elif head.right==None:
head=head.left
return head
平衡二叉树
不同搜索树的结构，影响其平均查找长度ASL，衡量查找效率，高度为logN；
平衡二叉树
平衡二叉树的调整：
右单旋
image.png
image.png
应用Sample
多项式的运算
B、堆
优先队列，按照元素的优先权而非元素的进入队列的先后顺序；
完全二叉树进行存储，且根节点为以它为跟的子树的最小或最大值
Huffman Tree
Huffman Tree 的构造，每次将权值最小的两颗二叉树进行合并，
