树状显示二叉树和完全二叉树判断

#include "BinaryTree.h" BinaryTree::BinaryTree() { root=NULL; cout<<"==================================="<<endl; cout<<"请输入二叉树的扩展先序序列:"; cout<<"(e.g:ABDH E CF G ) "<<endl; CreateBiTree(&root); } BinaryTree::~BinaryTree() { // } int BinaryTree::ex2(int n) { int result=1; for(int i=0; i<n; i++) result*=2; return result; } void BinaryTree::CreateBiTree(BiTree *root) { char ch; ch=getchar(); if(ch==' ') *root=NULL; else { *root=new BiTNode; (*root)->data=ch; CreateBiTree(&((*root)->lchild)); CreateBiTree(&((*root)->rchild)); } } void BinaryTree::porder(BiTree root)const { if(root) { cout<<root->data; porder(root->lchild); porder(root->rchild); } } void BinaryTree::preorder()const { cout<<"该二叉树的先序遍历序列:"<<endl; porder(root); cout<<endl; } void BinaryTree::PrintTree(BiTree root,int nLayer)const { if(root==NULL) return; PrintTree(root->rchild,nLayer+1); for(int i=0; i<nLayer; i++) cout<<" "; cout<<root->data<<endl; PrintTree(root->lchild,nLayer+1); } void BinaryTree::print()const { cout<<"按竖向树状打印二叉树:"<<endl; PrintTree(root,5); cout<<endl; } void BinaryTree::LayerOrder(queue<char> &Q,queue<Position> &QI,int dw,int sw) { //层次遍历二叉树，储存结点位置信息 if(root==NULL) return ; queue<BiTree> temp; queue<Position> temppos; BiTree p; Position pos; temp.push(root); Q.push(root->data); pos.layer=0; pos.blank=sw/2; temppos.push(pos); QI.push(pos); while(!temp.empty()) { p=temp.front(); temp.pop(); // cout<<Q.front(); Position parentpos=temppos.front(); temppos.pop(); int offset=sw/ex2(parentpos.layer+2); if(p->lchild) { temp.push(p->lchild); Q.push(p->lchild->data); pos.layer=parentpos.layer+1; pos.blank=parentpos.blank-offset; temppos.push(pos); QI.push(pos); } if(p->rchild) { temp.push(p->rchild); Q.push(p->rchild->data); pos.layer=parentpos.layer+1; pos.blank=parentpos.blank+offset; temppos.push(pos); QI.push(pos); } } } void BinaryTree::displaytree(int datawidth,int screenwidth) { cout<<"树状显示二叉树:"<<endl; queue <char> Q; queue <Position> QI; LayerOrder(Q,QI,datawidth,screenwidth); int layer=0,bk=0; while(!QI.empty()) { if(layer<QI.front().layer) { layer++; cout<<endl<<endl; bk=0; } while(bk<QI.front().blank) { cout<<" "; bk++; } cout<<Q.front(); bk+=datawidth; QI.pop(); Q.pop(); } cout<<endl<<endl; } bool BinaryTree::Iscompletebinarytree() { //判断一颗二叉树是否为完全二叉树 if(root==NULL) return true; queue <BiTree> Q; Q.push(root); int flag=0; while(!Q.empty()) { if(!Q.front()) flag=1; else if(flag) return false; else { Q.push(Q.front()->lchild); Q.push(Q.front()->rchild); } Q.pop(); } return true; }