树 (tree) 是一种非常高效的非线性存储结构。树，可以很形象的理解，有根，有叶子，对应在数据结构中就是根节点、叶子节点，同一层的叶子叫兄弟节点，邻近不同层的叫父子节点。
* 二叉树，就是每个节点都至多有二个子节点的树。
* 满二叉树，就是除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。
* 完全二叉树，就是叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
二叉树的具体功能实现
1. 先定义一个节点 node 类，存储数据 data 和左子节点 left 以及 右子节点 right。
2. 再实现二叉树 binary_tree 的类，应至少有以下属性和函数： 属性：有一个根节点（root) , 它是 node 类。 函数：添加子节点 add ，返回父节点 get_parent，删除子节点 delete。
class Node(object): #创建Node类
def __init__(self, item):
self.item = item #表示对应的元素
self.left = None #表示左子节点
self.right = None #表示右子节点
def __str__(self):
return str(self.item) #print 一个 Node 类时会打印 __str__ 的返回值
class Tree(object): #创建Tree类 定义根节点
def __init__(self):
self.root = Node(\'root\') #根节点定义为 root 永不删除，作为哨兵使用
def add(self, item): #add() 添加子节点到树里
node = Node(item)
if self.root is None: #如果二叉树为空，那么生成的二叉树最终为新插入树的点
self.root = node
else:
q = [self.root]
# 将q列表，添加二叉树的根节点
while True:
pop_node = q.pop(0)
if pop_node.left is None: #左子树为空则将点添加到左子树
pop_node.left = node
return
elif pop_node.right is None: #右子树为空则将点添加到右子树
pop_node.right = node
return
else:
q.append(pop_node.left)
q.append(pop_node.right)
def get_parent(self, item): #找到item的父节点
if self.root.item == item:
return None # 根节点没有父节点
tmp = [self.root] # 将tmp列表，添加二叉树的根节点
while tmp:
pop_node = tmp.pop(0)
if pop_node.left and pop_node.left.item == item: #某点的左子树为寻找的点
return pop_node #返回某点，即为寻找点的父节点
if pop_node.right and pop_node.right.item == item: #某点的右子树为寻找的点
return pop_node #返回某点，即为寻找点的父节点
if pop_node.left is not None: #添加tmp 元素
tmp.append(pop_node.left)
if pop_node.right is not None:
tmp.append(pop_node.right)
return None
def delete(self, item):
if self.root is None:
return False
parent = self.get_parent(item)
if parent:
del_node = parent.left if parent.left.item == item else parent.right #待删除节点
if del_node.left is None:
if parent.left.item == item:
parent.left = del_node.right
else:
parent.right = del_node.right
del del_node
return True
elif del_node.right is None:
if parent.left.item == item:
parent.left = del_node.left
del del_node
return True
else:
tmp_pre = del_node
tmp_next = del_node.right
if tmp_next.left is None:
tmp_pre.right = tmp_next.right
tmp_next.left = del_node.left
tmp_next.right = del_node.right
else:
while tmp_next.left:
tmp_pre = tmp_next
tmp_next = tmp_next.left
tmp_pre.left = tmp_next.right
tmp_next.left = del_node.left
tmp_next.right = del_node.right
if parent.left.item == item:
parent.left = tmp_next
else:
parent.right = tmp_next
del del_node
return True
else:
return False
