数据结构之树


前面提到的列表,队列,栈和链表都是线性的数据结构,数据元素之间都是一对一的关系,比如除了首尾元素外,内部的元素都有唯一的前驱和唯一的后缀。

除了线性结构外,另外一类数据结构是非线性结构,代表性的就是树,在非线性结构中,数据元素之间是一对多的关系,即前驱或者后继不是唯一的,而且还有层级之分。

利用树这种结构的例子有很多,比如生物学中的分类树,通过界门纲目科属种对生物进行分类;计算机的文件系统;HTML文档;域名体系。下图实例就是Unix文件系统的一部分

树结构的相关术语

  • 节点、边、根节点、路径、子节点、父节点、兄弟节点、子树、叶子结点、层数、高度

对于树的层数,与列表下标从0开始相似,根节点的层数为0,而树的高度就是其中节点层数的最大值

树的定义

树的定义有两种:

1.树由若干节点,以及两两连接节点的边组成,并有如下性质:

  • 其中一个节点被设定为根
  • 每个节点n(除根节点),都只连接一条来自节点p的边,p是n的父节点
  • 每个节点从根节点开始的路径是唯一的
  • 如果每个节点最多有两个子节点,这样的树称为“二叉树”,当然节点数也可以有多个,那就是多叉树。

树的第一种定义将树看作是节点和边的集合

2.树的递归定义

树是空集或者由根节点及0或多个子树构成(其中子树也是树),每个子树的根到根节点具有边相连。

树的实现

通过数据结构链表对树的第一种定义进行实现,实现树是二叉树。

#二叉树实现

class BTree(object):
    """
    二叉树类
    """
    def __init__(self, data=None, left=None, right=None):
        """
        初始化
        :param data: 数据域
        :param left: 左子树
        :param right: 右子树
        """
        self.data = data
        self.left = left
        self.right = right

    def height(self):
        """求取树的高度"""
        if self.data is None:
            return 0
        elif self.left is None and self.right is None:
            return 1
        elif self.left is None and self.right:
            return 1 + self.right.height()
        elif self.left and self.right is None:
            return 1 + self.left.height()
        else:
            return 1 + max(self.left.height(), self.right.height())

    def leaves(self):
        """叶子节点"""
        if self.data is None:
            return None
        elif self.left is None and self.right is None:
            print(self.data, end=' ')
        elif self.left is None and self.right:
            self.right.leaves()
        elif self.left and self.right is None:
            self.left.leaves()
        else:
            self.left.leaves()
            self.right.leaves()

    def insertLeft(self, newNode):
        """插入左节点"""
        if self.left == None:
            self.left = BTree(newNode)
        else:
            tmp = BTree(newNode)
            tmp.left = self.left
            self.left = tmp

    def insertRight(self, newNode):
        """插入右节点"""
        if self.right == None:
            self.right = BTree(newNode)
        else:
            tmp = BTree(newNode)
            tmp.right = self.right
            self.right = tmp

    def getLeft(self):
        return self.left

    def getRight(self):
        return self.right

    def setData(self, value):
        self.data = value

    def getData(self):
        return self.data


def test_tree():
    """测试二叉树类"""
    node1 = BTree(1)
    node2 = BTree(2)
    node3 = BTree(3)
    node4 = BTree(4)
    node5 = BTree(5)
    node6 = BTree(6)
    node7 = BTree(7)
    node8 = BTree(8)
    node9 = BTree(9)
    node10 = BTree(10)
    node11 = BTree(11)

    # 构建二叉树
    node1.left, node1.right = node2, node3
    node2.left, node2.right = node4, node5
    node3.left, node3.right = node6, node7
    node4.left, node4.right = node8, node9
    node5.left, node5.right = node10, node11

    # 指定 node1 为root节点
    tree = node1

    height = tree.height()
    print('树的高度为%s.' % height)

    print('叶子节点为:')
    tree.leaves()
    print()

测试程序的运行结果为:

树的高度为4.
叶子节点为:
8 9 10 11 6 7 

树的四种遍历

线性数据结构只有两种遍历方式,从前往后或者从后往前,而树这种数据结构有四种遍历方式,分别为:

  • 前序遍历:先访问根节点,再访问左子树,最后访问右子树
  • 中序遍历:先访问左子树,再访问根节点,最后访问右子树
  • 后序遍历:先访问左子树,再访问右子树,最后访问根节点
  • 层序遍历:按树的层次进行遍历,第0层、第1层、……

举例:

对上图所示的二叉树进行遍历,结果分别为:

  • 前序遍历:[1, 2, 4, 5, 3, 6, 7]
  • 中序遍历:[4, 2, 5, 1, 6, 3, 7]
  • 后序遍历:[4, 5, 2, 6, 7, 3, 1]
  • 层序遍历:[1, 2, 3, 4, 5, 6, 7]

实现代码:

"""可以直接在前面的二叉树类中加入四种遍历方法"""
    def preorder(self):
        """前序遍历"""
        if self.data:
            print(self.data, end=' ')
        if self.left:
            self.left.preorder()
        if self.right:
            self.right.preorder()

    def inorder(self):
        """中序遍历"""
        if self.left:
            self.left.inorder()
        if self.data:
            print(self.data, end=' ')
        if self.right:
            self.right.inorder()

    def postorder(self):
        """后序遍历"""
        if self.right:
            self.right.postorder()
        if self.left:
            self.left.postorder()
        if self.data:
            print(self.data, end=' ')

    def levelorder(self):
        """层序遍历"""
        if not self:
            return
        queue = []
        current_line = 0
        queue.append([current_line, self])
        while len(queue) > 0:
            line, node = queue.pop(0)
            if line != current_line:
                print()
                current_line = line
            print(node.data, end=' ')

            if node.left:
                queue.append([line+1, node.left])
            if node.right:
                queue.append([line+1, node.right])

直接在测试函数中调用tree的四种遍历方法,就可以测试程序的正确性。

完整版代码已上传github,具体地址可以点击主页右上角的Fork me


文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
虚拟存储管理(一) 虚拟存储管理(一)
虚拟存储的需求前面的物理内存管理都基于一个基本要求:执行指令必须在物理内存中。这使得程序的大小被限制在物理内存的大小以内。实际上,在程序中,并不是需要将整个程序放到内存中,比如:程序中处理异常和错误条件的代码;数组、链表和表通常分配比实际所
2020-08-04
下一篇 
物理内存管理(二) 物理内存管理(二)
上一篇文章详细讲了物理内存的连续分配,这篇文章讲一下物理内存的非连续分配 非连续内存分配的需求背景连续分配的缺点: 分配给程序的物理内存必须连续 存在外碎片和内碎片 内存分配的动态修改困难 内存利用率较低 非连续分配的设计目标:提高
2020-07-30
  目录