树和链式存储

老码农空杯修行记 2019-03-20

274

树的存储方式一般有两种

顺序存储：比如用数组存储，看下面的

特征：

左儿子：2i + 1
右儿子：2i + 2

优点：

查找子节点比较容易
适合存储完全二叉平衡树

缺点：

找父节点困难，为此需要加入，为此需要加入额外的存储空间来存储父节点
空节点占用空间，浪费内存，比如上面我们用#代替了空节点

链式存储：类似链表的形式存储

特征

既然是链表形式存储，自然额外需要两个整形的空间存储两个子节点，甚至还得加一个整形来存储父节点，但是除此之外不会再有别的空间的浪费

一般呢顺序存储的情况很少，所以下面以链式存储为例子看看如何实现，例子是一家公司的面试题，给定序列如下：

要求：

语言不限
构建如下的树结构

前序遍历
中序遍历
后序遍历
反转输出如下的树

我们采用python来实现，为啥选python，若是用伪代码来表达，似乎有点太笼统，而python更接近伪代码，又不像c语言那么复杂，实现起来更简单。好下面我来定义节点：

class Node(object):
    """
    树的节点
    data:  存储数据
    left:  存储左子树
    right: 存储右子树
    """
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

链式存储类定义

class ChainBinaryTree(object):
    """
    链式二叉树: 将给定序列按照原来序列中的顺序存储到树中, 从上到下从左到右依次存储
    特     征: 序列中的从0开始,后面的 2n+1 存储到左子树, 2n+2 存储到右子树
    """
    def __init__(self):
        self.tree = None

下面我们来看如何将这个给定序列放入到树中，我们先手动标注一下这个树，看看序列中元素与树中的对应关系

总结：假设父节点的索引为i，那么它的

左儿子的索引是：2i + 1
右儿子的索引是: 2i + 2

那么写出创建一个节点的基本逻辑如下：

    node = Node(arr[i])
    node.left = arr[2*i + 1]
    node.right = arr[2*i + 2]

为了创建每一个节点的子节点，我们需要递归，下面我们实现save方法来存储这个序列

    def save(self, arr):
        """
        数组存储到链式二叉树中
        :param arr: 输入序列
        :return:
        """
        self.tree = self._save(arr, len(arr), 0)


    def _save(self, arr, size, pos):
        """
        :param arr: 输入序列
        :param size: 输入序列长度, 保证序列不越界
        :param pos: 当前节点的序号
        :return: 返回节点
        """


        if pos < size:
            # 存储节点
            node = Node(arr[pos])


            # 序列中当前节点的 2n + 1 存储到左子树
            node.left = self._save(arr, size, pos * 2 + 1)


            # 序列中当前节点的 2n + 1 存储到右子树
            node.right = self._save(arr, size, pos * 2 + 2)


            # 返回当前节点
            return node
        return None

树的遍历

先序遍历：Root -> Left -> Right

    def pre_travel(self):
        arr = list()
        self._pre_travel(self.tree, arr)
        return arr


    def _pre_travel(self, tr, arr):
        """
        先序遍历: 跟节点 ----> 左子树 ----> 右子树
        :param tr:  输入节点
        :param arr: 用于存储输出节点
        :return:
        """
        if tr is None:
            return


        arr.append(tr.data)
        self._pre_travel(tr.left, arr)
        self._pre_travel(tr.right, arr)

中序遍历：Left -> Root -> Right

    def mid_travel(self):
        arr = list()
        self._mid_travel(self.tree, arr)
        return arr


    def _mid_travel(self, tr, arr):
        """
        中序遍历:    左子树 ---> 跟 ---> 右子树
        :param tr:  输入节点
        :param arr: 保存输出节点
        :return:
        """
        if tr is None:
            return
        self._mid_travel(tr.left, arr)
        arr.append(tr.data)
        self._mid_travel(tr.right, arr)

后序遍历：Left -> Right -> Root

    def post_travel(self):
        arr = list()
        self._post_travel(self.tree, arr)
        return arr


    def _post_travel(self, tr, arr):
        """
        后序遍历:    左子树 ---> 右子树 ---> 跟
        :param tr:  输入节点
        :param arr: 保存输出节点
        :return:
        """
        if tr is None:
            return
        self._post_travel(tr.left, arr)
        self._post_travel(tr.right, arr)
        arr.append(tr.data)

反转：比较简单就是左右节点交换，递归即可完成

    def lr_reverse(self):
        self._lr_reverse(self.tree)


    def _lr_reverse(self, tr):
        """
        翻转左右子树
        :param tr:
        :return:
        """
        if tr:
            tr.left, tr.right = tr.right, tr.left
            self._lr_reverse(tr.left)
            self._lr_reverse(tr.right)

下面我们测试一下这些接口

if __name__ == "__main__":
    arr  = [3, 8, 9, 10, 1, 2, 7, 22, 34, 10, 2]
    chain_tree = ChainBinaryTree()


    print("src   array is       :", arr)
    chain_tree.save(arr)
    print("chain tree size      :", chain_tree.len())
    print("chain tree pre       :", chain_tree.pre_travel())
    print("chain tree mid       :", chain_tree.mid_travel())
    print("chain tree post      :", chain_tree.post_travel())
    print("---------------------------------------------------")
    print("array is             :", chain_tree.array())
    print("---------------------------------------------------")
    chain_tree.lr_reverse()
    print("chain tree reverse pre       :", chain_tree.pre_travel())
    print("chain tree reverse mid       :", chain_tree.mid_travel())
    print("chain tree reverse post      :", chain_tree.post_travel())

打印输出如下

src   array is       : [3, 8, 9, 10, 1, 2, 7, 22, 34, 10, 2]
chain tree size      : 11
chain tree pre       : [3, 8, 10, 22, 34, 1, 10, 2, 9, 2, 7]
chain tree mid       : [22, 10, 34, 8, 10, 1, 2, 3, 2, 9, 7]
chain tree post      : [22, 34, 10, 10, 2, 1, 8, 2, 7, 9, 3]
---------------------------------------------------
array is             : [3, 8, 9, 10, 1, 2, 7, 22, 34, 10, 2]
---------------------------------------------------
chain tree reverse pre       : [3, 9, 7, 2, 8, 1, 2, 10, 10, 34, 22]
chain tree reverse mid       : [7, 9, 2, 3, 2, 1, 10, 8, 34, 10, 22]
chain tree reverse post      : [7, 2, 9, 2, 10, 1, 34, 22, 10, 8, 3]

详细源代码参见：https://github.com/DingKingTim/dstructure_algorithm/tree/master/tree/chain_btree

数据库

文章转载自老码农空杯修行记，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

树和链式存储

评论