判断完全二叉树:判断完全二叉树以及求二叉...

/* 判断完全二叉树，依据定义：任何一个节点（除去叶子节点)有且仅有两个“孩子” */
#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{