树1,用代码实现树--数据结构

一、如何用代码实现一个二叉树?

参考Trees and Tree Algorithms

1.1、通过嵌套列表实现树

在列表实现数时,我们将存储根节点的值作为列表得到第一个元素。列表的第二个元素是一个表示其左子树的列表,第三个元素是表示其右子树的另一个列表。例子:

树1,用代码实现树--数据结构

代码实现:

myTree = ['a',   #root
      ['b',  #left subtree
       ['d', [], []],
       ['e', [], []] ],
      ['c',  #right subtree
       ['f', [], []],
       [] ]
     ]

因为正常面试中不会考这个实现的方法,所以这里就提一下,对于插入节点,获得节点值的方法这里就不再赘述。重点讲解实现树的第二种方式。

1.2、节点和引用

这里,我们将定义具有1-根植,以及2-左子树和-3右子树属性的类。这个类有三个属性。
使用节点和引用,我们认为树的结构可能会类似于下图所示。

树1,用代码实现树--数据结构
图1.2

需要记住的是,左子节点和右子节点,会是另外的binarytree类的实例。比如,当我们插入一个新的左子节点到树中是,我们创建了另一个binarytree的实例,并修改了根节点的self.leftChild使之指向新的树。

1.2.1.创建Binarytree类

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

注意到上述代码中,构造函数init需要得到一个值存储在根中,这个值可以使你再列表中储存的任何一种你喜欢的类型(树的根对象可以指向任何一种类型)。比如在图1.2中,我们存储节点的名称a/b/c等作为根植。使用节点和引用来实现树。在图1.2中,我们创建了BinaryTree的六个实例。

1.2.2、添加子节点——创建一个新的二叉树对象

添加子节点属性,我们要考虑两种情况:

  • 1、根节点左子节点为空
    那么直接让左子节点等于新的二叉树实例对象就行
  • 2、根节点左子节点不为空
    那么我们需要将原来的左子节点降级——先通过引用类得到一个新的左子节点对象,把旧的左子节点复制成新的左子节点的左子节点,再把新的左子节点赋值给根节点的左子节点。
def insertLeft(self,newNode):
    if self.leftChild == None:
        self.leftChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        #注意,如果把下面两行替换顺序,会出现错误
        #要保证先把旧的子节点添加到新的子节点中,这样才不会丢失数据
        t.leftChild = self.leftChild
        self.leftChild = t

添加右子节点同理。

我们能够把一个二叉树的任何子节点当成二叉树本身。一个子节点不单单只是一个节点,这是一个二叉树类实例,可以进行所有对树的操作。

为了完善简单二叉树的定义,我们将编写几个用于访问左右子节点和根植的方法。

1.2.3、完善类方法

如果想要对一个树进行操作,我们需要有获得右子节点,获得左子节点,获得根节点值,更改根节点值的方法。

def getRightChild(self):
    return self.rightChild

def getLeftChild(self):
    return self.leftChild

def setRootVal(self,obj):
    self.key = obj

def getRootVal(self):
    return self.key

二、解析树

如何利用树去解决一些 实际的问题——解析树可以用来呈现例如句子或者数学表达式等真实世界中的结构。
这里不多说,可以参考 6.6. Parse Tree

;