python数据结构（树和二叉树）

树

非线性结构 一对多

根结点（无前驱）

多个叶子结点（无后继）

其他数据元素（一个前驱，多个后驱）

树与二叉树转换

树与二叉树均可用二叉链表作为存储结构，则以二叉链表为媒介可导出树之间的一个对应关系-----即给定一颗树，可以找到唯一一颗二叉树与之对应。

把树转化为二叉树

步骤一：加线。在各亲兄弟之间加一虚线

步骤二：抹线。抹掉（除第一个孩子外）该结点到其余孩子之间的连线。

步骤三：旋转。新加上去的虚线改实线且向右斜，原有的连线均向左斜，使之结构层次分明。

把二叉树转化为树

前提条件：二叉树的根节点无左右孩子。

步骤一：加线。若某节点i是双亲节点的左孩子，则将该结点的右孩子以及当且仅当连续地沿着此右孩子的右链不断搜索到的所有右孩子都分别与结点i的双亲用虚线连起来。

步骤二：抹线。抹掉原二叉树中所有双亲结点与右孩子的连线。

步骤三：归整化。将图形归整化，使各结点按层次排列且将加上去的虚线变成实线。

树的概览

结点的度：分支的个数

树和度：树中所有结点的度的最大值

叶子结点：度为零的结点

分支结点：度大于零的结点

孩子结点：结点子树的根称为该结点的双孩子

双亲结点：孩子结点的上层结点叫该结点的双亲 （父节点）

兄弟结点：同一双亲的孩子

结点的层次：根结点的层次为1，第i层的结点的子树的根结点的层次为i+1

树的深度：树中叶子结点所在的最大层次。

二叉树

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。

并且二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分！

二叉树创建

def createBiTree(self,root):
    data=input()
    if data is "#":
      return None
    else:
      root.data=data
      root.lchild=self.createBiTree(root.lchild)   #一个一个结点放上去
      root.rchild=self.createBiTree(root.rchild)
    return root

具有四种基本形态

空树、只有左子树、只有右子树、同时有左右子树

满二叉树

深度为k且含有（2的k次方减一）个结点的二叉树。

特点：

每一层上都含有最大结点数。

结点编号：从上到下，从左到右按自然数编号。

完全二叉树

深度为k的二叉树中所含的n个结点和深度为k的满二叉树中编号为1至n的结点一一对应。

特点：

1.除最后一层外，每一层都取最大结点数，最后一层结点都集中且连续分布在该层最左边的若干位置。

2.叶子结点只可能在层次最大的两层出现。

3.对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为L或L+1。

注意：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树！