树-二叉树, since 2022-05-05

作者: Mc杰夫 | 来源:发表于2022-05-05 16:42 被阅读0次

树结构在数据库设计中扮演重要作用。

基本概念：

树叶和分支节点：没有子节点的节点称为树叶，其余都是分支节点
(节点)度数degree: 一个节点的子节点个数。
层: 根的层数为0，位于k层的节点，其子节点是k+1层的元素。
高度(or深度): 树中节点的最大层数，只有根节点的树，其高度为0.
高度是从树叶往上数到目标节点。深度是从根节点往下数到目标节点。
$h_n = 1 + max(h_{children-of-n})$
$d_n = 1 + d_{n\_parent}$
满二叉树：二叉树中所有分支节点的度数为2。
满二叉树性质：树叶比分支节点多一个。
证明：从一个非空满二叉树，每次取走一个叶节点和它的母节点，并将剩余的节点相连形成新树，并对新树执行相似的过程。最终只剩下一个叶节点。证明树叶比分支节点多一个。
扩充二叉树：对已有二叉树T加入足够多的新叶节点，使T的原有节点都变为度数为2的节点，形成的新二叉树. 分为内部节点和外部节点。空树的扩充二叉树规定为空树。

扩充二叉树都是满二叉树(?)

完全二叉树：共h层，0- (h-1)层的节点数是 $2^{(h-1)}$ .如果最下一层的节点不满，则所有节点在左边连续排列，空位都在右边。此为完全二叉树。(除最下两层外，其余都是度数为2的节点。节点数为n的完全二叉树，其高度是不大于log2(n)的最大整数) 完全二叉树可自然的存入一个连续表。

二叉树的实现

二叉树可以用list实现，也可以用链表形式实现。

二叉树的List实现

(2022.05.06 Fri)
用二叉树中节点的位置计数(level numbering)作为list中的索引来保存树的节点。比如，对 $f(p)$ 做如下定义

如果 $p$ 是根节点，则 $f(p)=0$
如果 $p$ 是 $q$ 节点做的左子树，则 $f(p) = 2f(q) + 1$
如果 $p$ 是 $q$ 节点做的右子树，则 $f(p) = 2f(q) + 2$

$f(p)$ 确定了二叉树的节点在list中的索引，接下来只需把节点保存在相应的索引位置上即可。树-堆中应用了树的这种实现方式。

极简实现

(2020.12.21 Mon)

# -*- coding: utf-8 -*-
class btree:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.data = value
    def insert_left(self, value):
        self.left = btree(value) //插入的也是一个树
        return self.left
    def insert_right(self, value):
        self.right = btree(value)
        return self.right
    def show(self):
        print(self.data)
if __name__ == '__main__':
    root = btree('root')
    a = root.insert_left('a')
    c = a.insert_left('c')
    d = a.insert_right('d')
    f = d.insert_left('f')
    root.show()

Linked list实现

(2022.05.05 Thur)
一种没有Position特征的实现方式。在这种方式中，每个节点被封装为一个对象，对节点执行操作可生成树。通过节点的属性left/right/parent，该节点与其他节点相连，形成树。

class btnode:
    def __init__(self, value=None, parent=None, left=None, right=None):
        self.value = value
        self.parent = parent
        self.left = left
        self.right = right
        self.root = None
    def set_root(self, value):
        if not self.root:
            self.root = True
            self.value = value
        return self
    @property
    def is_root(self):
        if self.root:
            return True
        else:
            return False
    @property
    def is_leaf(self):
        return self.num_children > 0
    def add_left(self, value):
        if self.left:
            raise ValueError('left is not null')
        self.left = btnode(value, self)
        return self.left
    def add_right(self, value):
        if self.right:
            raise ValueError('right is not null')
        self.right = btnode(value, self)
        return self.right
    @property
    def num_children(self):
        num = 0
        if self.left:
            num += 1
        if self.right:
            num += 1
        return num
    @property
    def children(self):
        res = []
        if self.left:
            res.append(self.left)
        if self.right:
            res.append(self.right)
        return res
    @property
    def siblings(self):
        if not self.parent:
            return None
        if self.parent.left == self:
            return self.parent.right
        else:
            return self.parent.left
    @property
    def height(self):
        if self.num_children == 0:
            return 1
        else:
            return 1 + max(c.height for c in self.children)
    @property
    def depth(self):
        if self.root:
            return 0
        elif self.parent:
            return 1 + self.parent.depth

调用方式

>>> n = btnode()
>>> n = n.set_root(1000)
>>> n.is_root
True
>>> l1 = n.add_left(98)
>>> l11 = l1.add_left(198)
>>> r12 = l1.add_right(298)
>>> l121 = r12.add_left(99)
>>> l121.height
1
>>> n.height
4
>>> l121.depth
3

链表表达的复杂度分析：

add_left/add_right/set_root/is_leaf/is_root: $O(1)$
depth: $O(d_p+1)$
height: $O(n)$

另一种Linked List实现

(2022.05.19 Thur)
前面的Linked List实现方式，每个对象是一个节点，下面这种方式每个对象是树本身，而该对象中的_Node对象代表了节点。

class LinkedBinaryTree(BinaryTree):
    class _Node:
        __slots__ = '_element', '_parent', '_left', '_right'
        def __init__(self, element, parent=None, left=None, right=None):
            self._element = element
            self._parent = parent
            self._left = left
            self._right = right
    def __init__(self):
        self._root = None
        self._size = 0
    def __len__(self):
        return self._size
    def root(self):
        return self._root
    def left(self, p):
        return p._left
    def right(self, p):
        return p._right
    def num_children(self, p):
        cntr = 0
        if p._left is not None:
            cntr += 1
        if p._right is not None:
            cntr += 1
        return cntr
    def _add_root(self, e):
        if self._root is not None: raise ValueError('root exists')
        self._root = self._Node(e)
        self._size = 1
    def _add_left(self, p, e):
        if p._left is not None: raise ValueError('left exists')
        self._size += 1
        p._left = self._Node(e, p)
        return p._left
    def _add_right(self, p, e):
        if p._right is not None: raise ValueError('right exists')
        self._size += 1
        p._right = self._Node(e, p)
        return p._right
    def _replace(self, p, e):
        old = p._element
        p._element = e
        return old
    def _delete(self, p):
        if self.num_children(p) == 2: raise ValueError('2 children')
        child = p._left if p._left else p._right
        if child is not None:
            child._parent = p._parent
        if p is self.root:
            self._root = child
        else:
            parent = p._parent
            if p is parent._left:
                parent._left = child
            if p is parent._right:
                parent._right = child
        self._size -= 1
        p._parent = p
        return p._element

一般树的linked结构

(2022.06.12 Sun)
用链路结构表达二叉树，每个节点保留了左右两个字段作为指向子节点的引用。对于一般树，没有对节点数的先验限制。对于这样的树，用链路结构表达的自然方式是在每个节点中保存一个对子节点引用的容器。比的如一个节点的子树字段可以是python list，list中的每个元素是对子节点的引用。

这种实现方式的复杂度分析，其中的 $p$ 表示任意节点。len和is_empty， $O(1)$ ；root，parent，is_root，is_leaf， $O(1)$ ；children(p)， $O(c_p+1)$ ；depth(p)， $O(d_p+1)$ ；height， $O(n)$ 。

遍历(traverse): 深度优先、宽度优先

深度优先(Depth First Search, DFS)：根节点P左子节点L右子节点R，先根遍历顺序PLR，后根遍历顺序LRP，中序遍历LPR。

宽度优先(Breadth First Search, BFS)：按路径长度由近及远的访问节点，亦即按层次访问树的各层节点。用队列(Queue)实现宽度遍历。

(2020.12.21 Mon)
树的深度遍历(DFS)方法有三种，先序遍历、中序遍历和后序遍历。

一个记忆技巧：先、中、后序遍历，是针对根节点在遍历中位置来定义的，也就如果顺序是根节点-左-右，则称为先序遍历，以此类推。

先序遍历: 如果二叉树不为空，则访问根节点，然后访问左子树，最后访问右子树；否则程序退出
中序遍历: 如果二叉树不为空，则访问左子树，然后访问根节点，最后访问右子树；否则程序退出
后序遍历: 如果二叉树不为空，则访问左子树，然后访问右子树，最后访问根节点；否则程序退出

递归形式的遍历代码

# node = btree(5) 
def preorder(node):
    if node.data:
        node.show()
        if node.left:
            preorder(node.left)
        if node.right:
            preorder(node.right)
    
def inorder(node):
    if node.data:
        if node.left:
            inorder(node.left)
        node.show()
        if node.right:
            inorder(node.right)
    
def postorder(node):
    if node.left:
        postorder(node.left)
    if node.right:
        postorder(node.right)
    if node.data:
        node.show()
    
if __name__ == '__main__':
    root = btree('root')
    # some operations, insert trees
    ...
    inorder(root)
    preorder(root)
    postorder(root)

树的BFS遍历

(2020.12.22 Tues)
也就是按层遍历，需要用到queue作为工具。

class queue:
    default_capacity = 30
    def __init__(self):
        self.data = [None] * queue.default_capacity
        self.size = 0
        self.front = 0 # front index

    def enqueue(self, value):
        if self.size == len(self.data):
            self.resize(2*len(self.data))
        tail = (self.front + self.size)% len(self.data)
        self.data[tail] = value
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise Empty('queue empty.')
        ans = self.data[self.front]
        self.data[self.front] = None
        self.front = (self.front+1) % len(self.data)
        self.size -= 1
        return ans

    def resize(self, newlen):
        obs = deepcopy(self.data)
        obsind = self.front
        self.data = [None] * newlen
        for k in range(self.size):
            self.data[k] = obs[obsind]
            obsind = (obsind + 1)%len(obs)
        self.front = 0
    def is_empty(self):
        return self.size == 0

#2020.12.24
if __name__ == '__main__':
    root = btree('root')
    # some insertion operation
    ...
    q = queue()
    q.enqueue(root)
    result = []
    while q.is_empty():
        tmp = q.dequeue()
        result.append(tmp.data)
        if tmp.left:
            q.enqueue(tmp.left)
        if tmp.right:
            q.enqueue(tmp.right)
    # result is what we want

Reference

1 Goodrich and etc., Data Structures and Algorithms in Python

树-二叉树, since 2022-05-05

基本概念：

二叉树的实现

二叉树的List实现

极简实现

Linked list实现

另一种Linked List实现

一般树的linked结构

遍历(traverse): 深度优先、宽度优先

树的BFS遍历

Reference

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读