@Astar 2022-05-16 22:09 采纳率: 55.6%
浏览 336
已结题

二叉树的中序序列和后序序列构造二叉树,实现查找,求高度,先序、中序、后序和层次遍历,用相关数据进行测试

from collections import deque
class BTNode: #二叉链中结点类
def init(self,d=None): #构造方法
self.data=d #结点值
self.lchild=None #左hai子指针
self.rchild=None #右hai子指针

class BTree: #二叉树类
def init(self,d=None): #构造方法
self.b=None #根结点指针

def DispBTree(self):                            #返回二叉链的括号表示串
    return self._DispBTree1(self.b)

def _DispBTree1(self,t):                        #被DispBTree方法调用
    if t==None:                                 #空树返回空串
        return ""
    else:
        bstr=t.data                                #输出根结点值
        if t.lchild!=None or t.rchild!=None:
            bstr+="("                            #有hai子结点时输出"("
            bstr+=self._DispBTree1(t.lchild)    #递归输出左子树
            if t.rchild!=None:
                bstr+=","                        #有右hai子结点时输出","
            bstr+=self._DispBTree1(t.rchild)    #递归输出右子树
            bstr+=")"                            #输出")"
        return bstr

def FindNode(self,x):                            #查找值为x的结点算法
    return self._FindNode1(self.b,x)

def _FindNode1(self,t,x):                       #被FindNode方法调用
    if t==None: 
        return None                                #t为空时返回null
    elif t.data==x: 
        return t                                #t所指结点值为x时返回t
    else:
        p=self._FindNode1(t.lchild,x)            #在左子树中查找
        if p!=None: 
            return p                            #在左子树中找到p结点,返回p
        else:
            return self._FindNode1(t.rchild,x)    #返回在右子树中查找结果

def Height(self):                                #求二叉树高度的算法
    return self._Height1(self.b)

def _Height1(self,t):                            #被Height方法调用
    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方法调用
if t!=None:
print(t.data,end=' ') #访问根结点
_PreOrder(t.lchild) #先序遍历左子树
_PreOrder(t.rchild) #先序遍历右子树
def InOrder(bt): #中序遍历的递归算法
_InOrder(bt.b)
def _InOrder(t): #被InOrder方法调用
if t!=None:
_InOrder(t.lchild) #中序遍历左子树
print(t.data,end=' ') #访问根结点
_InOrder(t.rchild) #中序遍历右子树
def PostOrder(bt): #后序遍历的递归算法
_PostOrder(bt.b)
def _PostOrder(t): #被PostOrder方法调用
if t!=None:
_PostOrder(t.lchild) #后序遍历左子树
_PostOrder(t.rchild) #后序遍历右子树
print(t.data,end=' ') #访问根结点

def LevelOrder(bt): #层次遍历的算法
qu=deque() #将双端队列作为普通队列qu
qu.append(bt.b) #根结点进队
while len(qu)>0: #队不空循环
p=qu.popleft() #出队一个结点
print(p.data,end=' ') #访问p结点
if p.lchild!=None: #有左hai子时将其进队
qu.append(p.lchild)
if p.rchild!=None: #有右hai子时将其进队
qu.append(p.rchild)

def CreateBTree2(posts,ins): #由后序序列posts和中序序列ins构造二叉链
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) #创建根结点(结点值为d)
p=ins.index(d) #在ins中找到根结点的索引
k=p-j #确定左子树中结点个数k
t.lchild=_CreateBTree2(posts,i,ins,j,k) #递归构造左子树
t.rchild=_CreateBTree2(posts,i+k,ins,p+1,n-k-1) #递归构造右子树
return t

#主程序
ins=['D','G','B','A','E','C','F']
posts=['G','D','B','E','F','C','A']
print()
print(" 中序:",end=' '); print(ins)
print(" 后序:",end=' '); print(posts)
print(" 构造二叉树bt")
bt=BTree()
bt=CreateBTree2(posts,ins)
print(" bt:",end=' '); print(bt.DispBTree())
x='X'
(请填补代码)
if p!=None: print(" bt中存在"+x)
else: print(" bt中不存在"+x)
print(" bt的高度=%d" %((请填补代码)))
print(" 先序序列:",end=' ');PreOrder(bt);print()
print(" 中序序列:",end=' ');(请填补代码);print()
print(" 后序序列:",end=' '); (请填补代码);print()
print(" 层次序列:",end=' '); (请填补代码);print()

  • 写回答

1条回答 默认 最新

  • Hann Yang 全栈领域优质创作者 2022-05-17 07:28
    关注
    from collections import deque
    
    class BTNode: #二叉链中结点类
            def __init__(self,d=None): #构造方法
                self.data=d #结点值
                self.lchild=None #左hai子指针
                self.rchild=None #右hai子指针
    
    class BTree: #二叉树类
            def __init__(self,d=None): #构造方法
                self.b=None #根结点指针
        
            def DispBTree(self):                            #返回二叉链的括号表示串
                return self._DispBTree1(self.b)
             
            def _DispBTree1(self,t):                        #被DispBTree方法调用
                if t==None:                                 #空树返回空串
                    return ""
                else:
                    bstr=t.data                                #输出根结点值
                    if t.lchild!=None or t.rchild!=None:
                        bstr+="("                            #有hai子结点时输出"("
                        bstr+=self._DispBTree1(t.lchild)    #递归输出左子树
                        if t.rchild!=None:
                            bstr+=","                        #有右hai子结点时输出","
                        bstr+=self._DispBTree1(t.rchild)    #递归输出右子树
                        bstr+=")"                            #输出")"
                    return bstr
             
            def FindNode(self,x):                            #查找值为x的结点算法
                return self._FindNode1(self.b,x)
             
            def _FindNode1(self,t,x):                       #被FindNode方法调用
                if t==None: 
                    return None                                #t为空时返回null
                elif t.data==x: 
                    return t                                #t所指结点值为x时返回t
                else:
                    p=self._FindNode1(t.lchild,x)            #在左子树中查找
                    if p!=None: 
                        return p                            #在左子树中找到p结点,返回p
                    else:
                        return self._FindNode1(t.rchild,x)    #返回在右子树中查找结果
             
            def Height(self):                                #求二叉树高度的算法
                return self._Height1(self.b)
             
            def _Height1(self,t):                            #被Height方法调用
                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方法调用
                if t!=None:
                    print(t.data,end=' ') #访问根结点
                    _PreOrder(t.lchild) #先序遍历左子树
                    _PreOrder(t.rchild) #先序遍历右子树
            
    def InOrder(bt): #中序遍历的递归算法
                _InOrder(bt.b)
            
    def _InOrder(t): #被InOrder方法调用
                if t!=None:
                    _InOrder(t.lchild) #中序遍历左子树
                    print(t.data,end=' ') #访问根结点
                    _InOrder(t.rchild) #中序遍历右子树
            
    def PostOrder(bt): #后序遍历的递归算法
                _PostOrder(bt.b)
            
    def _PostOrder(t): #被PostOrder方法调用
                if t!=None:
                    _PostOrder(t.lchild) #后序遍历左子树
                    _PostOrder(t.rchild) #后序遍历右子树
                    print(t.data,end=' ') #访问根结点
    
    def LevelOrder(bt): #层次遍历的算法
                qu=deque() #将双端队列作为普通队列qu
                qu.append(bt.b) #根结点进队
                while len(qu)>0: #队不空循环
                    p=qu.popleft() #出队一个结点
                    print(p.data,end=' ') #访问p结点
                    if p.lchild!=None: #有左hai子时将其进队
                        qu.append(p.lchild)
                    if p.rchild!=None: #有右hai子时将其进队
                        qu.append(p.rchild)
    
    def CreateBTree2(posts,ins): #由后序序列posts和中序序列ins构造二叉链
                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) #创建根结点(结点值为d)
                p=ins.index(d) #在ins中找到根结点的索引
                k=p-j #确定左子树中结点个数k
                t.lchild=_CreateBTree2(posts,i,ins,j,k) #递归构造左子树
                t.rchild=_CreateBTree2(posts,i+k,ins,p+1,n-k-1) #递归构造右子树
                return t
    
    #主程序
    ins=['D','G','B','A','E','C','F']
    posts=['G','D','B','E','F','C','A']
    print()
    print(" 中序:",end=' '); print(ins)
    print(" 后序:",end=' '); print(posts)
    print(" 构造二叉树bt")
    bt=BTree()
    bt=CreateBTree2(posts,ins)
    print(" bt:",end=' '); print(bt.DispBTree())
    
    
    x='X'
    p=bt.FindNode(x)
    if p!=None: print(" bt中存在"+x)
    else: print(" bt中不存在"+x)
    
    print(" bt的高度=%d" %( bt.Height() ))
    print(" 先序序列:",end=' ');PreOrder(bt);print()
    print(" 中序序列:",end=' ');InOrder(bt);print()
    print(" 后序序列:",end=' ');PostOrder(bt);print()
    print(" 层次序列:",end=' ');LevelOrder(bt);print()
    
    #result:
     中序: ['D', 'G', 'B', 'A', 'E', 'C', 'F']
     后序: ['G', 'D', 'B', 'E', 'F', 'C', 'A']
     构造二叉树bt
     bt: A(B(D(,G)),C(E,F))
     bt中不存在X
     bt的高度=4
     先序序列: A B D G C E F 
     中序序列: D G B A E C F 
     后序序列: G D B E F C A 
     层次序列: A B C D E F G 
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 5月25日
  • 已采纳回答 5月17日
  • 创建了问题 5月16日

悬赏问题

  • ¥200 如何使用postGis实现最短领规划?
  • ¥15 pyinstaller打包错误
  • ¥20 cesm的气溶胶排放文件
  • ¥15 逐月累计,月份不连续,补齐月份
  • ¥15 应用简单的Python代码完成一个学生成绩管理系统
  • ¥15 用matlab求微分方程初值问题
  • ¥15 vscode下编写第三方库opencv与pcl代码时没有代码提示
  • ¥15 能够跑通不报错,如何解决?(标签-matlab)
  • ¥15 MOS在RDS较大,频率高时开关波形异常
  • ¥15 SCENIC分析报错求解答