Python数据结构与算法笔记（八）：数据结构——树，二叉树和AVL树

树

class Node:
    def __init__(self, name, type='dir'):
        self.name = name
        self.type = type   #"dir" or "file"
        self.children = []
        self.parent = None
        # 链式存储

    def __repr__(self):
        return self.name

class FileSystemTree:
    def __init__(self):
        self.root = Node("/")
        self.now = self.root

    def mkdir(self, name):
        # name 以 / 结尾
        if name[-1] != "/":
            name += "/"
        node = Node(name)
        self.now.children.append(node)
        node.parent = self.now

    def ls(self):
        return self.now.children

    def cd(self, name):
        # "/var/python/"
        if name[-1] != "/":
            name += "/"
        if name == "../":
            self.now = self.now.parent
            return
        for child in self.now.children:
            if child.name == name:
                self.now = child
                return
        raise ValueError("invalid dir")

tree = FileSystemTree()
tree.mkdir("var/")
tree.mkdir("bin/")
tree.mkdir("usr/")

tree.cd("bin/")
tree.mkdir("python/")

tree.cd("../")

print(tree.ls())
[var/, bin/, usr/]

二叉树

概念：
如果用列表存储，很有地方就会有空着的，浪费空间。因此采用链式存储。

from collections import deque

# 二叉树的节点
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None   # 左孩子
        self.rchild = None # 右孩子

a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")

e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f

root = e

print(root.lchild.rchild.data)
C

二叉树的遍历：

# 前序遍历：E在开头
# 先访问左子树，然后访问右子树
def pre_order(root):
    if root:
        print(root.data, end=',')
        pre_order(root.lchild)
        pre_order(root.rchild)

pre_order(root)
E,A,C,B,D,G,F,

# 中序遍历：E在中间
# 先访问左子树，然后访问自己，再访问右子树
def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data, end=',')
        in_order(root.rchild)

in_order(root)
A,B,C,D,E,G,F,

树（子树）的根在中间。

# 后序遍历
# 先递归左，然后递归右，最后打印自己
def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end=',')

post_order(root)
B,D,C,A,F,G,E,

# 层次遍历
# 一层一层来，从左至右
from collections import deque

def level_order(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0: # 只要队不空
        node = queue.popleft()
        print(node.data, end=',')
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)

level_order(root)
E,A,G,C,F,B,D,

二叉搜索树的概念：

插入：

class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)

    def insert(self, node, val):# 递归
        if not node:
            node = BiTreeNode(val)
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)
            node.lchild.parent = node
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        return node

    def insert_no_rec(self, val):# 非递归
        p = self.root
        if not p:               # 空树
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:           # 左孩子不存在
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p
                    return
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return

tree = BST([1,4,2,5,3,8,6,9,7])

tree.pre_order(tree.root)
print("")
1,4,2,3,5,8,6,7,9,

tree.in_order(tree.root)
print("")
1,2,3,4,5,6,7,8,9,

tree.post_order(tree.root)
print("")
3,2,7,6,9,8,5,4,1,

对于中序序列，左孩子树都是小的，右孩子树都是大的。所以，中序序列出来一定是由小到大排列的。

查询：

#接上面的代码
    def query(self, node, val):# 递归
        if not node:
            return None
        if node.data < val:
            return self.query(node.rchild, val)
        elif node.data > val:
            return self.query(node.lchild, val)
        else:
            return node

    def query_no_rec(self, val):# 非递归
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif p.data > val:
                p = p.lchild
            else:
                return p
        return None

print(tree.query_no_rec(4).data)
4

print(tree.query_no_rec(10))
None

删除
有以下三种情况：

不管是左孩子还是右孩子

删除根节点。此时根节点变为35,。

找左子树中最大的数，或者右子树中最小的数。这些数与节点最接近。

# 接上面的代码
    def __remove_node_1(self, node):
        # 情况1：node是叶子节点
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:  #node是它父亲的左孩子
            node.parent.lchild = None
        else:   #右孩子
            node.parent.rchild = None

    def __remove_node_21(self, node):
        # 情况2.1：node只有一个左孩子
        if not node.parent: # 根节点
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent

    def __remove_node_22(self, node):
        # 情况2.2：node只有一个右孩子
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent


    def delete(self, val):
        if self.root:   # 不是空树
            node = self.query_no_rec(val)
            if not node: # 不存在
                return False
            if not node.lchild and not node.rchild: #1. 叶子节点
                self.__remove_node_1(node)
            elif not node.rchild:       # 2.1 只有一个左孩子
                self.__remove_node_21(node)
            elif not node.lchild:       # 2.2 只有一个右孩子
                self.__remove_node_22(node)
            else:   # 3. 两个孩子都有
                min_node = node.rchild
                while min_node.lchild:
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)

tree.in_order(tree.root)
print("")
1,2,3,4,5,6,7,8,9,

tree.delete(4)
tree.in_order(tree.root)
print("")
1,2,3,5,6,7,8,9,

二叉树的搜索效率：
二叉树偏斜时，时间复杂度最差为O(n)。

AVL树

任何节点左右子树的高度差都不能超过1.
平衡因子：记录左右子树的高度差。

AVL树——插入：

沿着左边插入1.然后从1往回找，看是否是平衡树，是否是一个节点路径。只有带颜色的节点平衡可能发生变化。
相关网站：树结构图示

看2是否平衡。左1，右0.平衡往下找。

4：左边2，右边1.相差1以内，平衡。

6。左3右1。不平衡，

通过旋转，使其平衡。此时，左边的子树是平衡的。


不平衡的情况：
（同性则异，异性则同）
左左——右旋

右右——左旋

右左——右旋-左旋


左右——左旋-右旋

在插入的时候，从插入的节点到根节点，往回找。找到第一个节点的平衡因子是±2的，然后根据以上四种情况，进行旋转。

旋转实现代码：

插入实现代码：

AVL树的应用：

二叉树扩展应用——B树
AVL树是二叉树，B树是多叉树。