[数据结构与算法]python数据结构之树

??上一节我们学习了数据结构里面的各种排序算法，今天，我们接着学习数据结构中又一重要的结构：树，对往期内容感兴趣的小伙伴可以参考下面内容👇:

• python数据类型: python数据结构之数据类型.
• python的输入输出: python数据结构之输入输出、控制和异常.
• python数据结构之面向对象: python数据结构之面向对象.
• python数据结构之算法分析: python数据结构之算法分析.
• python数据结构之栈、队列和双端队列: python数据结构之栈、队列和双端队列.
• python数据结构之递归: python数据结构之递归.
• python数据结构之搜索: python数据结构之搜索.
• python数据结构之排序: python数据结构之排序.

🌵数据结构中所说的‘树’，一般都是指二叉树，许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

1.初识树

树结构在我们生活中很常见，我们举一些例子：

从树的顶部开始，沿着由椭圆和箭头构成的路径，一直到底部。一个节点的所有子节点都与另一个节点的所有子节点无关，叶子节点都是独一无二。

2.树的术语及定义

2.1 树的术语

先介绍树的一些术语：

• 节点：节点是树的基础部分。它可以有自己的名字，我们称作“键”。节点也可以带有附加信息，我们称作“有效载荷”。有效载荷信息对于很多树算法来说不是重点，但它常常在使用树的应用中很重要。
• 边：边是树的另一个基础部分。两个节点通过一条边相连，表示它们之间存在关系。除了根节点以外，其他每个节点都仅有一条入边，出边则可能有多条。
• 根节点：根节点是树中唯一没有入边的节点（树的启始节点）
• 路径：路径是由边连接的有序节点列表。比如，哺乳纲→食肉目→猫科→猫属
• 子节点：一个节点通过出边与子节点相连。
• 父节点 ：一个节点是其所有子节点的父节点。
• 兄弟节点 ：具有同一父节点的节点互称为兄弟节点。
• 子树：一个父节点及其所有后代的节点和边构成一棵子树。
• 叶子节点 ：叶子节点没有子节点。
• 层数：节点 n 的层数是从根节点到 n 的唯一路径长度。
• 高度 ：树的高度是其中节点层数的最大值。

2.2 树的定义

树的定义有两种：

第一种：

• 有一个根节
• 除根节点外，其他每个节点都与其唯一的父节点相连
• 从根节点到其他每个节点都有且仅有一条路径
• 如果每个节点最多有两个子节点，我们就称这样的树为二叉树

第二种：
一棵树要么为空，要么由一个根节点和零棵或多棵子树构成，子树本身也是一棵树。 每棵子树的根节点通过一条边连到父树的根节点。从树的递归定义可知，图中的树至少有 4 个节点，因为三角形代表的子树必定有一个根节点。这棵树或许有更多 的节点，但必须更深入地查看子树后才能确定。

3. 树的实现

3.1 列表实现法

树的根节点是 myTree[0]，左子树是 myTree[1]，右子树是 myTree[2]
表示方法如下：

#树
mytree=['a',['b',['d',[],[]],['e',[],[]]],['c',['f',[],[]],[]]]
#左子树
mytree[1]
#右子树
mytree[2]

创建树的函数

def binarytree(r):#创建一颗以r为根节点的树
    return [r,[],[]]
def insertleftree(root,newbr):#向左节点插入一棵树
    t=root.pop(1)
    if len(t)>1:
        root.insert(1,[newbr,t,[]])
    else:
        root.insert(1,[newbr,[],[]])
    return root
def insertrighttree(root,newbr):#向右节点插入一颗树
    t=root.pop(2)
    if len(t)>1:
        root.insert(2,[t,newbr,[]])
    else:
        root.insert(2,[t,newbr,[]])
    return root
def getlefttree(r):#获取左子树
    return r[1]
def getrighttree(r):#获取右子树
    return r[2]

3.2 面向对象法

利用节点与引用。我们将定义一个类，其中有根节点和左右子树的属性。 这种表示法遵循面向对象编程范式，结构如下：

树的实现

class binarytree2:
        def __init__(self,key):
            self.root=key
            self.left=None
            self.right=None
        def insertleft(self,nbran):#插入左节点
            if self.left ==None:
                self.left=binarytree2(nbran)
            else:
                t=binarytree2(nbran)
                t.left=self.left
                self.left=t
        def insertright(self,nbran):#插入右节点
            if self.right==None:
                self.right=binarytree2(nbran)
            else:
                t=binarytree2(nbran)
                t.right=self.right
                self.right=t
        def getrighttree(self):#获取右子树
            return self.right
        def getlefttree(self):#获取左子树
            return self.left
        def gettreeroot(self):#获取根节点
            return self.root

4. 二叉树的应用

4.1 解析树

树的实现已经齐全了，现在来看看如何用树解决一些实际问题。这里介绍解析树，可以用它 来表示现实世界中像句子或数学表达式这样的构造。

构建解析树的第一步是将表达式字符串拆分成标记列表。需要考虑 4 种标记：左括号、右括号、运算符和操作数。我们知道，左括号代表新表达式的起点，所以应该创建一棵对应该表达式的新树。反之，遇到右括号则意味着到达该表达式的终点。我们也知道，操作数既是叶子节点，也是其运算符的子节点。此外，每个运算符都有左右子节点。规则如下：

• 如果当前标记是(，就为当前节点添加一个左子节点，并下沉至该子节点；
• 如果当前标记在列表[’+’, ‘-’, ‘/’, ‘*’]中，就将当前节点的值设为当前标记对应的运算符；为当前节点添加一个右子节点，并下沉至该子节点；
• 如果当前标记是数字，就将当前节点的值设为这个数并返回至父节点；
• 如果当前标记是)，就跳到当前节点的父节点。

解析树实现方式

rom pythonds.basic import Stack
from pythonds.trees import BinaryTree
def buildParseTree(teststring):#解析树创建
    str=teststring.split()#将字符串拆分
    pstack=Stack()#创建一个栈，方便访问树节点
    etree=BinaryTree('')#创建树
    pstack.push(etree) #将树压入栈中
    currenttree = etree 
    for i in str: #依次判断每个字符所属情况
        if i == '(': 
            currenttree.insertLeft('') 
            pstack.push(currenttree) 
            currenttree = currenttree.getLeftChild()
        elif i in ['+','-','/','*']:#是运算符，创建右节点
            currenttree.setRootVal(i)
            currenttree.insertRight('')
            pstack.push(currenttree)
            currenttree=currenttree.getRightChild()
        elif i not in ['+','-','/','*',')']:#是数字设置该节点的值
            currenttree.setRootVal(eval(i))
            currenttree=pstack.pop()
        elif i ==')':
            currenttree = pstack.pop() 
        else:
             raise ValueError("Unknown Operator: " + i) 
    return etree

可通过如下调用：

4.2 树的遍历

树是创建好了，可是怎么遍历树呢？按节点的访问方式分为 3 种。我们将对所有节点的访问称为“遍历”，共有 3 种遍历方式，分别为前序遍历、中序遍历和后序遍历。

• 前序遍历：在前序遍历中，先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
• 中序遍历：在中序遍历中，先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
• 后序遍历：在后序遍历中，先递归地后序遍历右子树，然后递归地后序遍历左子树，最后访问根节。

三种遍历方式

#前序遍历
def preorder(tree): 
    if tree: 
        print(tree.getRootVal()) 
        preorder(tree.getLeftChild()) 
        preorder(tree.getRightChild())

#中序遍历
def inorder(tree): 
    if tree != None: 
        inorder(tree.getLeftChild()) 
        print(tree.getRootVal()) 
        inorder(tree.getRightChild())


#后序遍历
def postorder(tree): 
    if tree != None: 
        inorder(tree.getLeftChild())  
        inorder(tree.getRightChild())
        print(tree.getRootVal())

效果如下：

5. 参考书籍

《python数据结构与算法》
《大话数据结构》