数据结构与算法-06树及二叉树

树和二叉树

完全二叉树: 除了最下层,每一层都满了
满二叉树: 每一层都满了
平衡二叉树: 任意两个节点的高度差不大于1
排序二叉树:

链式存储

常见应用场景

1. xml/html解析
2. 路由协议
3. mysql数据库索引
4. 文件系统结构

二叉树

1. 在二叉树的第i层上至多有2^(i-1)个结点
2. 深度为k的二叉树至多有2^k-1个结点
3. 对于任意一颗二叉树, 如果其叶结点数为N, 则度数为2的节点总数为N+1
4. 具有n个节点的完全二叉树的深度必为log2(n+1)
5. 对于完全二叉树, i节点的左孩子变化为2i, 右孩子为2i+1

二叉树的节点表示和树的创建

节点

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.lchild = lchild
        self.rchild = rchild

树

class Tree(object):
    def __init__(self, root=None):
        self.root = root
        
    def add(self, item):
        node = Node(item)
        if self.root is None
            self.root = node
            return
        else:
        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)
                
    # 广度优先遍历
    def breadth_travel(self):
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queuq.pop(0)
            print(cur_node.elem)
            if cur_node.lchild is not None:
                quequ.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(rchild)
                
    # 先序遍历
    def preorder(self, node):
        if node is None:
            return
        print(node.elem)
        self.preorder(node.lchild)
        self.preorder(node.rchild)
        
    # 中序遍历
    def inorder(self, node):
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem)
        self.inorder(node.rchild)
        
    # 后序遍历
    def postorder(self, node):
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(self.elem)

根据 先序遍历+中序遍历 或 后序+中序 推导出一颗树

1. 先从先序/后序中找出root节点

2. 在中序中找到root节点 分成两半

3. 先序中 安装中序中的两半 分开

4. 左右子树分别重复前三步操作