如何实现二叉树？

在这个问题中，出现的原因是想要了解如何实现一个二叉树。为了解决这个问题，可以按照以下步骤进行操作。

首先，需要定义一个BinaryTree类，其中包含了一些方法来操作二叉树的节点。在这个类中，有getLeftChild和getRightChild方法来获取节点的左子节点和右子节点，setNodeValue和getNodeValue方法来设置和获取节点的值，insertRight和insertLeft方法来插入节点的右子节点和左子节点，以及printTree方法来打印整个二叉树。

接下来，可以创建一个testTree函数来测试这个二叉树的实现。在这个函数中，首先创建一个名为myTree的BinaryTree对象，并将根节点的值设置为"Maud"。然后，使用insertLeft方法插入一个值为"Bob"的左子节点，再使用insertRight方法插入一个值为"Tony"的右子节点，并再次使用insertRight方法插入一个值为"Steven"的右子节点。最后，调用printTree方法打印整个二叉树。

此外，文章还提到了关于二叉树的其他资料。第一个链接是关于二叉树的一个简单实现的文章，可以点击链接进行阅读。第二个链接是一个很好的教程，其中包含了一些问题可以帮助理解二叉树的实现。最后一个链接是一个坏掉的链接，需要修复。

在代码中，还提到了一个问题，即在insertLeft方法中的代码是有问题的，会导致在尝试递归遍历二叉树的最左分支时产生无限循环。可以通过交换以下两行代码来轻松解决这个问题：tree.left = self.left self.left = tree。

这篇文章介绍了如何实现一个二叉树，并提供了一些相关的资料和解决问题的方法。

如何实现二叉树？

在面试中，一个节点类(Node class)足以表示一个二叉树的数据结构。

（虽然其他答案大部分是正确的，但在二叉树中不需要它们：不需要扩展对象类，不需要是二叉搜索树，不需要导入deque。）

下面是一个树的示例：

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

在这个示例中，n1是树的根节点，它有n2和n3作为它的子节点。

其他答案对于一个二叉树来说过于复杂。这是实现二叉树所需要的基本部分。其他答案会使新手难以理解，所以我只是发布了最基本的部分来帮助新手。其他答案适合于文章和学术论文；）这也是面试中的一个需要的部分。

它增加了简单性，这是有价值的。

简单而非常逻辑。太棒了！我喜欢它！

添加图表是很棒的！

如何实现二叉树？

以下是一个简单的递归实现的二叉搜索树。

#!/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 is None:
            self.root = Node(val)
        else:
            self._add(val, self.root)
    def _add(self, val, node):
        if val < node.v:
            if node.l is not None:
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if node.r is not None:
                self._add(val, node.r)
            else:
                node.r = Node(val)
    def find(self, val):
        if self.root is not 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 is not None):
            return self._find(val, node.l)
        elif (val > node.v and node.r is not None):
            return self._find(val, node.r)
    def deleteTree(self):
        # garbage collector will do this for us.
        self.root = None
    def printTree(self):
        if self.root is not None:
            self._printTree(self.root)
    def _printTree(self, node):
        if node is not None:
            self._printTree(node.l)
            print(str(node.v) + ' ')
            self._printTree(node.r)
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()

很好的实现。我只是在这里指出一些风格上的问题。Python通常使用`node is not None`而不是你的`(node!=None)`。另外，你可以使用`__str__`函数代替`printTree`方法。

此外，你的`_find`应该是：

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

这不是一个二叉树，而是一个二叉搜索树。

是的，这是一个二叉搜索树。从`_printTree`函数来看，树的遍历是左-根-右。

`tree.find(0)`, `tree.find(2)`, `tree.find(4)`, `tree.find(8)`都返回`None`。

进一步解释's'的评论，你应该修改`_find()`方法，使其将递归调用返回给函数。你现在的写法是，值在回传给调用函数时没有传回值。

修改后的写法如下：

def _find(self, node, val):
    if val == node.value:
        return node
    elif val > node.value and node.right is not None:
        return self._find(node.right, val)
    elif val < node.value and node.left is not None:
        return self._find(node.left, val)
    else:
        return None

有一个小bug，当你尝试插入一个已经存在的键时，它会在树中继续向下创建一个具有重复键的新节点。

我更喜欢非递归实现，但至少你应该将Node类声明为"object"的子类，并在类定义中声明`__slots__ = "l","v","r"`。因为你可能有很多节点，这样可以节省大量内存。

这不是一个二叉树，而是一个二叉搜索树。