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

• 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资料结构与算法》
《大话资料结构》