weixin_38008621
weixin_38008621
2017-10-16 06:47

c++输入二叉树,判读是否为完全二叉树,貌似指针出错

10
  • c++
  • 二叉树

c++输入二叉树的节点数,以及每个结点的左结点和右结点的序号,从右下往根的顺序输入,判读是否为完全二叉树
然后源代码如下,不知道错在哪里,问题如图

这道题目的要求如下:
给出一棵二叉树的结构,判断这棵二叉树是不是完全二叉树。必须使用二叉树类实现。

Input Format
输入文件一共包含N+1行。

第一行含有一个正整数N,代表树中结点总数。

第二行到第N+1行,每行包含二个整数。其中第i行的二个整数Pi,Qi,代表结点i的左孩子为Pi,右孩子为Qi。若Pi=0,则表明结点i没有左孩子。同样的,若Qi=0,则表明结点i没有右孩子。(第i行指的是这N行中的第i行)

Output Format
如果给出的树是完全二叉树,则输出'Y',否则输出'N'。(均不包含引号)

Sample Input1
4
0 0
0 0
1 0
3 2
Sample Output1
Y
Sample Input2
4
0 0
0 0
0 1
3 2
Sample Output2
N

#include
#include
using namespace std;

class BinaryTree{
private:

struct Node{
Node *left,*right;
int data;

   Node():left(NULL),right(NULL),data(0){}
   Node(int item,Node *L=NULL,Node *R=NULL):
       data(item),left(L),right(R){}
   ~Node() {};
};


 Node *root=new Node;

public:
BinaryTree():root(NULL){} //构造空二叉树
BinaryTree(const int&value){root=new Node(value);}

bool makeTreeandjudge(int *ln,int *rn,int n);

};

bool BinaryTree::makeTreeandjudge(int ln,int *rn,int n)
{
Node **iscbt;
iscbt=new Node
[n+1];
for(int i=0;i<n+1;++i)
iscbt[i]=NULL;

//MAKETREE
int j=1;
for(int i=n-1;i>=0;--i) //先以完全二叉树的情况保存
{
cout<<"N="<left ="<right ="< if(2*j>n) //若在iscbt情况下结点无左结点时
{
cout<<"iscbt结点无左结点"< Node *tmp1=new Node;
iscbt[j]->left=tmp1;
tmp1->data=ln[i];
}
else{
cout<<"lscbt["< if(iscbt[j]==NULL) cout else cout iscbt[j]->left=iscbt[2*j];
iscbt[2*j]->data=ln[i];}

   if(2*j+1>n)
   {
       Node *tmp2=new Node;
       iscbt[j]->right=tmp2;
       tmp2->data=rn[i];
   }
   else{
        cout<<"lscbt["<<2*j<<"]="<<rn[i];
   iscbt[j]->right=iscbt[2*j+1];
   iscbt[2*j+1]->data=rn[i];
   }


   j+=1;
   cout<<"next j="<<j;

}

//JUDGE

int height=log(n)/log(2);
for(int m=1;m<=pow(2,height-1)-1;++m) //若在1--height-1内有节点的data为零,则不是完全二叉树
{
if(iscbt[m]->data==0) return false;
}

for(int n=pow(2,height-1)-1;n>pow(2,height-2)-1;--n)
{
if(iscbt[n]->right!=0&&iscbt[n]->left==0) return false;
if(iscbt[n]->left!=0&&iscbt[n]->right==0)
{
--n;
int k=n;
for(n=k;n>pow(2,height-2)-1;--n)
{
if(!(iscbt[n]->left->data!=0&&iscbt[n]->right->data!=0)) return false;
if(n==pow(2,height-2)) return true;
}
}
}

return true;

}

int main()
{
int N; //树中的结点总数
cin>>N;

BinaryTree TREE;

int *leftnumber=new int[N];
int *rightnumber=new int[N];

for(int i=0;i<N;++i)
{
    cin>>leftnumber[i]>>rightnumber[i];
}

bool flag;
flag=TREE.makeTreeandjudge(leftnumber,rightnumber,N);

if(flag==true) cout<<"Y";
else cout<<"N";

return 0;

}

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答