分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 

完全二叉树是一种效率很高的数据结构，堆就是一种完全二叉树，效率极高。像十分常用的排序算法、Dijkstra算法、Prim算法等等都要用堆才能优化；经常提到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

 

完全二叉树（CompleteBinaryTree）的定义

若设二叉树的高度为h，除第h层外，其它各层（1～h-1）的结点数都达到最大个数，且第h层所有的节点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。

 

完全二叉树的特点

叶子结点只可能在最下面的两层上出现，对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1；

出于简便起见，完全二叉树通常采用数组而不是链表存储，其存储结构如下:

vartree:array[1...n]ofobject;{n:integer;n>=1}

对于tree，有如下特点：

（1）若i为奇数且i>1，那么tree[i]的左兄弟为tree[i-1]；

（2）若i为偶数且i

（3）若i>1，tree[i]的双亲为tree[idiv2]；

（4）若2*i<=n，那么tree[i]的左孩子为tree[2*i]；若2*i+1<=n，那么tree[i]的右孩子为tree[2*i+1]；

（5）若i>n/2，那么tree[i]为叶子结点（对应于（3））；

（6）若i<(n-1)/2，那么tree必有两个孩子（对应于（4））；

（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；

（8）完全二叉树第i层至多有2^(i-1)个节点，共i层的完全二叉树最多有2^i-1个节点。

 

完全二叉树叶子结点数的算法

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，而n=n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n=2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2，就可根据完全二叉树的结点总数计算出叶子结点数。

 

完全二叉树的性质

具有n个结点的完全二叉树的深度为floor(log2n)+1或ceil(log2(n+1))。

证明：设所求完全二叉树的深度为k。

由完全二叉树定义可得：

深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2^(k-1)-1个结点。

由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：n>2^(k-1)-1。

由二叉树的性质可知：n≤2^(k)-1，即：2^(k-1)-1

由此可推出：2^(k-1)<≤n≤2k，取对数后有：k-1

由于k-1和k是相邻的两个整数，故有k-1=floor(log2n)，由此即得：k=floor(log2n)+1。



#coding:utf-8

'BiTree'

class Node(object):

  'Node Defination'

  def __init__(self,item):

    self.item = item

    self.left = None

    self.right = None

class Tree(object):

  'Bitree Defination'

  def __init__(self):

    self.root = None

  def add(self,item):

    node = Node(item)

    if self.root is None:

      self.root = node

    else:

      q = [self.root]

      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 traverse(self):#层次遍历

    if self.root is None:

      return None

    q = [self.root]

    res = [self.root.item]

    while q != []:

      pop_node = q.pop(0)

      if pop_node.left is not None:

        q.append(pop_node.left)

        res.append(pop_node.left.item)

      if pop_node.right is not None:

        q.append(pop_node.right)

        res.append(pop_node.right.item)

    return res

  def preorder(self,root): #先序遍历

    if root is None:

      return []

    result = [root.item]

    left_item = self.preorder(root.left)

    right_item = self.preorder(root.right)

    return result + left_item + right_item

  def inorder(self,root): #中序遍历

    if root is None:

      return []

    result = [root.item]

    left_item = self.inorder(root.left)

    right_item = self.inorder(root.right)

    return left_item + result + right_item

  def postorder(self,root): #后序遍历

    if root is None:

      return []

    result = [root.item]

    left_item = self.postorder(root.left)

    right_item = self.postorder(root.right)

    return left_item + right_item + result

if __name__=='__main__':

  t = Tree()

  for i in range(10):

    t.add(i)

  print "层序遍历:",t.traverse()

  print "先序遍历:",t.preorder(t.root)

  print "中序遍历:",t.inorder(t.root)

  print "后序遍历:",t.postorder(t.root)

 pop_node = q.pop(0)

其中  q为python的列表     

pop(0)指的是弹出里面的第一个元素

二叉树基本概述：

二叉树是有限个元素的几个，如果为空则为空二叉树，或者有一个结点称之为根节点，分列根节点两侧的为二叉树的左右子节点，二叉树有如下的性质：

1. 二叉树的每个结点不存在度大于2的结点
2. 二叉树的第i层至多有2^{i-1}个结点
3. 深度为k的二叉树至多有2^k - 1个结点
4. 二叉树中，度为0的结点数N0比度为2的结点数N2大1，即存在N2 + 1 = N0

Python代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#coding:utf-8 'BiTree' class Node(object):   'Node Defination'   def __init__(self,item):     self.item = item     self.left = None     self.right = None class Tree(object):   'Bitree Defination'   def __init__(self):     self.root = None   def add(self,item):     node = Node(item)     if self.root is None:       self.root = node     else:       q = [self.root]       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 traverse(self):#层次遍历     if self.root is None:       return None     q = [self.root]     res = [self.root.item]     while q != []:       pop_node = q.pop(0)       if pop_node.left is not None:         q.append(pop_node.left)         res.append(pop_node.left.item)       if pop_node.right is not None:         q.append(pop_node.right)         res.append(pop_node.right.item)     return res   def preorder(self,root): #先序遍历     if root is None:       return []     result = [root.item]     left_item = self.preorder(root.left)     right_item = self.preorder(root.right)     return result + left_item + right_item   def inorder(self,root): #中序遍历     if root is None:       return []     result = [root.item]     left_item = self.inorder(root.left)     right_item = self.inorder(root.right)     return left_item + result + right_item   def postorder(self,root): #后序遍历     if root is None:       return []     result = [root.item]     left_item = self.postorder(root.left)     right_item = self.postorder(root.right)     return left_item + right_item + result if __name__=='__main__':   t = Tree()   for i in range(10):     t.add(i)   print "层序遍历:",t.traverse()   print "先序遍历:",t.preorder(t.root)   print "中序遍历:",t.inorder(t.root)   print "后序遍历:",t.postorder(t.root)

输出结果：

层序遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先序遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中序遍历: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后序遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]

这里对于

1 2	if __name__=='__main__': “Make a script both importable and executable”

意思就是说让你写的脚本模块既可以导入到别的模块中用，另外该模块自己也可执行。

这里通过一个示例进行解释：

1 2 3 4 5

#test.py def func():  print "we are in %s"%__name__ if __name__ == '__main__':  func()