判定其是否为完全二叉树（小编推荐）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“判断完全二叉树”。
#include #include /*........................抽象数据类型的定义.........................................*/ template struct BiNode { T data;BiNode *lchild,*rchild;};template struct element { BiNode *ptr;int flag;};template cla BiTree { public: BiTree();//有参构造函数，初始化一棵二叉树
~BiTree();BiNode* Getroot();//获得指向根结点的指针
void PreOrder(BiNode *root);//先序遍历二叉树,中序遍历二叉树，后序遍历二叉树
void PreOrder1(BiNode *root);void PreOrder3(BiNode *root);void InOrder(BiNode *root);void PostOrder(BiNode *root);void PostOrder1(BiNode *root);void LevelOrder(BiNode *root);//层序遍历算法
void CountLeaf(BiNode *root);//计算叶子节点的算法
int LeafNodes(BiNode *root);void PreOrder2(BiNode *root);//打印叶子节点,注意BiNOde后的，此标志着其来源于类模板
bool ComBiTree(BiNode *root);private: BiNode *root;BiNode *Creat();//有参构造函数调用
void Release(BiNode *root);//析构函数调用 };/*.....................有参构造函数....................*/ template BiTree::BiTree()//这里BiTree后面的不能省掉否则会出现以下错误use of cla template requires template argument list { this->root = Creat();} template BiNode* BiTree::Creat(){ BiNode* root;T ch;//cout>ch;if(ch=='.')root = NULL;else{ root = new BiNode;//生成一个结点
root->data=ch;root->lchild = Creat();//递归建立左子树
root->rchild = Creat();//递归建立右子树
} return root;} /*.......................析构函数..........................*/ template BiTree::~BiTree()//注意细节，少了一个冒号 { Release(root);} template //每个函数前面都必须加类模板注解 void BiTree::Release(BiNode *root){ if(root!=NULL){ Release(root->lchild);Release(root->rchild);delete root;} } /*....................前序递归遍历二叉树................递归算法*/ template void BiTree::PreOrder(BiNode *root){ if(root==NULL)return;else { coutdata;PreOrder(root->lchild);PreOrder(root->rchild);} } /*....................前序非递归算法..........................*/ template void BiTree::PreOrder1(BiNode *root){ int n=0;const int MaxSize=100;int top=-1;BiNode *s[MaxSize];//定义一个节点结构，这个数组存储的都是各个根节点,要指出该数组具体长度，不然程序无法读入 while(root!=NULL||top!=-1){ while(root!=NULL){ coutdata;s[++top]=root;root=root->lchild;} if(top!=-1){ root=s[top--];root=root->rchild;} } } template void BiTree::PreOrder3(BiNode *root){ const int MaxSize=100;BiNode *s[MaxSize],*p;//定义栈的节点数组，用来存储根节点指针.注意BiNode后的不能省掉； int top=-1;int n=0;if(root!=NULL){ top++;s[top]=root;while(top>-1){ p=s[top];top--;coutdata;if(p->rchild!=NULL){ top++;s[top]=p->rchild;} if(p->lchild!=NULL){ top++;s[top]=p->lchild;} if(p->lchild==NULL&&p->rchild==NULL){ n++;} } cout void BiTree::InOrder(BiNode *root){ if(root==NULL)return;else { InOrder(root->lchild);coutdata;InOrder(root->rchild);} } /*................后序遍历递归算法...............*/ template void BiTree::PostOrder(BiNode *root){ if(root==NULL)return;else { PostOrder(root->lchild);PostOrder(root->rchild);coutdata;} } /*................后序非递归遍历算法..........*/ template void BiTree::PostOrder1(BiNode *root){ const int MaxSize=100;int top=-1;element s[MaxSize];while(root!=NULL||top!=-1){ while(root!=NULL){ top++;s[top].ptr=root;//s是一个节点结构，其内含ptr与flag因此要定义一个节点结构
s[top].flag=1;root=root->lchild;} while(top!=-1&&s[top].flag==2){ root=s[top--].ptr;coutdata;} if(top!=-1){ s[top].flag=2;root=s[top].ptr->rchild;} } } /*.................层序遍历算法..............*/ template void BiTree::LevelOrder(BiNode *root){ const int MaxSize=100;BiNode *Q[MaxSize];BiNode *q;//这里q一个节点，要将其定义 int front,rear;front=rear=0;if(root==NULL)return;Q[++rear]=root;while(front!=rear){ q=Q[++front];coutdata;if(q->lchild!=NULL)Q[++rear]=q->lchild;if(q->rchild!=NULL)Q[++rear]=q->rchild;} } /*..............求二叉树中叶子节点的个数................*/ template void BiTree::CountLeaf(BiNode *root){ int n=0;if(root){ if(!root->lchild&&!root->rchild){coutdata;n++;} CountLeaf(root->lchild);CountLeaf(root->rchild);} } template int BiTree::LeafNodes(BiNode *root){ int num1,num2;if(root==NULL)return 0;else if(root->lchild==NULL&&root->rchild==NULL)return 1;else { num1=LeafNodes(root->lchild);num2=LeafNodes(root->rchild);return(num1+num2);} } template void BiTree::PreOrder2(BiNode *root)//打印叶子节点 { if(root){ if(!root->lchild&&!root->rchild)coutdata;PreOrder2(root->lchild);PreOrder2(root->rchild);} } /*..............................获取根节点的root................*/ template BiNode* BiTree::Getroot(){ return root;}
template bool BiTree::ComBiTree(BiNode *root){ int front,rear;const int MaxSize=100;BiNode *Q[MaxSize];//定义节点数组 front=rear=-1;int BJ,CM;BJ=CM=1;BiNode *p;if(root){ Q[++rear]=root;while(front!=rear){ p=Q[++front];if(!p->lchild){ BJ=0;if(p->rchild)CM=0;} else { CM=BJ;Q[++rear]=p->lchild;if(!p->rchild)BJ=0;else Q[front]=p->rchild;} } } return CM;}
void main(){ cout BT;//这里c++编译器只调用系统默认的构造函数
//注意这里的int型。这里要用实际的类型区定义类的数据类型 no appropriate default constructor available 找不到构造函数
/*常常在编译C++的时候，会出现这个问题，这儿是因为系统找不到默认的构造函数。因为类在没有定义任何构造函数的时候，系统才会默认产生构造函数，一旦定义了任何形式的构造函数，系统就不会在产生默认的构造函数了。
该错误是所找不到正确的无参数的构造函数。所以，一般情况下，只需要写一个空的构造函数，就可以解决问题。*/ BiNode *root = BT.Getroot();//获取指向根结点的指针 cout
