耿国华数据结构第六章答案.doc

总结二叉树
深度为k的二叉树的结点个数最多为2k-1 。在此层中最多有2k-1个节点。
N各节点的完全二叉树深度为[log(n)]-1.
二、叉树的链式存储结构
Typedef struct node
{
Int e;
Struct node *lchild;
Struct node *rchild;
}node,*bitree;
先序遍历
Void pre_order(bitree p)
{
If(p!=null)
{
Visit(p)
pre_order(p->left);
pre_order(p->right);
}
}
三、统计叶子节点的数目
Int n; //作为外部变量统计叶子节点的数目
Void leaf_num(bitree bt)
{
If(bt!=null)
{
If((bt->left==null)&& (bt->right==null))
N++;
Leaf_num(bt->left);
Leaf_num(bt->right);
}
}
Int leaf_num(bitree bt)
{
Int n;
If(bt==null)
N==0;
Else if((bt->left==null)&& (bt->right==null))
N==1;
Else
{
N= leaf_num(bt->left)+leaf(bt->right);
}
Return n;
}
四、求二叉树的高度
Int height(bitree bt)
{
Int height,m,n;
If(bt==null)
{
Height=0;
}
Else
{
m=height(bt->leftchild)+1;
n=height(bt->rightchild)+1;
if(m>n)
height=m;
else
height=n;
}
Return height;
}
五、中序与后序的非递归算法
Void inorder(bitree bt)
{
Int e;
Sqstack s;
Initstack(&s);
Bitnode p;
P=s;
While((!emptystack(s))||(p))
{
While(p)
{
Push(&s,p);
P=p->leftchild;
}
If(!emptystack(s))
{
pop(&s,&p);
Visit(p->data);
P=p->rightchild;
}
}
后续非递归:
Void last_order(bitree bt)
{
Bitnode *p,*q;
Bitree s[stack_size];
P=bt;
Q=null;
While((p)||(!emptystack(s)))
{
While(p)
{
Push(&s,p);
P=p->leftchild;
}
If(!emptystack(s))
{
gethead(s,&p);
If((p->rightchild==null)&&(p->rightchild==q))

{
Pop(&s,&p);
Visit(p);
Q=p;
P=null;
}
Else
P=p->rightchild
}
}
}
六、线索二叉树
中序线索二叉树找前驱
bitnode *find_pre(bitnode *p)
{
Bitnode *q;
If(p->lefttag==1)
Return p->leftchild;
Else
{
q=p->leftchild;
While(p->righttag==0)
{
Q=p;
P=p->rightchild;
}
Return q;
}
}
Bitnode *find_last(bitnode *p)
{
Bitnode *q,*pre;
Q=p;
If(q->righttag==1)
Return q->rightchild;
Else
{
Q=q->rightchild
While(q->righttag==0)
{
Pre=q;
Q=q->rightchild;
}
Return q->rightchild;
}
}
七、二叉树相似性的判断
#define ok 1
Int tre_alike(bitree b,bitree a)
{
Int m,n;
Bitnode *p,