前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
中序遍历：若树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历右子树。
后序遍历：若树为空，则空操作返回，否则从左到右先访问叶子结点后结点的方式遍历左右子树，最后访问根节点。
层序遍历：若树为空，则空操作返回，否则从树的每一层，即从根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
假设已知后序遍历和中序遍历结果，从后序遍历的结果可以等到最后一个访问的结点是根节点，对于最简单的二叉树，此时在中序遍历中找到根节点之后，可以分辨出左右子树，这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树，重建得到根结点和暂时混乱的左右结点，通过递归将左右结点依次重建为子二叉树，即可完成整个二叉树的重建。（在得到根结点之后，需要在中序遍历序列中寻找根结点的位置，并将中序序列拆分为左右部分，所以要求序列中不能有相同的数字，这是序列重建为二叉树的前提。）
Root =None
strs="abc##d##e##" #前序遍历扩展的二叉树序列
vals =list(strs)
Roots=Create_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
print(Roots)
inorderSearch = inOrderTraverse2(Roots)
print(inorderSearch)
用python构造一个n层的完全二叉树的代码如下：typedef struct {
int weight
int parent, lchild, rchild
} HTNode ,*HuffmanTree // 动态分配数组存储huffman树
算法设计
void createHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode)// 动态分配数组存储huffman树,0号单元未用
// m:huffman 树中的结点数（m=2*n-1）
for (i=1i<=m++i)
ht[i].parent= ht[i]->lch= ht[i]->rch=0
for (i=1i<=n++i)
ht[i].weight=w[i] //初始化，w[i]：n个叶子的权值
for (i=n+1i<=m,++i) ｛ //建哈夫曼树
select(i-1),s1,s2) //在ht[k](1<=k<=i-1)中选择两个双亲域为零而权值取最小的结点 :s1和s2
ht[s1].parent= ht[s2].parent=i
ht[i].lch=s1
ht[i].rch=s2
ht[i].weight=ht[s1].weight + ht[s2].weight
}
}
