全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 【算法源代码】
BiTree Creat() { /*建立二叉树的二叉链表形式的存储结构*/ ElemType x; BiTree bt;
scanf(\ if(x==0) bt=NULL; else if(x>0) {bt=(BiTNode *)malloc(sizeof(BiTNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } return(bt); }/*结束 creat*/
int JudgeComplete(BiTree bt){
/*判断二叉树是否是完全二叉树,如是,返回1,否则,返回0*/ int tag=0;
BiTree p=bt, Q[50]; /* Q是队列,元素是二叉树结点指针,容量足够大*/ if(p==NULL) return 1; QueueInit(Q);
QueueIn(Q,p); /*初始化队列,根结点指针入队*/ while(!QueueEmpty(Q)){ p=QueueOut(Q);
if (p->lchild && !tag) QueueIn(Q,p->lchild); /*左子女入队*/
else if (p->lchild) return 0; /*前边已有结点为空,本结点不空*/ else tag=1; /*首次出现结点为空*/ if (p->rchild && !tag) QueueIn(Q,p->rchild); /*右子女入队*/ else if (p->rchild) return 0; else tag=1; }/*while*/ return 1;
} /*JudgeComplete*/
5.有n个结点的完全二叉树存放在一维数组A[1..n]中,试据此建立一棵用二叉链表表示的二叉树,根由tree指向。
【算法源代码】
typedef int ElemType;
BiTree Creat(ElemType A[],int i){ BiTree tree; if (i<=n) {
tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];
if(2*i>n) tree->lchild=NULL;
else tree->lchild=Creat(A,2*i); if(2*i+1>n) tree->rchild=NULL;
else tree->rchild=Creat(A,2*i+1); }
return (tree); }/*Creat*/
6.编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值。 【算法源代码】
int c,k; /*这里把k和计数器c作为全局变量处理 */
void Get_PreSeq(BiTree T) /*求先序序列为k的结点的值 */ { if(T)
{ c++; /*每访问一个子树的根都会使前序序号计数器加1 */
if(c==k) { printf(\ return; } else
{ Get_PreSeq(T->lchild); /*在左子树中查找 */