一. 二叉树构建以及遍历
1.构建结点
二叉树的结点Node有数据域，左孩子和右孩子三部分。
class Node(object):
def __init__(self,item):
self.elem = item
self.lchild = None
self.rchild = None
2.利用上面的结点构建一个树类
class Tree(object):
def __init__(self):
self.root = None
树添加结点的方法
def add(self,item):
"""
param: item 是传进来来的数据,我们要实例化一个结点取接收他,但是他的位置要放在树梢,不能乱插入
queue 我们创建一个队列来接收和弹出结点,这样我们找到结点需要接收的位置
"""
node = Node(item)
if self.root is None：
"""如果根结点是None,是一颗空数,我们就把node赋值给root,那么下面的while循环是不会受影响的,因为是队列[None]的bool值是True"""
self.root = node
return
#把要遍历的结点加入queue队列中
queue = [self.root]
while queue:
#队列的弹出要加0，与栈相仿
cur_node = queue.pop(0)
if cur_node.lchild is None:
#这里有空位，插入结点
cur_node.lchild = node
else:
#cur_node的做孩子放进队列中，下次循环左子结点
queue.append(cur_node.lchild)
#同理对于右边的操作
if cur_node.rchild is None:
cur_node.rchild = node
else:
queue.append(cur_node.rchild)
广度遍历 —— 层序遍历
递归版
def levelOrder(self,root):
def helper(node,level):
if not node:
return
else:
sol[level-1].append(node.val)
if len(sol) == level: #遍历到新层时，只有最左边的结点使得等式成立
sol.append([])
helper(node.lchild,level+1)
helper(node.rchild,level+1)
sol = [[]]
helper(root,1)
return sol[:-1]
循环版
def breadth_travel(self):
"""广度遍历与结点的添加非常相似,广度遍历不用插入结点了,在循环里面的条件和添加的相仿"""
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
# 我们打印看看结点的遍历顺序对不对
print(cur_node.elem)
if cur_node.lchild is not None:
# 扔进队列循环
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
深度遍历：前序，中序，后序
递归版
#先序遍历 根左右
def preOrder(self,node):
if self.root is None:
return
print(node.elem)
self.preOrder(node.lchild)
self.preOrder(node.rchild)
#中序遍历 左根右
def middleOrder(self,node):
if self.root is None:
return
self.preOrder(node.lchild)
print(node.elem)
self.preOrder(node.rchild)
#后序遍历 左右根
def lastOrder(self,node):
if self.root is None:
return
self.preOrder(node.lchild)
self.preOrder(node.rchild)
print(node.elem)
循环版 —— 使用栈遍历二叉树
def front(self):
"""堆栈前序遍历"""
if not self.root:
return
tmp_stack = []
node = self.root
while tmp_stack or node:
while node:
print(node.data)
tmp_stack.append(node)
node = node.left_child
node = tmp_stack.pop()
node = node.right_child
def middle(self):
"""堆栈中序遍历"""
if not self.root:
return
tmp_stack = []
node = self.root
while tmp_stack or node:
while node:
tmp_stack.append(node)
node = node.left_child
node = tmp_stack.pop()
print(node.data)
node = node.right_child
def last(self):
"""堆栈后序遍历，较难"""
if not self.root:
return
tmp_node = self.root
tmp_stack = []
while tmp_node or tmp_stack:
while tmp_node:
tmp_stack.append(tmp_node)
tmp_node = tmp_node.left_child or tmp_node.right_child
tmp_node = tmp_stack.pop()
print(tmp_node.data)
if tmp_stack and tmp_stack[-1].left_child is tmp_node:
tmp_node = tmp_stack[-1].right_child
else:
tmp_node = None
def lastSimpleV(self,root):
stack = []
sol = [] #保存打印输出结果的列表
curr = root
while stack or curr:
if curr:
sol.append(curr.data)
stack.append(curr.left_child)
curr = curr.right_child
else:
curr = stack.pop()
return sol[::-1] #反向打印结果
二 链表的创建及相关操作
1.定义一个单链表结点类
class Node(object):
def __init__(self,data):
self.data = data
self.next = None
2.方法
#判断是否为空
def isEmpty(self):
return (self.length ==0)
#增加一个结点,增加之后 要把链表长度加一
def append(self,dataOrNode):
item = None
if isinstance(dataOrNode,Node):
#如果是结点的话
item = dataOrNode
else:
item = Node(dataNode)
if not self.head:
#如果头结点为空的话直接插入
self.head = item
self.length += 1
else:
node = self.head
while node.next:
node = node.next
node.next = item
self.length += 1
#删除一个结点,删除结点之后要把链表长度减
def delete(self,index):
if self.isEmpty():
print("this chain table is empty")
return
if index<0 or index>=self.length:
print("error:out of index")
return
#删除第一个结点
if index==0:
self.head = self.head.next
self.length -= 1
return
#prev为保存前驱结点
#node为保存当前结点
#当j与index相等时就，相当于找到要删除的节点
j = 0
node = self.head
prev = self.head
while node.next and j<index:
prev = node
node = node.next
j+=1
if j==index:
prev.next = node.next
self.length -= 1
#更新结点值
def update(self,index,data):
if self.isEmpty() or index <0 or index>=self.length:
return
j = 0
node = self.head
while node.next and j<index:
node = node.next
j += 1
if j == index:
node.data = data
三 图的创建以及深度广度遍历
