python实现二叉排序树

目录

• 方法一（粗暴）
• 方法二（递归）

方法一（粗暴）

#二叉排序树
class BTree():
    def __init__(self,data):
        self.left = None
        self.right = None
        if type(data) == list:
            self.data = data[0]
            for d in data[1:]:
                self.insert(d)
        else:
            self.data = data
    def insert(self,data):
        bt = self
        while True:
            if data <= bt.data:
                if bt.left == None:
                    bt.left = BTree(data)
                    break
                else:
                    bt = bt.left
            else:
                if bt.right == None:
                    bt.right = BTree(data)
                    break
                else:
                    bt = bt.right
    def mid_order(self):
        res = []
        stack = []
        node = self 
        while node or stack:
            while node:
                stack.append(node) 
                node = node.left
            node = stack.pop()
            res.append(node.data)
            node = node.right
        return res

data = [5,1,2,3,6,8,9]
bt = BTree(data)
print(bt.mid_order())

方法二（递归）

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

class BinaryTree(object):
    def insert(self,root, node):
        if root is None:
            return node
        if node.data < root.data:
            root.left = self.insert(root.left, node)
        else:
            root.right = self.insert(root.right, node)
        return root
    def mid_order(self,root):
        node = root
        stack = []
        res = []
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.data)
            node = node.right
        return res
    
data = [5,1,2,3,6,8,9]
root = TreeNode(data[0])
tree = BinaryTree()
for i in data[1:]:
    tree.insert(root,TreeNode(i))
print(tree.mid_order(root))

到此这篇关于python实现二叉排序树的文章就介绍到这了,更多相关python二叉排序树内容请搜索北冥有鱼以前的文章或继续浏览下面的相关文章希望大家以后多多支持北冥有鱼！