数据结构考研分类复习真题 第六章 答案 (五)[34]

．int Count (BiTree bt) // 非递归遍历求二叉树上的叶子结点个数

{int num=;

BiTree s[]; //s是栈栈中元素是二叉树结点指针栈容量足够大

whlie(bt!=null || top>)

{while(bt!=null) {push(sbt)bt=bt>lchild} //沿左分支向下

if(!StackEmpty(s))

{bt=pop(s)if(bt>lchild==null && bt>rchild==null) num++//叶子结点

bt=bt>rchild

}

} return(num);

}//结束Count

[题目分析]对二叉树的某层上的结点进行运算采用队列结构按层次遍历最适宜

int LeafKlevel(BiTree bt int k) //求二叉树bt 的第k(k>) 层上叶子结点个数

{if(bt==null || k<) return();

BiTree p=btQ[]; //Q是队列元素是二叉树结点指针容量足够大

int front=rear=leaf=; //front 和rear是队头和队尾指针 leaf是叶子结点数

int last=level=; Q[]=p; //last是二叉树同层最右结点的指针level 是二叉树的层数

while(front<=rear)

{p=Q[++front];

if(level==k && !p>lchild && !p>rchild) leaf++; //叶子结点

if(p>lchild) Q[++rear]=p>lchild; //左子女入队

if(p>rchild) Q[++rear]=p>rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理层数增

last=rear; } //last移到指向下层最右一元素

if(level>k) return (leaf); //层数大于k 后退出运行

}//while }//结束LeafKLevel

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []