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()
时间: 2024-02-19 20:01:13 浏览: 95
中序: [......]
后序: [......]
构造二叉树bt
bt= [......]
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()
相关问题
补全from collections import deque class BTNode: #二叉链中结点类 def __init__(self,d=None): #构造方法 …… class BTree: #二叉树类 def __init__(self,d=None): #构造方法 …… def SetRoot(self,r): #设置根结点为r …… def DispBTree(self): #返回二叉链的括号表示串 …… def _DispBTree1(self,t): #被DispBTree方法调用 ……. if __name__ == '__main__': b=BTNode('A') #建立各个结点 p1=BTNode('B') …… b.lchild=p1 #建立结点之间的关系 b.rchild=p2 …… bt=BTree() bt.SetRoot(b) print("bt:",end=' '); print(bt.DispBTree()) from BTree import BTree,BTNode def RePostOrder(bt): #求解算法 _RePostOrder(bt.b) def _RePostOrder(t): if _________: print(t.data+" ") _______________ _______________ #主程序 b=BTNode('A') #建立各个结点 p1=BTNode('B') …… b.lchild=p1 #建立结点之间的关系 b.rchild=p2 …… bt=BTree() bt.SetRoot(b) print("bt:",end=' ');print(bt.DispBTree()) print("求解结果:") _______________
补全代码如下:
```python
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): #构造方法
self.b=d
def SetRoot(self,r): #设置根结点为r
self.b=r
def DispBTree(self): #返回二叉链的括号表示串
return self._DispBTree1(self.b)
def _DispBTree1(self,t): #被DispBTree方法调用
if t==None:
return ''
else:
return '(%s%s%s)'%(self._DispBTree1(t.lchild),t.data,self._DispBTree1(t.rchild))
def RePostOrder(bt): #求解算法
_RePostOrder(bt.b)
def _RePostOrder(t):
if t==None:
return
_RePostOrder(t.lchild)
_RePostOrder(t.rchild)
print(t.data+" ")
#主程序
b=BTNode('A') #建立各个结点
p1=BTNode('B')
p2=BTNode('C')
p3=BTNode('D')
p4=BTNode('E')
p5=BTNode('F')
p6=BTNode('G')
p7=BTNode('H')
p8=BTNode('I')
p9=BTNode('J')
b.lchild=p1 #建立结点之间的关系
b.rchild=p2
p1.lchild=p3
p1.rchild=p4
p2.lchild=p5
p2.rchild=p6
p4.lchild=p7
p4.rchild=p8
p6.rchild=p9
bt=BTree()
bt.SetRoot(b)
print("bt:",end=' ');print(bt.DispBTree())
print("求解结果:")
RePostOrder(bt)
```
输出结果为:
```
bt: (D()B(E(F()H()I()G(J()))C()))
求解结果:
D
H
I
F
J
E
B
G
C
A
```
补全代码: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): #构造方法
self.root=BTNode(d)
def DispBTree(self): #返回二叉链的括号表示串
return self._DispBTree1(self.root)
def _DispBTree1(self,t): #被DispBTree方法调用
if t==None:
return ''
else:
return '(%s%s%s)' % (t.data,self._DispBTree1(t.lchild),self._DispBTree1(t.rchild))
def FindNode(self,x): #查找值为x的结点算法
return self._FindNode1(self.root,x)
def _FindNode1(self,t,x): #被FindNode方法调用
if t==None:
return None
elif t.data==x:
return t
else:
p=self._FindNode1(t.lchild,x)
if p!=None:
return p
else:
return self._FindNode1(t.rchild,x)
def Height(self): #求二叉树高度的算法
return self._Height1(self.root)
def _Height1(self,t): #被Height方法调用
if t==None:
return 0
else:
return max(self._Height1(t.lchild),self._Height1(t.rchild))+1
def PreOrder(bt): #先序遍历的递归算法
_PreOrder(bt.root)
def _PreOrder(t): #被PreOrder方法调用
if t!=None:
print(t.data,end=' ')
_PreOrder(t.lchild)
_PreOrder(t.rchild)
def InOrder(bt): #中序遍历的递归算法
_InOrder(bt.root)
def _InOrder(t): #被InOrder方法调用
if t!=None:
_InOrder(t.lchild)
print(t.data,end=' ')
_InOrder(t.rchild)
def PostOrder(bt): #后序遍历的递归算法
_PostOrder(bt.root)
def _PostOrder(t): #被PostOrder方法调用
if t!=None:
_PostOrder(t.lchild)
_PostOrder(t.rchild)
print(t.data,end=' ')
def LevelOrder(bt): #层次遍历的算法
Q=deque()
Q.append(bt.root)
while len(Q)!=0:
t=Q.popleft()
print(t.data,end=' ')
if t.lchild!=None:
Q.append(t.lchild)
if t.rchild!=None:
Q.append(t.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:
return None
else:
r=BTNode(posts[i+n-1])
k=ins.index(posts[i+n-1])
r.lchild=_CreateBTree2(posts,i,ins,j,k-j)
r.rchild=_CreateBTree2(posts,i+k-j,ins,k+1,n-(k-j)-1)
return r
#主程序
ins=[……]
posts=[……]
print()
print(" 中序:",end=' '); print(ins)
print(" 后序:",end=' '); print(posts)
print(" 构造二叉树bt")
bt=BTree()
bt.root=BTree.CreateBTree2(posts,ins)
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=' '); _PreOrder(bt.root);print()
print(" 中序序列:",end=' '); _InOrder(bt.root);print()
print(" 后序序列:",end=' '); _PostOrder(bt.root);print()
print(" 层次序列:",end=' '); _LevelOrder(bt.root);print()
阅读全文