再帰呼び出しを使った２分木 Segmentation fault

Question

再帰呼び出しを使う2分木の質問です。初めにこちらのプログラムは正しいでしょうか？Binarry_Tree関数に配列の値を引数にとると、Segmentation fault 11というエラーがでてしまいます。
また、下のような出力結果を出したい時どうすれば良いでしょうか？Print_Tree関数は未完成です。
Input Number: 8 (root)
[ 8] is joined at アドレス; Parent: 0
Input Number: 5
[ 5] is joined at アドレス; Left child of Parent: 親のアドレス
Input Number: 7
[ 7] is joined at アドレス; Right child of Parent: 親のアドレス
コメントアウトは無視してください。 よろしくお願いします。

#include <iostream>
using namespace std;

struct TREE{
  int data;
  TREE *Parent;
  TREE *LeftChild;
  TREE *RightChild;
};

void Binary_Tree(TREE *,int );
void Add_New_Vertex(TREE *,int );
void Print_Tree(TREE *,int);


int main()
{
  TREE *root = new TREE;

  int a[] = {8,5,7,3,10,9,6,1,20};
  int i = 0;
  //int x=5;

  root->data=a[i];
  root->Parent = NULL;
  root->LeftChild = NULL;
  root->RightChild = NULL;

  for(i=1;i < 9; i++){
    x=a[i];
  Binary_Tree(root,x);
  }
  //Binary_Tree(root,x);
  
  /*for(int j=1; i<9; i++){
    Print_Tree(root,a[i]);
  */
  
  //cout<< root->data <<" " << root <<" " << root->Parent <<" " << root->LeftChild <<" " <<" " << root->RightChild << endl;
  //cout<< root->LeftChild->data <<" " << root->LeftChild <<" " << root->LeftChild->Parent <<" " << root->LeftChild <<" " <<" " << root->RightChild << endl;
  //cout<< root->LeftChild->RightChild->data <<" " << root->LeftChild->RightChild <<" " << root->LeftChild->RightChild->Parent <<" " << root->LeftChild <<" " <<" " << root->RightChild << endl;
}

void Binary_Tree(TREE *p,int x)
{
  
  if(x < p->data && p->LeftChild != NULL){
    Binary_Tree(p->LeftChild,x);
  }else if(x > p->data && p->RightChild !=NULL){
    Binary_Tree(p->RightChild,x);
  }else{
    Add_New_Vertex(p,x);
  }
  
}


void Add_New_Vertex(TREE *p,int x)
{
  TREE *add = new TREE;

  add->data = x;
  if(x < p->data){
    p->LeftChild = add;
    p->RightChild = NULL;
    add->Parent = p;
  }else if(x > p->data){
    p->RightChild = add;
    p->LeftChild = NULL;
    add->Parent = p;
  }
}

 void Print_Tree(TREE *p,int x ){

   if(x < p->data && p->LeftChild != NULL){
     cout << p->data << endl;
    Print_Tree(p->LeftChild,x);
  }else if(x > p->data && p->RightChild !=NULL){
     cout << p->data << endl;
    Print_Tree(p->RightChild,x);
   }
   cout << p->data << endl;
 }

Answer 1

質問のコードの Segmenttation fault はどのようにして解決したのでしょうか？
解決したコードを質問に追記してください。

質問内容に書いてるような配列の要素順に出力し、LeftChildならLeftChildと、RightChildならRightChildと出力するにはどうすれば良いでしょうか？

次のコードは参考になりますか？

#include <iostream>
using namespace std;

struct TREE {
	int data;
	TREE *Parent;
	TREE *LeftChild;
	TREE *RightChild;
};

void Binary_Tree(TREE *, int);
TREE *Add_New_Vertex(TREE *, int);
void Print_Tree(TREE *, int);

int main()
{
	int a[] = { 8, 5, 7, 3, 10, 9, 6, 1, 20 };
	TREE *root = Add_New_Vertex(NULL, a[0]);
	for (int i = 1; i < 9; i++)
		Binary_Tree(root, a[i]);
	for (int i = 0; i < 9; i++)
		Print_Tree(root, a[i]);
}

void Binary_Tree(TREE *p, int x)
{
	if (x < p->data) {
		if (p->LeftChild != NULL)
			Binary_Tree(p->LeftChild, x);
		else
			p->LeftChild = Add_New_Vertex(p, x);
	} else if (x > p->data) {
		if (p->RightChild != NULL)
			Binary_Tree(p->RightChild, x);
		else
			p->RightChild = Add_New_Vertex(p, x);
	}
}

TREE *Add_New_Vertex(TREE *p, int x)
{
	TREE *add = new TREE;
	add->data = x;
	add->Parent = p;
	add->LeftChild = add->RightChild = NULL;
	return add;
}

void Print_Tree(TREE *p, int x)
{
	if (x < p->data)
		Print_Tree(p->LeftChild, x);
	else if (x > p->data)
		Print_Tree(p->RightChild, x);
	else {
		cout << "[ " << x << "] is joind at " << p;
		if (p->Parent == NULL)
			cout << "; Parent: 0\n";
		else if (p == p->Parent->LeftChild)
			cout << "; Left child of Parent: " << p->Parent << endl;
		else
			cout << "; Right child of Parent: " << p->Parent << endl;
	}
}

実行結果

[ 8] is joind at 0x7fffcf7f6eb0; Parent: 0
[ 5] is joind at 0x7fffcf7f6ee0; Left child of Parent: 0x7fffcf7f6eb0
[ 7] is joind at 0x7fffcf7f6f10; Right child of Parent: 0x7fffcf7f6ee0
[ 3] is joind at 0x7fffcf7f6f40; Left child of Parent: 0x7fffcf7f6ee0
[ 10] is joind at 0x7fffcf7f6f70; Right child of Parent: 0x7fffcf7f6eb0
[ 9] is joind at 0x7fffcf7f6fa0; Left child of Parent: 0x7fffcf7f6f70
[ 6] is joind at 0x7fffcf7f6fd0; Left child of Parent: 0x7fffcf7f6f10
[ 1] is joind at 0x7fffcf7f7000; Left child of Parent: 0x7fffcf7f6f40
[ 20] is joind at 0x7fffcf7f7030; Right child of Parent: 0x7fffcf7f6f70

理解できたかどうかコメントをお願いします。
理解できない場合、どこが分からないのかをコメントしてください。

Comments

[Giovannaaa]

ありがとうございます。理解することができました。

Answer 2

こちらのプログラムは正しいでしょうか？Binarry_Tree関数に配列の値を引数にとると、Segmentation fault 11というエラーがでてしまいます。

実行時エラーが出てるなら正しいわけがない。

void Add_New_Vertex(TREE* p, int x)
{
    TREE* add = new TREE;

    add->data = x;
    add->LeftChild = NULL; // コレと
    add->RightChild = NULL; // コレを忘れてない?
    ...

下のような出力結果を出したい時どうすれば良いでしょうか？Print_Tree関数は未完成です。

// ひんと: とにかく全部プリントする
void PrintTree(TREE* p) {
  if ( p != NULL ) {
    data と 親アドレスをプリントする
    PrintTree(p->LeftChild);
    PrintTree(p->RightChild);
  }
}

Comments

[Giovannaaa]

回答ありがとうございます。
付け足したのですが、コメントアウトをしている出力オブジェクトを使ってもrootの値は出力されるのですが、下のLeft,RightChildの値は出力されません。
よろしくお願いします。

[episteme]

出力していないからでしょ(追記しました)

[Giovannaaa]

ありがとうございます。試してみたのですが、
8
0x0
20
0x7fd15d405930
このような出力結果になってしまいます。

[episteme]

デバッグを丸投げするおつもりか?

[Giovannaaa]

何回もすみません。
for文を回さず、Binarry_Tree(root,5)とするとコメントアウトしている出力オブジェクトは正しく実行結果がでます。この引数にa[i]という配列を渡すとsegmentation fault 11が出ます。なぜなのでしょうか？

[episteme]

配列を渡す? Binarry_Tree(root、a) したんですか? コンパイルエラーじゃありませんか?

[episteme]

void Binary_Tree(TREE *p,int x) に p = NULL が渡されると
p->data, p->LeftChild, p->RightChild が segmentation fault するでしょね。

[Giovannaaa]

指摘していただいたおかげで、解決できました。ありがとうございます。
最後に質問なのですが、質問内容に書いてるような配列の要素順に出力し、LeftChildならLeftChildと、RightChildならRightChildと出力するにはどうすれば良いでしょうか？　ヒントでもいいので教えて欲しいです。よろしくお願いします。

[episteme]

int a[] = {8,5,7,3,10,9,6,1,20};
for ( i = 0; i < 9; ++i ) {
TREE の中から p->data == a[i] である p を見つけてプリントする
}

[Giovannaaa]

ヒントの内容をずっと考えているのですが、pを移動していくにはどうすれば良いのでしょうか？

[episteme]

ここまでできててわからんわけない。
てか、いくつ質問すれば気がすむのかな? Segmentation fault は解決したんでしょ?

[Giovannaaa]

ありがとうございました。