二叉树

二叉树广度优先遍历:一层一层
二叉树深度优先遍历:前序(根左右)、中序(左根右)、后序(左右根)

class Node():
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

class Tree():
    def __init__(self):
        self.root = None
    def addNode(self, item):
        node = Node(item)
        if self.root == None:
            self.root = node
            return
        cur = self.root
        q = [cur] #列表元素是我们进行遍历判断的节点
        while q:
            nd = q.pop(0)
            if nd.left == None:
                nd.left = node
                return
            else:
                q.append(nd.left)
            if nd.right == None:
                nd.right = node
                return
            else:
                q.append(nd.right)
    def travel(self):
        cur = self.root
        q = [cur]
        while q:
            nd = q.pop(0)
            print(nd.item)
            if nd.left:
                q.append(nd.left)
            if nd.right:
                q.append(nd.right)
    #前序:根左右
    def forward(self,root):
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)
    # 中序:左根右
    def middle(self, root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    # 后序:左右根
    def back(self, root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)

tree = Tree()
tree.addNode(1)
tree.addNode(2)
tree.addNode(3)
tree.addNode(4)
tree.addNode(5)
tree.addNode(6)
tree.addNode(7)
tree.travel()
print("前序")
tree.forward(tree.root)
print("中序")
tree.middle(tree.root)
print("后序")
tree.back(tree.root)
上一篇:斐波那契堆模板


下一篇:bzoj2733 永无乡 splay树的启发式合并