补全代码 from collections import deque class BTNode: #二叉链中结点类 def init(self,d=None): #构造方法 …… class BTree: #二叉树类 def init(self,d=None): #构造方法 …… def DispBTree(self): #返回二叉链的括号表示串 …… def _DispBTree1(self,t): #被DispBTree方法调用 …… def FindNode(self,x): #查找值为x的结点算法 …… def _FindNode1(self,t,x): #被FindNode方法调用 ……. def Height(self): #求二叉树高度的算法 …… def _Height1(self,t): #被Height方法调用 …… def PreOrder(bt): #先序遍历的递归算法 ……. def _PreOrder(t): #被PreOrder方法调用 …… def InOrder(bt): #中序遍历的递归算法 …… def _InOrder(t): #被InOrder方法调用 …… def PostOrder(bt): #后序遍历的递归算法 …… def _PostOrder(t): #被PostOrder方法调用 …… def LevelOrder(bt): #层次遍历的算法 …… def CreateBTree2(posts,ins): #由后序序列posts和中序序列ins构造二叉链 …… def _CreateBTree2(posts,i,ins,j,n): #被CreateBTree2方法调用 …… #主程序 ins=[……] posts=[……] print() print(" 中序:",end=' '); print(ins) print(" 后序:",end=' '); print(posts) print(" 构造二叉树bt") bt= ___ ___ ___ ___ bt= ___ ___ ___ ___ print(" bt:",end=' '); print(bt.DispBTree()) x= ___ ___ ___ ___ p=bt.FindNode(x) if p!=None: print(" bt中存在"+x) else: print(" bt中不存在"+x) print(" bt的高度=%d" %(bt.Height())) print(" 先序序列:",end=' '); _ ___ ___ ___;print() print(" 中序序列:",end=' '); _ ___ ___ ___;print() print(" 后序序列:",end=' '); _ ___ ___ ___;print() print(" 层次序列:",end=' '); _ ___ ___ ___;print()补全代码

补全代码如下：

from collections import deque

class BTNode: #二叉链中结点类
def __init__(self,d=None): #构造方法
self.data=d
self.lchild=None
self.rchild=None

class BTree: #二叉树类
def __init__(self,d=None): #构造方法
if d is None:
self.root=None
else:
self.root=BTNode(d)

def DispBTree(self): #返回二叉链的括号表示串
t=self.root
s=""
if t is not None:
s=self._DispBTree1(t)
return s

def _DispBTree1(self,t): #被DispBTree方法调用
s=str(t.data)
if t.lchild is not None:
s+="("+self._DispBTree1(t.lchild)
if t.lchild is None and t.rchild is not None:
s+="("+str(None)
if t.rchild is not None:
s+=self._DispBTree1(t.rchild)+")"
return s

def FindNode(self,x): #查找值为x的结点算法
t=self.root
if t is None:
return None
else:
return self._FindNode1(t,x)

def _FindNode1(self,t,x): #被FindNode方法调用
if t is None:
return None
elif t.data==x:
return t
else:
p=self._FindNode1(t.lchild,x)
if p is not None:
return p
else:
return self._FindNode1(t.rchild,x)

def Height(self): #求二叉树高度的算法
t=self.root
if t is None:
return 0
else:
return self._Height1(t)

def _Height1(self,t): #被Height方法调用
if t is None:
return 0
else:
lh=self._Height1(t.lchild)
rh=self._Height1(t.rchild)
if lh>rh:
return lh+1
else:
return rh+1

def PreOrder(bt): #先序遍历的递归算法
t=bt.root
if t is not None:
_PreOrder(t)

def _PreOrder(t): #被PreOrder方法调用
print(t.data,end=' ')
if t.lchild is not None:
_PreOrder(t.lchild)
if t.rchild is not None:
_PreOrder(t.rchild)

def InOrder(bt): #中序遍历的递归算法
t=bt.root
if t is not None:
_InOrder(t)

def _InOrder(t): #被InOrder方法调用
if t.lchild is not None:
_InOrder(t.lchild)
print(t.data,end=' ')
if t.rchild is not None:
_InOrder(t.rchild)

def PostOrder(bt): #后序遍历的递归算法
t=bt.root
if t is not None:
_PostOrder(t)

def _PostOrder(t): #被PostOrder方法调用
if t.lchild is not None:
_PostOrder(t.lchild)
if t.rchild is not None:
_PostOrder(t.rchild)
print(t.data,end=' ')

def LevelOrder(bt): #层次遍历的算法
t=bt.root
if t is None:
return
q=deque()
q.append(t)
while len(q)>0:
x=q.popleft()
print(x.data,end=' ')
if x.lchild is not None:
q.append(x.lchild)
if x.rchild is not None:
q.append(x.rchild)

def CreateBTree2(posts,ins): #由后序序列posts和中序序列ins构造二叉链
n=len(posts)
return _CreateBTree2(posts,0,ins,0,n)

def _CreateBTree2(posts,i,ins,j,n): #被CreateBTree2方法调用
if n<=0 or i>=n or j>=n:
return None
t=BTNode(posts[i])
k=j
while k<j+n and ins[k]!=posts[i]:
k+=1
t.lchild=_CreateBTree2(posts,i+n-k+j,k-n+j,ins,j,k-j)
t.rchild=_CreateBTree2(posts,i-1,k+1,ins,k+1,j+n-k-1)
return t

#主程序
ins=[......]
posts=[......]
print()
print(" 中序:",end=' '); print(ins)
print(" 后序:",end=' '); print(posts)
print(" 构造二叉树bt")
bt=BTree()
bt.root=CreateBTree2(posts,len(posts)-1,ins,0,len(ins))
print(" bt:",end=' '); print(bt.DispBTree())
x=值
p=bt.FindNode(x)
if p is not 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()