003树.md

实现树的数据结构

什么是树

树是计算机里非常重要的数据机构，与数组、链表类似，类比于现实中的树，树的数据结构有根节点、叶子节点等。树其实是很大的抽象，我们根据结构还可以分为二叉树、红黑树等，这里我们将介绍和时间较常见和易入门的几种。

如何实现树的数据结构

任何通用编程语言都可以实现树，不过不同语言实现难度不同，但基本思想是一样的。

在面向对象的设计中，首先要定义Node类，然后可以定义Tree类并实现遍历等函数。

使用Python实现通用树

首先进入ipython开始编写代码，按之前讨论先定义一个类。

class Node(ojbect):

  def __init__(self):
    print("Init the clas")

node = Node()

我们设计一个节点，首先应该包含一个数据，然后还包含一系列子节点，用数组来存储。

class Node(object):

  def __init__(self, data):
    self.data = data
    self.children = []

  def add_child(self, Node):
    self.children.append(Node)

node = Node("node1")
node2 = Node("node2")

node.add_child(node2)

接着我们可以考虑实现Tree类，也是用数组来保存一系列Node。

class Tree(object):

  def __init__(self):
    self.nodes = []

tree = Tree()

如何实现遍历二叉树

遍历树的方法有多种，深度优先或广度优先，为了简化代码我们通过实现二叉树和二叉树的遍历来演示。

首先每个二叉树都有两个节点，因此我们定义的Node类与前面有些差异，而Tree类暂时只需要记录root的节点。

class BinaryNode(object):

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right


class BinaryTree(object):

  def __init__(self):
    self.root = None


tree = BinaryTree()

然后我们考虑支持插入数据，这是要保证数据比较小的在左节点，数据比较大的在右节点。注意插入的时候我们是递归实现，因此其实需要多加一个root参数的。

class BinaryTree(object):

  def __init__(self):
    self.root = None

  def add_node(self, root, data):
    if self.root == None:
       self.root = BinaryNode(data)
    else:
      if root is None:
        root = BinaryNode(data)
      elif data <= root.data:
        root.left = self.add_node(root.left, data)
      elif data > root.data:
        root.right = self.add_node(root.right, data)
    return root

tree = BinaryTree()
tree.add_node(tree.root, 10)
tree.add_node(tree.root, 5)
tree.add_node(tree.root, 15)
tree.add_node(tree.root, 20)

然后要实现遍历，从左节点到右节点深度遍历，这样就比较简单了。

  def pre_travel(self, root):
    if root != None:
      if root.left != None:
        self.pre_travel(root.left)
      print(root.data)
      if root.right != None:
        self.pre_travel(root.right)


tree = BinaryTree()
tree.add_node(tree.root, 10)
tree.add_node(tree.root, 5)
tree.add_node(tree.root, 15)
tree.add_node(tree.root, 20)

tree.pre_travel(tree.root)
# Print [5, 10, 15, 20]

这是本章内容，希望对你有所帮助。进入下一章