为了账号安全,请及时绑定邮箱和手机立即绑定

如何实现二叉树?

如何实现二叉树?

慕无忌1623718 2019-11-22 15:57:14
哪种数据结构可用于在Python中实现二叉树?
查看完整描述

3 回答

?
慕尼黑5688855

TA贡献1848条经验 获得超2个赞

这是二进制搜索树的简单递归实现。


#!/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()


查看完整回答
反对 回复 2019-11-22
?
LEATH

TA贡献1936条经验 获得超6个赞

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

在此处了解更多信息:-这是二进制树的非常简单的实现。


查看完整回答
反对 回复 2019-11-22
?
慕莱坞森

TA贡献1810条经验 获得超4个赞

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)


查看完整回答
反对 回复 2019-11-22
  • 3 回答
  • 0 关注
  • 750 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信