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

参考Trees and Tree Algorithms

1.1、通过嵌套列表实现树

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

代码实现：

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

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

1.2、节点和引用

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

图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