Cartesian Tree – PAT_A

Cartesian Tree – PAT_A

问题描述: Cartesian tree,笛卡尔树。从一个各数值均不同的序列建一棵笛卡尔树,这棵树的中序遍历与这个序列一致,同时,笛卡尔树符合一个小顶堆的结构(父结点的值均小于子结点)

给出一个各数值均不同的序列,根据此序列建一棵笛卡尔树,并输出它的层序遍历。

问题分析:给定序列与树的中序遍历一致,并且树是个小顶堆。那么大方向是向右加结点,如果初始有1个笛卡尔树,序列的下一个数字比当前树根的值还小,则这下一个数字就是新的根,原树成为其左子结点。如果下个数字比树根的值大,若右子树为空,则直接插入成右子树,右子树不为空则在右子树上找一个合适的位置插入。由于要求中序必须与原序列一致,所以右子树不空的情况下,新插入的必须在最右,新插入位置原有的树是新插入结点的左子树即可。建好了树对此树层序遍历即可出结果。

参考程序

N=int(input())

class Tree:
    def __init__(self,v):
        self.value=v
        self.lChild=None
        self.rChild=None

def transTree(t):
    def __tran(t):
        if t!=None:
            __tran(t.lChild)
            print(t.value,end=" ")
            __tran(t.rChild)
    __tran(t)
    print()

def Enqueue(Q,v):
    Q.append(v)
    
def Dequeue(Q):
    return Q.pop(0)


def levelOrder(t):
    queue1=[]
    print(t.value,end="")
    if t.lChild!=None:
        Enqueue(queue1,t.lChild)
    if t.rChild!=None:
        Enqueue(queue1,t.rChild)
    while len(queue1)>0:
        print(" ",end="")
        node=Dequeue(queue1)
        if node.lChild!=None:
            Enqueue(queue1,node.lChild)
        if node.rChild!=None:
            Enqueue(queue1,node.rChild)
        print(node.value,end="")
        
a=map(int,input().split())
t=Tree(a.__next__())

for it in a:
    if it < t.value:
        nt=Tree(it)
        nt.lChild=t
        t=nt
        
    else:
        # it > t.value
        # if it.rchild is none, insert it        
        if t.rChild==None:
            t.rChild=Tree(it)
        
        # else
        #  go through tha path and find correct position and insert
        else:
            prev=t
            curr=t.rChild
            while curr!=None:
                if prev.value<it and it<curr.value:
                    break
                prev=curr
                curr=curr.rChild
            newNode=Tree(it)
            newNode.lChild=curr
            prev.rChild=newNode
            

levelOrder(t)

发表评论

电子邮件地址不会被公开。 必填项已用*标注