1377-王同学

,

# 搜索

## 二分法查找

def binary_search(alist,item):
"""二分查找,递归版"""
n = len(alist)
if n > 0:
mid = n // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search(alist[:mid],item)
else:
return binary_search(alist[mid+1:], item)
return False

def binary_search_2(alist, item):
"""二分查找，非递归版"""
n = len(alist)
first = 0
last = n-1
while first <= last:
mid = (last + first) // 2
if alist[mid] == item:
return True
elif alist[mid] < item:
first = mid + 1
else:
last = mid - 1
return False


# 二叉树

## 二叉树的性质(特性)

### 完全二叉树

class Node(object):
# 建立二叉树节点
def __init__(self, item):
self.elem = item
self.lchild = None
self.rchild = None

class Tree(object):
def __init__(self):
self.root = None

# 二叉树添加元素
node = Node(item)
li = [self.root]
if self.root is None:
self.root = node
return
while li:
cur_node = li.pop(0)
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
li.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
li.append(cur_node.rchild)


## 二叉树的遍历

### 广度遍历

 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)


### 深度遍历

1） 先序遍历

    def preorder(self, node):
"""先序遍历"""
if node is None:
return
print(node.elem, end=' ')
self.preorder(node.lchild)
self.preorder(node.rchild)


2） 中序遍历

  def inorder(self,node):
"""中序遍历"""
if node is None:
return
self.inorder(node.lchild)
print(node.elem, end=' ')
self.inorder(node.rchild)


3）后序遍历

 def postorder(self,node):
"""后序遍历"""
if node is None:
return
self.postorder(node.lchild)
self.postorder(node.rchild)
print(node.elem, end=' ')


Vieu3.3主题

Q Q 登 录