from collections import deque  #層遍歷中用到隊(duì)列數(shù)據(jù)類型
 
class BTNode:   #二叉鏈中結(jié)點(diǎn)類
    def __init__(self,d = None):
        self.data = d       #結(jié)點(diǎn)值
        self.lchild = None  #左hai子指針
        self.rchild = None  #右hai子指針
 
class BTree: #二叉樹類
    def __init__(self,d = None):
        self.b = None       #根結(jié)點(diǎn)指針
    
    def DispBTree(self):    #返回二叉鏈的括號表示串
        return self._DispBTree1(self.b)
     
    def _DispBTree1(self,t):    #被DispBTree方法調(diào)用
        if t==None:             #空樹返回空串
            return ""
        else:
            bstr = t.data       #輸出根結(jié)點(diǎn)值
            if t.lchild != None or t.rchild != None:
                bstr += "("     #有hai子結(jié)點(diǎn)時(shí)輸出"("
                bstr += self._DispBTree1(t.lchild)    #遞歸輸出左子樹
            if t.rchild != None:
                bstr += ","     #有右hai子結(jié)點(diǎn)時(shí)輸出","
                bstr += self._DispBTree1(t.rchild)    #遞歸輸出右子樹
                bstr += ")"     #輸出")"
        return bstr
     
    def FindNode(self,x):       #查找值為x的結(jié)點(diǎn)算法
        return self._FindNode1(self.b,x)
     
    def _FindNode1(self,t,x):   #被FindNode方法調(diào)用
        if t==None: 
            return None         #t為空時(shí)返回null
        elif t.data==x: 
            return t            #t所指結(jié)點(diǎn)值為x時(shí)返回t
        else:
            p = self._FindNode1(t.lchild,x)    #在左子樹中查找
        if p != None: 
            return p            #在左子樹中找到p結(jié)點(diǎn)，返回p
        else:
            return self._FindNode1(t.rchild,x)  #返回在右子樹中查找結(jié)果
         
    def Height(self):           #求二叉樹高度的算法
        return self._Height1(self.b)
         
    def _Height1(self,t):       #被Height方法調(diào)用
        if t==None:
            return 0            #空樹的高度為0
        else:
            lh = self._Height1(t.lchild)    #求左子樹高度lchildh
            rh = self._Height1(t.rchild)    #求右子樹高度rchildh
        return max(lh,rh)+1
 
def PreOrder(bt):   #先序遍歷的遞歸算法
    _PreOrder(bt.b)
    
def _PreOrder(t):   #被PreOrder方法調(diào)用
    if t != None:
        print(t.data,end = ' ')     #訪問根結(jié)點(diǎn)
        _PreOrder(t.lchild)         #先序遍歷左子樹
        _PreOrder(t.rchild)         #先序遍歷右子樹
    
def InOrder(bt):    #中序遍歷的遞歸算法
    _InOrder(bt.b)
    
def _InOrder(t):    #被InOrder方法調(diào)用
    if t != None:
        _InOrder(t.lchild)          #中序遍歷左子樹
        print(t.data,end = ' ')     #訪問根結(jié)點(diǎn)
        _InOrder(t.rchild)          #中序遍歷右子樹
    
def PostOrder(bt):  #后序遍歷的遞歸算法
    _PostOrder(bt.b)
    
def _PostOrder(t):  #被PostOrder方法調(diào)用
    if t != None:
        _PostOrder(t.lchild)        #后序遍歷左子樹
        _PostOrder(t.rchild)        #后序遍歷右子樹
        print(t.data,end = ' ')     #訪問根結(jié)點(diǎn)
 
def LevelOrder(bt): #層序遍歷的算法
    qu = deque()            #將雙端隊(duì)列作為普通隊(duì)列qu
    qu.append(bt.b)         #根結(jié)點(diǎn)進(jìn)隊(duì)
    while len(qu)>0:        #隊(duì)不空循環(huán)
        p = qu.popleft()            #出隊(duì)一個(gè)結(jié)點(diǎn)
        print(p.data,end = ' ')     #訪問p結(jié)點(diǎn)
        if p.lchild != None:        #有左hai子時(shí)將其進(jìn)隊(duì)
            qu.append(p.lchild)
        if p.rchild != None:        #有右hai子時(shí)將其進(jìn)隊(duì)
            qu.append(p.rchild)
 
def CreateBTree2(posts,ins):        #由后序序列posts和中序序列ins構(gòu)造二叉鏈
    bt = BTree()
    bt.b = _CreateBTree2(posts,0,ins,0,len(posts))
    return bt
 
def _CreateBTree2(posts,i,ins,j,n):
    if n <= 0:
        return None
    d = posts[i+n-1]        #取后序序列尾元素d
    t = BTNode(d)           #創(chuàng)建根結(jié)點(diǎn)(結(jié)點(diǎn)值為d)
    p = ins.index(d)        #在ins中找到根結(jié)點(diǎn)的索引
    k = p-j                 #確定左子樹中結(jié)點(diǎn)個(gè)數(shù)k
    t.lchild = _CreateBTree2(posts,i,ins,j,k)           #遞歸構(gòu)造左子樹
    t.rchild = _CreateBTree2(posts,i+k,ins,p+1,n-k-1)   #遞歸構(gòu)造右子樹
    return t
 
if __name__ == '__main__':
 
    inlst = ['D','G','B','A','E','C','F']
    posts = ['G','D','B','E','F','C','A']
 
    print(f"中序列表 ：{inlst}")
    print(f"后序列表 ：{posts}")
    
    #構(gòu)造二叉樹bt    
    bt = BTree()
    bt = CreateBTree2(posts,inlst)
    print(f"\n構(gòu)造二叉樹：{bt.DispBTree()}")
 
    x = 'F'
    if bt.FindNode(x):
        print(f"bt中存在 ：'{x}'")
    else:
        print(f"bt中不存在 ：'{x}'")
     
    print(f"bt的高度 ：{bt.Height():^3}")
 
    print("\n先序遍歷 ：",end='')
    PreOrder(bt)
    print("\n中序遍歷列 ：",end='')
    InOrder(bt)
    print("\n后序遍歷 ：",end='')
    PostOrder(bt)
    print("\n層序遍歷 ：",end='')
    LevelOrder(bt)