求下列代码的每种算法的时间和空间复杂度
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=None
def SetRoot(self,r):
self.b=r
def DispBTree(self):
return self._DispBTree1(self.b)
def _DispBTree1(self,t):
if t==None:
return ""
else:
bstr=t.data
if t.lchild!=None or t.rchild!=None:
bstr+="("
bstr+=self._DispBTree1(t.lchild)
if t.rchild!=None:
bstr+=","
bstr+=self._DispBTree1(t.rchild)
bstr+=")"
return bstr
def FindNode(self,x): #查找值为x的结点算法
return self._FindNode1(b,x)
def _FindNode1(self,t,x):
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(b)
def _Height1(self,t):
if t==None:
return 0
else:
lh=self._Height1(t.lchild)
rh=self._Height1(t.rchild)
return max(lh,rh)+1
def PreOrder(bt): #先序遍历
PreOrder1(bt.b)
def PreOrder1(t):
if t!=None:
print(t.data,end=' ')
PreOrder1(t.lchild)
PreOrder1(t.rchild)
def InOrder(bt): #中序遍历
InOrder1(bt.b)
def InOrder1(t):
if t!=None:
InOrder1(t.lchild)
print(t.data,end=' ')
InOrder1(t.rchild)
def PostOrder(bt): #后序遍历
PostOrder1(bt.b)
def PostOrder1(t):
if t!=None:
PostOrder1(t.lchild)
PostOrder1(t.rchild)
print(t.data,end=' ')
def LevelOrder(bt): #层次遍历
qu=deque()
qu.append(bt.b)
while len(qu)>0:
p=qu.popleft()
print(p.data,end=' ')
if p.lchild!=None:
qu.append(p.lchild)
if p.rchild!=None:
qu.append(p.rchild)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=None
def SetRoot(self,r):
self.b=r
def DispBTree(self):
return self._DispBTree1(self.b)
def _DispBTree1(self,t):
if t==None:
return ""
else:
bstr=t.data
if t.lchild!=None or t.rchild!=None:
bstr+="("
bstr+=self._DispBTree1(t.lchild)
if t.rchild!=None:
bstr+=","
bstr+=self._DispBTree1(t.rchild)
bstr+=")"
return bstr
def FindNode(self,x): #查找值为x的结点算法
return self._FindNode1(b,x)
def _FindNode1(self,t,x):
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(b)
def _Height1(self,t):
if t==None:
return 0
else:
lh=self._Height1(t.lchild)
rh=self._Height1(t.rchild)
return max(lh,rh)+1
def PreOrder(bt): #先序遍历
PreOrder1(bt.b)
def PreOrder1(t):
if t!=None:
print(t.data,end=' ')
PreOrder1(t.lchild)
PreOrder1(t.rchild)
def InOrder(bt): #中序遍历
InOrder1(bt.b)
def InOrder1(t):
if t!=None:
InOrder1(t.lchild)
print(t.data,end=' ')
InOrder1(t.rchild)
def PostOrder(bt): #后序遍历
PostOrder1(bt.b)
def PostOrder1(t):
if t!=None:
PostOrder1(t.lchild)
PostOrder1(t.rchild)
print(t.data,end=' ')
def LevelOrder(bt): #层次遍历
qu=deque()
qu.append(bt.b)
while len(qu)>0:
p=qu.popleft()
print(p.data,end=' ')
if p.lchild!=None:
qu.append(p.lchild)
if p.rchild!=None:
qu.append(p.rchild)
