介绍：树形结构是应用相当广泛的一种非线性结构，建立与应用大多使用链表来处理，当然也可用连续的列表来实现
常见概念：
满二叉树：如果树高位H，树的结点总数为2*H-1，H>=0,称为满二叉树
完全二叉树：高度为H，节点数小于2*H-1，但节点的编号方式与满二叉树一致
斜二叉树：当一个二叉树完全没有左节点或者右节点的时候，称为左斜二叉树或者右斜二叉树
严格二叉树：每一个非终端的节点均有非空的左右子树
1.用数组实现二叉树
规则：左子树的节点索引值是父节点索引值乘2
右子树的节点索引值是父节点索引值乘2加1
每一个树根的值大于左子树值小于友子树值
创建函数：
def Betree(betree,data,length): for i in range(1,length): level = 1 while betree[level] != 0: if betree[level] > data[i]: level = level*2 else: level = level*2+1 betree[level] = data[i] return betree
2.链表实现二叉树
有点：节点的增加和删除容易实现，缺点：很难找到父节点
class tree: def __init__(self): self.data=0 self.left=None self.right=None
def creat_tree(root,val):
newnode=tree()
newnode.data=val
newnode.left=None
newnode.right=None
if root==None:
root=newnode
return root
else:
current=root
while current != None:
backup = current
if current.data > val:
current=current.left
else:
current=current.right
if backup.data > val:
backup.left = newnode
else:
backup.right = newnode
3.二叉树遍历
三种遍历方法：
#中序遍历 def inorder(ptr): if ptr != None: inorder(ptr.left) print("%4d"%ptr.data,end="") inorder(ptr.right) print() #后序遍历 def postorder(ptr): if ptr != None: postorder(ptr.left) postorder(ptr.right) print("%4d"%ptr.data,end="") print() #前序遍历 def preorder(ptr): if ptr != None: print("%4d"%ptr.data,end="") preorder(ptr.left) preorder(ptr.right)
4.二叉树节点查找
原则：从树根出发进行比较，如果小于树根，左子树查找，大于树根，右子树查找，找到要查找的值
def search(ptr,val): while True: if ptr == None: return None if ptr.data == val: return ptr else: if ptr.data > val: ptr = ptr.left else: ptr = ptr.right
5.二叉树节点的删除
a.删除的节点位叶子，只需将与其相连的父节点指向None
b.删除节点只有一棵子树，将其子树移到该节点的父节点指向
c.删除节点有左右两个子树，将左右子树中值较大的子树移到该结点处
原文：https://www.cnblogs.com/wxw9280/p/12552000.html