0 
#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include<iostream>
#include<vector>

using namespace std;

class Binary_Tree;

static int levelCount=0;

extern vector<vector<Binary_Tree*>> vec;
extern vector<Binary_Tree*> tempVec;

class Binary_Tree
{
  public:
     Binary_Tree()
     {
        childNum=0;
        data=0;
        level=0;
        prev=NULL;
        next[0]=NULL;
        next[1]=NULL;
    };

    Binary_Tree(int d)
    {
         childNum=0;
         data=d;
         level=0;
         prev=NULL;
         next[0]=NULL;
         next[1]=NULL;
         levelCount++;
     }


    void insert_node(int,int,int);

    int get_level();

    int get_childCount();

    friend int set_childNum(Binary_Tree*);

private:
    int childNum;
    int data;
    int level;
    Binary_Tree *prev;
    Binary_Tree *next[2];
};

#endif // BINARY_TREE_H

実装ファイルはこちら

#include<iostream>
#include<cmath>
#include "Binary_Tree.h"

using namespace std;



void Binary_Tree::insert_node(int lev, int d, int sib)
{
if(vec.empty())
{
    cout<<"You Have to create Root first";
}

else
{
    if(set_childNum(vec[lev][sib-1])==0)
    {
        cout<<"Child cant be created parent Node already has two childs.";
    }

    else
    {
        childNum=set_childNum(vec[lev][sib-1]);
        data=d;
        level=lev+1;
        prev=vec[lev][sib];
        next[0]=NULL;
        next[1]=NULL;
        tempVec.clear();
        for(int i=0; i<pow(2,(lev+1)); i++)
        {
            if(i==childNum-1)
            {
                tempVec.push_back(this);
            }
            else
            tempVec.push_back(vec[lev][i]);
        }
        vector<vector<Binary_Tree*>>::iterator itr=vec.begin()+(lev+1);
        vec.erase(itr);
        vec.insert(itr,tempVec);
       }
   }
}

int set_childNum(Binary_Tree *lstNdAdr)
{
    if(lstNdAdr->get_childCount()==0)
        return 1;

    else if(lstNdAdr->get_childCount()==1)
        return 2;

    else
      return 0;
}

int Binary_Tree::get_level()
{
    return level;
}

int Binary_Tree::get_childCount()
{
  if(next[0]==NULL)
  {
    return 0;
  }

  else if(next[0]!=NULL && next[1]==NULL)
  {
    return 1;
  }

  else
  {
    return 2;
  }


}

メイン.cpp

#include <iostream>
#include<cmath>
#include"Binary_Tree.h"

using namespace std;

vector<vector<Binary_Tree*>> vec;
vector<Binary_Tree*> tempVec;


int main()
{
  Binary_Tree tree;
  here:
  cout<<"Enter your Choice:1.Create Root Of Tree\n"
      <<"2.Insert node\n"<<endl;

  int choice;
  cin>>choice;

  switch(choice)
  {
    case 1:
      {
        int d;
        cout<<"Enter Data to insert: ";
        cin>>d;

         Binary_Tree treeDummy(d);

         tree=treeDummy;

         tempVec.push_back(&tree);

         vec.push_back(tempVec);
       }

     break;

    case 2:
    {
        int lev;
        int sibbling;
        int d;
        cout<<"Enter at which level and data and parent's sibling-no.: ";
        cin>>lev;
        cin>>d;
        cin>>sibbling;

        if(sibbling>pow(2,lev))
            cout<<"Illegal Sibbling Number."<<endl;
        else
            tree.insert_node(lev,d,sibbling);

    }
    break;
}
int x;
cin>>x;
if(x==5)
{
    cout<<endl<<endl;
    goto here;

}

  return 0;
}

上記のコードでは、実行時に任意のノードを挿入および削除できる、動的に操作およびトラバースできるバイナリ ツリー型構造を作成しようとしています (ただし、問題が発生しているため不完全です)。ベクトルをプッシュバックしている間tempVec、コードはセグメンテーション違反を生成し、実装の関数に vetcor> vec に格納されているオブジェクトを渡すことにも疑問があります (私は Stl を初めて使用し、クラスへのポインターを含むベクトルのベクトルを初めて処理します)種類）

4

2 に答える 2

1

iネストされたベクトルのエントリは、が に設定されている場合にのみ埋められます1。ただし、関係なくその要素にアクセスしようとします[0][0]。iではない場合、境界外アクセスがあり1ます。

于 2013-09-06T22:57:41.520 に答える
1

コードには多くの問題が存在し、スタイルや書式設定の悪さと相まって、デバッグが楽しくありません。

   Binary_Tree treeDummy(d);
   tree = treeDummy;

   tempVec.push_back(&tree);

ここで何をしようとしているのかわかりませんが、上記は間違っているようです。treeDummy のデータをツリーに浅いコピーしています。子ノード ツリーが指すものへのリンクが失われます。その後、同じツリー インスタンスを一時的なベクターにプッシュします。つまり、ベクター内のすべての要素がローカル変数treeinを指すことになりますmain。したがって、セグメンテーション違反が発生しなくても、エイリアシングの問題が発生します。それらはすべて同じtreeオブジェクトを参照しており、個別の一意のBinaryTreeインスタンスではありません。

  vector< vector<Binary_Tree*> >::iterator itr=vec.begin()+(lev+1);
  vec.erase(itr);
  vec.insert(itr,tempVec);

BinaryTree::insert_node実行後に無効化されたイテレータを使用していますが、これeraseは未定義の動作です。

  childNum = set_childNum(vec[lev][sib-1]);
  // ...
  prev = vec[lev][sib];

上記は、ベクター内の範囲外のインデックスにアクセスできます。例えば。要素が 1 つしかないa を push_back してから、= 1でtempVec呼び出します。insert_nodesib

 // ...
 if(x == 5)
 {
   cout<<endl<<endl;
   goto here;
 }

の使用gotoもここでは完全に不要であり、 をチェックする従来の while ループに置き換える必要がありますcondition != 5。

ただし、プログラムのより高いレベルの問題は、その設計に明確な制約と不変条件がないことです。これらの各機能が機能するために必要な前提条件と前提条件は何ですか? BinaryTreeクラス自体がノードを処理する必要がある場合に、ベクトルを使用してノードを保持する理由。最初に全体的なデザインを整理する必要があります。そうしないと、他のバグが発生したときにもぐらたたきをするだけになります。

于 2013-09-07T02:06:26.850 に答える