n0+n1+….+Nm=∑i*ni  +1 （求和的下限是i=1,上限是m）
n0=∑(i-1)*ni  +1
３. 两类特殊的二叉树：　满二叉树（结点数为2**k-1个），完全二叉树（结点号与满二叉树必须对应）
４. 性质４的证明　（书上有证明）
５. 二叉树的存储结构（书上的定义一定要记住）
顺序存储结构　　　　链式存储
二叉：　　空域　　　n+1
三叉：    空域      n+2
一般有：在一棵有n个结点，度为k的树中必有n*(k-1)+1个空链域
６. 各种遍历的递归和非递归算法均应熟练掌握
中序非递归见P130
先序非递归参看相关的资料
后序非递归：
Void  postorder_fei(BinNode   *t)
{　BinNode   *p;
  　　　　　printf(“post_order_fei :  “');
  　　　　 　top=0; stack[top]=t;
   　　　　　while (top!=-1)
    　　　　　{   while (stack[top])
           　　　 {   top=top+1; 
                　　　stack[top]=stack[top-1]->lch;
                　　　top=top-1;
 if  (top!=-1)
                　　　　　{  p=stack[top];
                   　　　　　　if( (!p->rch) || (p->rch->visited==1))
                       　　　　　  {  stack[top]=null;
                           　　　　　 printf(“%c”,p->data);   p->visited=1;
                        　　　　　 }
                  　　　　　　else
                   　　　　　　　 {  top=top+1;  stack[top]=p->rch;  }
                　　　　　}
}
}
　　　　　｝
７. 遍历算法的应用举例
(１) 求二叉树中叶子结点的个数。（先序（中序，后序）遍历二叉树，设一个全局变量作为计数器，左右指针为空的结点为叶结点）
int countleaf(BinTree  T)
  { int n1,n2;
   if (!T) return 0;
  else { if ((!T->lchild)&&(!T->rchild))
       return 1;
       else { n1=countleaf(T->lchild); //n1存放左子树的叶结点数
            n2=countleaf(T->rchild);// n2存放右子树的叶结点数
            return(n1+n2);
           }
       }
  }
(２) 求二叉树深度（后序遍历　）
基本思想：二叉树的深度为左右子树的最大深度加１
int  Depth(BinTree T)
 { int  dep,dep1,dep2;
   if (!T) dep=0;
   else { dep1=Depth(T->lch);
        dep2=Depth(T->rch);
dep=1+(dep1>dep2 ? dep1: dep2);
                   }
                 return dep;
}
(３) 复制二叉树（先序遍历）
Void copytree(BinTree root, BinTree *newroot) //newroot为指向指针的指针
　｛if (!root) *newroot=Null;
else
   { *newroot=(BinNode*)malloc(sizeof(BinNOde));
    (*newroot)->data=root->data;
    copytreer(root->lchild, &((*newroot)->lchild));//复制到左子树
    copytree(root->rchild, &((*newroot)->rchild));//复制到右子树
　｝
｝
(４) 交换二叉树的左右子树(类似先序遍历，用后序也可以，但中序不行)
Void  exchange(BinNode *T)
 { BinNode *q;
  if (T)
{ q=T->lchild;
  T->lchild=T->rchild;
  T->rchild=q;
  exchange(T->lchild);
  exchange(T->rchild);
}
}
　　　　　(5)建立二叉树的存储结构（不同的定义方法相应有不同的存储结构，现以字符串的形式　根　左子树　　右子树定义一棵二叉树（即二叉树的扩展序列）
　　　　　　如：　　　　　　　　　　　　　　
 　　以字符串AB*C**D** (*号表示空字符)
status  CreatBitree(BiTree &T) //按先序扩展序列建立二叉树的递归算法
　｛　scanf(&ch);
      if (ch= =’ ‘) T=Null;
      else{ if (!(T=(BinNode*)malloc(sizeof(BinNode))));
            exit(overflow);
           T->data=ch;
           CreatBitree(T->lchild);
           CreatBitree(T->rchild);
         }
     return ok;
   }
7. 已知按某规律遍历二叉树的非扩展序列（也即由先序，中序，后序遍历而得的序列），是否可以唯一确定该二叉树的结构？
结论：按某规律遍历二叉树的非扩展序列不能唯一确定该二叉树的结构
８. 已知按某规律遍历二叉树的扩展序列，能否唯一确定该二叉树的结构？
结论：先序扩展序列能唯一确定　　　中序扩展序列不能唯一确定
后序扩展序列能唯一确定（从后往前推导）
　　　　　//按后序遍历扩展序列建立二叉树结构的递归算法
　　　　　Void crt_bt_post(Bitreeptr *bt)
           { if (i>=s.len)  //I是全局变量，初始值为０，s存放后序扩展序列字符和长度
{ bt=stack[top]; top=top-1;} //入栈
else
  { i++; c=s.ch[i];　
　　if (c=’ ‘) *bt=Null;
    else { *bt=(BiNode*)malloc(sizeof(BiNode));
         (*bt)->data=c;
         (*bt)->rch=stack[top]; top=top-1;
         (*bt)->lch=stack[top]; top=top-1;
       }
   top=top+1; stack[top]=*bt;
   crt_bt_post(&bt);
 }
}
９. 层次遍历某二叉树的扩展序列可以唯一确定二叉树的存储结构
按层次遍历的扩展序列建立二叉树非递归算法（pascal）
getnode(var bt: bitreptr)
 begin
 i=i+1; e=s.ch[i];
  if (c=’ ‘) then bt=nil;
  else begin
new(bt); bt->data=c; que.rear=que.rear+1; que.elem[que.rear]=bt;
end
 end
proceede crt_bt_level( var bt:bitreptr)
 var p:bitreptr;
begin
   que.front=0;  que.rear=0;  getnode(bt);
   while que.rear<>que.front do
begin
  que.front=que.front+1;
  p=que.elem[que.front];
  getnode(p->lch); getnode(p->rch);
end
          end
１０. 由二叉树的先序和中序建立二叉树（要求会手工做）
Int pos(char ch; char pin[]; int start)  //定位：ch在中序中的位置
  { i=start;   b=false;
while ((i<=n)&&!b)