如何实现二叉树？

Question

哪个是可用于在Python中实现二进制树的最佳数据结构？

Answer 1

这是我对二叉树的简单递归实现.

#!/usr/bin/python

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

class Tree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if(node.r != None):
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        elif(val < node.v and node.l != None):
            self._find(val, node.l)
        elif(val > node.v and node.r != None):
            self._find(val, node.r)

    def deleteTree(self):
        # garbage collector will do this for us. 
        self.root = None

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print str(node.v) + ' '
            self._printTree(node.r)

#     3
# 0     4
#   2      8
tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print (tree.find(3)).v
print tree.find(10)
tree.deleteTree()
tree.printTree()

Answer 2

[面试需要什么] Node 类是表示二叉树的足够数据结构。

（虽然其他答案大多是正确的，但二叉树不需要它们：不需要扩展对象类，不需要成为 BST，不需要导入双端队列）。

class Node:

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

下面是一个树的例子：

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.left  = n2
n1.right = n3

在这个例子中，n1 是树的根，有 n2、n3 作为它的孩子。

Answer 3

# simple binary tree
# in this implementation, a node is inserted between an existing node and the root


class BinaryTree():

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

    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

    def insertRight(self,newNode):
        if self.right == None:
            self.right = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.right = self.right
            self.right = tree

    def insertLeft(self,newNode):
        if self.left == None:
            self.left = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.left = self.left
            self.left = tree


def printTree(tree):
        if tree != None:
            printTree(tree.getLeftChild())
            print(tree.getNodeValue())
            printTree(tree.getRightChild())



# test tree

def testTree():
    myTree = BinaryTree("Maud")
    myTree.insertLeft("Bob")
    myTree.insertRight("Tony")
    myTree.insertRight("Steven")
    printTree(myTree)

阅读更多相关内容: - 这是一个非常简单的二叉树实现.

这是一个很好的教程,介于两者之间

Answer 4

在Python中简单实现BST

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

class Tree:
    def __init__(self):
        self.root = None

    def addNode(self, node, value):
        if(node==None):
            self.root = TreeNode(value)
        else:
            if(value<node.data):
                if(node.left==None):
                    node.left = TreeNode(value)
                else:
                    self.addNode(node.left, value)
            else:
                if(node.right==None):
                    node.right = TreeNode(value)
                else:
                    self.addNode(node.right, value)

    def printInorder(self, node):
        if(node!=None):
            self.printInorder(node.left)
            print(node.data)
            self.printInorder(node.right)

def main():
    testTree = Tree()
    testTree.addNode(testTree.root, 200)
    testTree.addNode(testTree.root, 300)
    testTree.addNode(testTree.root, 100)
    testTree.addNode(testTree.root, 30)
    testTree.printInorder(testTree.root)

Answer 5

使用列表实现二叉树的一种非常快速的方法.不是最有效的,也不是很好地处理零值.但它非常透明(至少对我而言):

def _add(node, v):
    new = [v, [], []]
    if node:
        left, right = node[1:]
        if not left:
            left.extend(new)
        elif not right:
            right.extend(new)
        else:
            _add(left, v)
    else:
        node.extend(new)

def binary_tree(s):
    root = []
    for e in s:
        _add(root, e)
    return root

def traverse(n, order):
    if n:
        v = n[0]
        if order == 'pre':
            yield v
        for left in traverse(n[1], order):
            yield left
        if order == 'in':
            yield v
        for right in traverse(n[2], order):
            yield right
        if order == 'post':
            yield v

从iterable构造一个树:

 >>> tree = binary_tree('A B C D E'.split())
 >>> print tree
 ['A', ['B', ['D', [], []], ['E', [], []]], ['C', [], []]]

穿越树:

 >>> list(traverse(tree, 'pre')), list(traverse(tree, 'in')), list(traverse(tree, 'post'))
 (['A', 'B', 'D', 'E', 'C'],
  ['D', 'B', 'E', 'A', 'C'],
  ['D', 'E', 'B', 'C', 'A'])

Answer 6

基于连接节点的类Node是标准方法。这些可能很难想象。

受一篇关于Python 模式 - 实现图的文章的启发，考虑一个简单的字典：

给定

一棵二叉树

               a
              / \
             b   c
            / \   \
           d   e   f

代码

制作一个唯一节点的字典：

tree = {
   "a": ["b", "c"],
   "b": ["d", "e"],
   "c": [None, "f"],
   "d": [None, None],
   "e": [None, None],
   "f": [None, None],
}

细节

• 每个键值对都是一个指向其子节点的唯一节点。
• 列表（或元组）包含一对有序的左/右子元素。
• 对于具有有序插入的字典，假设第一个条目是根。
• 常见方法可以是改变或遍历 dict 的函数（请参阅 参考资料find_all_paths()）。

基于树的函数通常包括以下常见操作：

• traverse：按给定顺序生成每个节点（通常是从左到右）
  • 广度优先搜索（BFS）：遍历级别
  • 深度优先搜索（DFS）：首先遍历分支（前序/中序/后序）
• insert：根据子节点的数量向树添加一个节点
• 删除：根据子节点的数量删除节点
• 更新：将丢失的节点从一棵树合并到另一棵树
• Visit：产生遍历节点的值

尝试实施所有这些操作。在这里，我们演示了其中一个函数 - BFS 遍历：

例子

import collections as ct


def traverse(tree):
    """Yield nodes from a tree via BFS."""
    q = ct.deque()                                         # 1
    root = next(iter(tree))                                # 2
    q.append(root)
    
    while q:
        node = q.popleft() 
        children = filter(None, tree.get(node))
        for n in children:                                 # 3 
            q.append(n)
        yield node

list(traverse(tree))
# ['a', 'b', 'c', 'd', 'e', 'f']

这是应用于节点和子节点字典的广度优先搜索（级别顺序）算法。

1. 初始化deque并稍后使用该.popleft()方法来模拟FIFO 队列。
2. 获取根节点并将其排入队列（假设根是字典中的第一个条目，Python 3.6+）。
3. 迭代节点并将其出队，将其子节点入队并生成节点值。

另请参阅有关树的深入教程。

洞察力

通过替换底层数据结构，我们可以轻松地在 BFS 和 DFS 遍历技术之间切换。提醒：

• 广度优先搜索（BFS）：使用 FIFO 数据结构（又名“ queue”），例如queue.queue（collections.deque如上所示）
• 深度优先搜索（DFS）：使用 LIFO 数据结构（又名堆栈），例如list，collections.deque

FIFO（先进先出）数据结构将在一端添加项目并从另一端退出。LIFO（后进先出）数据结构将在退出的同一侧添加项目。

Adeque可以模拟 FIFO 或 LIFO，具体取决于.pop*()使用哪种方法使节点出列（如上所示）。因此，替换node = q.popleft()为node = q.pop()将形成一个 LIFO 堆栈，从而产生一个右偏的、预先排序的 DFS : ['a', 'c', 'f', 'b', 'e', 'd']。

Answer 7

我不禁注意到这里的大多数答案都在实现二进制搜索树。二进制搜索树！=二进制树。

• 二叉搜索树具有非常特殊的属性：对于任何节点X，X的密钥都大于其左子节点的任何后代的关键字，并且小于其右子节点的任何后代的关键字。

• 二叉树不施加这样的限制。二叉树只是具有“键”元素和两个孩子的数据结构，分别是“左”和“右”。

• 树是二叉树的更一般的情况，其中每个节点可以具有任意数量的子代。通常，每个节点都有一个“孩子”元素，其类型为列表/数组。

现在，为了回答OP的问题，我将在Python中包含Binary Tree的完整实现。给定它提供最佳的O（1）查找，存储每个BinaryTreeNode的基础数据结构是一个字典。我还实现了深度优先遍历和深度优先遍历。这些是在树上执行的非常常见的操作。

from collections import deque

class BinaryTreeNode:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

    def __repr__(self):
        return "%s l: (%s) r: (%s)" % (self.key, self.left, self.right)

    def __eq__(self, other):
        if self.key == other.key and \
            self.right == other.right and \
                self.left == other.left:
            return True
        else:
            return False

class BinaryTree:
    def __init__(self, root_key=None):
        # maps from BinaryTreeNode key to BinaryTreeNode instance.
        # Thus, BinaryTreeNode keys must be unique.
        self.nodes = {}
        if root_key is not None:
            # create a root BinaryTreeNode
            self.root = BinaryTreeNode(root_key)
            self.nodes[root_key] = self.root

    def add(self, key, left_key=None, right_key=None):
        if key not in self.nodes:
            # BinaryTreeNode with given key does not exist, create it
            self.nodes[key] = BinaryTreeNode(key)
        # invariant: self.nodes[key] exists

        # handle left child
        if left_key is None:
            self.nodes[key].left = None
        else:
            if left_key not in self.nodes:
                self.nodes[left_key] = BinaryTreeNode(left_key)
            # invariant: self.nodes[left_key] exists
            self.nodes[key].left = self.nodes[left_key]

        # handle right child
        if right_key == None:
            self.nodes[key].right = None
        else:
            if right_key not in self.nodes:
                self.nodes[right_key] = BinaryTreeNode(right_key)
            # invariant: self.nodes[right_key] exists
            self.nodes[key].right = self.nodes[right_key]

    def remove(self, key):
        if key not in self.nodes:
            raise ValueError('%s not in tree' % key)
        # remove key from the list of nodes
        del self.nodes[key]
        # if node removed is left/right child, update parent node
        for k in self.nodes:
            if self.nodes[k].left and self.nodes[k].left.key == key:
                self.nodes[k].left = None
            if self.nodes[k].right and self.nodes[k].right.key == key:
                self.nodes[k].right = None
        return True

    def _height(self, node):
        if node is None:
            return 0
        else:
            return 1 + max(self._height(node.left), self._height(node.right))

    def height(self):
        return self._height(self.root)

    def size(self):
        return len(self.nodes)

    def __repr__(self):
        return str(self.traverse_inorder(self.root))

    def bfs(self, node):
        if not node or node not in self.nodes:
            return
        reachable = []    
        q = deque()
        # add starting node to queue
        q.append(node)
        while len(q):
            visit = q.popleft()
            # add currently visited BinaryTreeNode to list
            reachable.append(visit)
            # add left/right children as needed
            if visit.left:
                q.append(visit.left)
            if visit.right:
                q.append(visit.right)
        return reachable

    # visit left child, root, then right child
    def traverse_inorder(self, node, reachable=None):
        if not node or node.key not in self.nodes:
            return
        if reachable is None:
            reachable = []
        self.traverse_inorder(node.left, reachable)
        reachable.append(node.key)
        self.traverse_inorder(node.right, reachable)
        return reachable

    # visit left and right children, then root
    # root of tree is always last to be visited
    def traverse_postorder(self, node, reachable=None):
        if not node or node.key not in self.nodes:
            return
        if reachable is None:
            reachable = []
        self.traverse_postorder(node.left, reachable)
        self.traverse_postorder(node.right, reachable)
        reachable.append(node.key)
        return reachable

    # visit root, left, then right children
    # root is always visited first
    def traverse_preorder(self, node, reachable=None):
        if not node or node.key not in self.nodes:
            return
        if reachable is None:
            reachable = []
        reachable.append(node.key)
        self.traverse_preorder(node.left, reachable)
        self.traverse_preorder(node.right, reachable)
        return reachable