（6）判断是否完全二叉树
在这里我用了完全前序创建的二叉树；
#include <iostream> #include <string> #include <math.h> using namespace std; struct node//数的节点 { char ch;//字符 node *leftChild;//左儿子 node *rightChild;//右儿子 }; struct info//记录树节点的一些信息，判断是否为完全二叉树时用 { bool isChildErCha;//如果左子树比右子树的高度多一或相等则为true，否则为false int Height;//记录树的高度； }; class myQueue//队列adt实现，用于树的广度遍历 { int last,head; node* ch[100]; public: myQueue() { last = 0; head = -1; } void push(node* a) { ch[last] = a; last++; } node* pop() { head++; return ch[head]; } bool isEmpty()//判断是否为空 { if(last-head==1)return true; else return false; } }; int create(string str,int i,node *&root)//给定一串字符串，用@隔开，用于创建一棵二叉树 { if(str[i]=='@') return i+1; else { root = new node; root->ch = str[i]; root->leftChild = NULL; root->rightChild = NULL; int n= create(str,i+1,root->leftChild); int m = create(str,n,root->rightChild); return m; } } void visitQian(node *root)//前序遍历 { if(root!=NULL) { cout<<root->ch; visitQian(root->leftChild); visitQian(root->rightChild); } } void visitZhong(node *root)//中序遍历 { if(root!=NULL) { visitZhong(root->leftChild); cout<<root->ch; visitZhong(root->rightChild); } } int height(node *root)//求树的高度 { if(root->leftChild==NULL && root->rightChild==NULL)return 1; else if(root->leftChild==NULL) return height(root->rightChild)+1; else if(root->rightChild==NULL) return height(root->leftChild)+1; else { int m = height(root->leftChild); int n = height(root->rightChild); if(m>n) return m+1; else return n+1; } } void visitHou(node *root)//后续遍历 { if(root!=NULL) { visitHou(root->leftChild); visitHou(root->rightChild); cout<<root->ch; } } void visitGuang(node *root)//广度遍历 { if(root==NULL)return ; else { myQueue MyQueue; MyQueue.push(root); while(!MyQueue.isEmpty()) { node *p = MyQueue.pop(); cout<<p->ch; if(p->leftChild!=NULL)MyQueue.push(p->leftChild); if(p->rightChild!=NULL)MyQueue.push(p->rightChild); } } } bool match(node *root,char tar)//判断root的儿子的ch是否为tar { if(root->leftChild!=NULL && root->rightChild!=NULL) { if(root->leftChild->ch ==tar ||root->rightChild->ch==tar) return true; else return false; } else if(root->leftChild!=NULL) { if(root->leftChild->ch==tar) return true; else return false; } else if(root->rightChild!=NULL) { if(root->rightChild->ch==tar) return true; else return false; } } char parent(node *root,char tar)//求ch为tar的节点的双亲 { if(root==NULL)return ' '; else if(match(root,tar)) return root->ch; else { char c; if((c=parent(root->leftChild,tar))!=' ')return c; else return parent(root->rightChild,tar); } } int leafNmu(node *root)//叶子节点的数目 { if(root==NULL)return 0; else if(root->leftChild==NULL && root->rightChild==NULL)return 1; else return leafNmu(root->leftChild)+leafNmu(root->rightChild); } int nonLeafNmu(node *root)//非叶子节点的数目 { if(root==NULL)return 0; else if(root->leftChild==NULL && root->rightChild==NULL)return 0; else return 1+leafNmu(root->leftChild)+leafNmu(root->rightChild); } info isWanQuanErCha(node *root)//判断该树是否为完全二叉树，判断依据为任意结点的左子树的高度比右子树高1或相等 { info rootInfo; if(root==NULL) { rootInfo.Height=0; rootInfo.isChildErCha = true; return rootInfo; } else { info i1 = isWanQuanErCha(root->leftChild); info i2 = isWanQuanErCha(root->rightChild); rootInfo.isChildErCha = (i1.Height-i2.Height==1 ||i1.Height-i2.Height==0)&i1.isChildErCha&i2.isChildErCha; rootInfo.Height = max(i1.Height,i2.Height)+1; return rootInfo; } } int main() { cout<<"请输入带有标志位的完全前序序列，以‘@’未标识"<<endl; string str; cin>>str; node *root = NULL; create(str,0,root); visitGuang(root); cout<<endl; visitQian(root); cout<<endl; visitZhong(root); cout<<endl; visitHou(root); cout<<endl; cout<<isWanQuanErCha(root).isChildErCha; return 0; } 可能会有bug，希望批评指正！