欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python学习——二叉树遍历

程序员文章站 2022-03-22 22:25:40
import os,sysclass node: def __init__(self,item): self.num=item self.lchild=None self.rchild=Noneclass tree: def __init__(self): self.root=None def ad ......
import os,sys

class node:
def __init__(self,item):
self.num=item
self.lchild=None
self.rchild=None

class tree:
def __init__(self):
self.root=None

def add(self,ii):
inode = node(ii)
if self.root is None:
self.root=inode
else:
p=[self.root]
iipp=0
while 1:
ip=p[iipp]
#print ip
iipp=iipp+1
if ip.lchild is None:
ip.lchild=inode
return
elif ip.rchild is None:
ip.rchild = inode
return
else:
p.append(ip.lchild)
p.append(ip.rchild)

def lorder(self,node1):
l=[]
if node1 is not None:
l.append(node1.num)
ll= self.lorder(node1.lchild)
l=l+ll
#l.append(ll)#带结构
rl = self.lorder(node1.rchild)
#l.append(rl)#带结构
l=l+rl
return l

def morder(self,node2):
m = []
if node2 is not None:
lm = self.morder(node2.lchild)
m = m + lm
m.append(node2.num)
rm = self.morder(node2.rchild)
m = m + rm
return m

def rorder(self,node3):
r = []
if node3 is not None:
lr = self.rorder(node3.lchild)
r = r + lr
rr = self.rorder(node3.rchild)
r = r + rr
r.append(node3.num)
return r

if __name__ == '__main__':
t=tree()
for i in range(1,10):
t.add(i)
print t.lorder(t.root)#先序遍历
print t.morder(t.root)#中序遍历
print t.rorder(t.root)#后序遍历