二叉树:
class bitree:
def __init__(self,data):
self.data=data
self.lchild=None
self.rchild=None
a=bitree('A')
b=bitree('B')
c=bitree('C')
d=bitree('D')
e=bitree('E')
f=bitree('F')
g=bitree('G')
e.rchild=a
e.lchild=g
a.rchild=c
c.lchild=b
c.rchild=d
g.rchild=f
root=e#根节点
print(root.lchild.rchild.data)
class bitree:
def __init__(self,data):
self.data=data
self.lchild=None
self.rchild=None
a=bitree('A')
b=bitree('B')
c=bitree('C')
d=bitree('D')
e=bitree('E')
f=bitree('F')
g=bitree('G')
e.rchild=g
e.lchild=a
a.rchild=c
c.lchild=b
c.rchild=d
g.rchild=f
root=e#根节点
print(root.lchild.rchild.data)
#前序遍历
def pre_order(root):
if root is not None:
print(root.data,end=',')
pre_order(root.lchild)
pre_order(root.rchild)
pre_order(root)
#中序遍历
def in_order(root):
if root is not None:
in_order(root.lchild)
print(root.data,end=',')
in_order(root.rchild)
in_order(root)
#后序遍历
def post_order(root):
if root is not None:
post_order(root.lchild)
post_order(root.rchild)
print(root.data,end=',')
post_order(root)
#层次遍历
def level_order(root):
queue=deque()
queue.append(root)
while len(queue)>0:#只要队不空
node=queue.popleft()
print(node.data,end=',')
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
level_order(root)
二叉搜索树的中序遍历的结果是有序的(重点重点,leetcode有些题要用这个)
二叉树插入:
class bitree:
def __init__(self,data):
self.data=data
self.lchild=None
self.rchild=None
self.parent=None
class bst:
def __init__(self,li=None):
self.root=None
if li:
for val in li:
self.ii(val)
def insert(self,node,val):#node是节点
if node is None:
node=bitree(val)
elif valnode.data:
noed.rchild=self.insert(node.rchild,val)
node.rchild.parent=node
return node
def ii(self,val):
p=self.root
if not p:#空树
self.root=bitree(val)
return
while 1:
if val < p.data:
if p.lchild:
p=p.lchild
else:#左子树不存在
p.lchild=bitree(val)
p.lchild.parent=p
return
elif val>p.data:
if p.rchild:
p=p.rchild
else:#左子树不存在
p.rchild=bitree(val)
p.rchild.parent=p
return
else:
return
'''
def pre_order(self,root):
if root is not None:
print(root.data,end=',')
self.pre_order(root.lchild)
self.pre_order(root.rchild)
tree=bst([4,6,7,9,2,1,3,5,8])
tree.pre_order(tree.root)
print('')
查找:
def query(self,node,val):
if node is None:
return None
if node.data val:
return self.query(node.lchild.val)
else:
return node
def query_no(self,val):
p=self.root
while p:
if p.dataval:
p=p.lchild
else:
return p
tree=bst([4,6,7,9,2,1,3,5,8])
print(tree.query_no(4).data)
删除:
def __remove_node_1(self,node):#情况一
if node.parent is None:
self.root=None
if node==node.parent.lchild:#node是它父亲的做孩子
node.parent.lchild=None
else:
node.parent.rchild=None
def __remove_node_21(self,node):#情况二:node只有一个左孩子
if not node.parent:
self.root=node.lchild
node.lchild.parent=None
elif node==node.parent.lchild:
node.parent.lchild=node.lchild
node.lchild.parent=node.parent
else:
node.parent.rchild=node.lchild
node.lchild.parent=node.parent
def __remove_node_22(self,node):#node只有一个右孩子
if not node.parent:
self.root=node.rchild
elif node==node.parent.lchild:
node.parent.lchild=node.rchild
node.rchild.parent=node.parent
else:
node.parent.rchild=node.rchild
node.rchild.parent=node.parent
def delete(self.val):
if self.root:#不是空树
node=self.query_no(val)
if not node:
return False
if not node.lchild and not node.rchild:
self.__remove_node_1(node)
elif not node.rchild:#只有一左孩子
self.__remove_node_21(node)
elif not node.lchild:
self.__remove_node_22(node)
else:#两个孩子都有
min_node=node.rchild
while min_node.lchild:
min_node=min_node.lchild
node.data=min_mode.data
#删除min_node
if min_node.rchild:
self.__remove_node_22(node)
else:
self.__remove_node_1(node)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)