树、堆、集合

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 的构造，每次将权值最小的两颗二叉树进行合并，

C、集合

并查集

性能提升