# 二叉树
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:
            n=q.pop(0)
            if n.left==None:
                n.left=node
                break
            else:
                q.append(n.left)

            if n.right==None:
                n.right=node
                break
            else:
                q.append(n.right)

    # 广度遍历
    def travel(self):
        cur=self.root
        q=[cur]
        while q:
            n=q.pop(0)
            print(n.item)
            if n.left!=None:
                q.append(n.left)
            if n.right!=None:
                q.append(n.right)

    # 深度遍历：前中后指的是根节点的位置
    # 前序：根左右
    def frontTravel(self,root):
        # 空
        if root==None:
            return
        print(root.item)
        self.frontTravel(root.left)
        self.frontTravel(root.right)
    # 中序：左根右
    def midTravel(self,root):
        if root==None:
            return
        self.midTravel(root.left)
        print(root.item)
        self.midTravel(root.right)
    # 后序：左右根
    def afterTravel(self,root):
        if root==None:
            return
        self.afterTravel(root.left)
        self.afterTravel(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()
tree.midTravel(tree.root)

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

class SortTree():
    def __init__(self):
        self.root=None

    def midTravel(self,root):
        # print(111)
        if root==None:
            return
        # 左根右
        self.midTravel(root.left)
        print(root.item)
        self.midTravel(root.right)

    def insertNode(self,item):
        node=Node(item)
        cur=self.root
        if self.root == None:

            self.root=node
            return
        # 树非空
        while True:
            if cur.item>node.item:
                if cur.left==None:

                    cur.left=node
                    break
                else:
                    cur=cur.left
            else:
                if cur.right==None:

                    cur.right=node
                    break
                else:
                    cur=cur.right




t = SortTree()
t.insertNode(3)
t.insertNode(8)
t.insertNode(3)
t.insertNode(1)
t.insertNode(1)

t.midTravel(t.root)