如何实现二叉树？

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

# 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 3

BST在Python中的简单实现

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)