新建 文本文档.txt

判断完全二叉树以及求二叉树深度的递归与非递归算法实现

/* 判断完全二叉树，依据定义：任何一个节点（除去叶子节点)有且仅有两个“孩子” */ 
#include<stdlib.h>
#define MAX_TREE_DEGREE 10
typedef struct BTnode{//以二叉链表作为存储结构 
char data;
struct BTnode* lchild;
struct BTnode* rchild;
}BTnode,*BTree;
int createBTree(BTree* T){//先根建立一棵二叉树 
char ch;
scanf("%c",&ch);
if(ch == ' ')
*T = NULL;
else{
if(!(*T = (BTnode*)malloc(sizeof(BTnode))))
return -1;
(*T)->data = ch;
createBTree(&(*T)->lchild);
createBTree(&(*T)->rchild);
}
return 1;
}
/** 判断完全二叉树 */ 
int judgeComBTree(BTree root){//递归方式实现,被注释掉的部分可有可无 
if(!root) //空树 
return 0;
if(!root->lchild && !root->rchild) //没有孩子 
return 1;
//if((!root->lchild && root->rchild) || (root->lchild && !root->rchild)) // 只有一个孩子 
// return 0;
return judgeComBTree(root->lchild) & judgeComBTree(root->rchild); // 有且仅有两个孩子 
}
/** 二叉树深度的递归算法 */ 
int depth(BTree root){
int ldepth,rdepth;
if(!root)
return 0;
else{
ldepth = depth(root->lchild);
rdepth = depth(root->rchild);
if(ldepth >= rdepth) //取左右子树深度的最大值加一返回 
return ldepth+1;
else
return rdepth+1;
} 
return 1; //只有根节点 
} 

/** 二叉树深度的非递归算法（在中根遍历算法的基础上修改的来）， 关于中根遍历的详细解释参考

http://blog.csdn.net/panqiaomu/archive/2007/05/17/1612556.aspx */

int depth2(BTree root){
int top = 0;
int depth = 0,temp = 0;//temp 保存当前单分支的最大值
BTree p = root;
BTree nodePointer[MAX_TREE_DEGREE];
while(p || top > 0){
if(p){
nodePointer[top] = p;
++ top;
++ depth; //统计单分支的深度 
p = p->lchild;
}else{
-- top;
p = nodePointer[top];
p = p->rchild;
if(p == NULL){ //单分支结束
if(depth > temp )
temp = depth;
-- depth;
}
}//else
}//while
return temp;
}
int main(void){ //简单测试 
BTree root;
createBTree(&root);
printf("%d",judgeComBTree(root));
//compare
printf("\nThe depth of curBTree are:%d,%d \n",depth(root),depth2(root));
system("pause");
return 0;
}