木構造編集プログラムのノードの削除機能について

Question

木構造編集プログラムに、ノードの削除機能を追加しています．
コマンドは、以下の形式とします．
「 D n L|R 」：　n番ノードの左（L）または右（R）の子ノードを削除する.
削除対象ノードが1つの子を持つときには、その子を削除ノードのあった位置に接続します．2つの子を持つときには削除しません．

以下が現在のコードです．

#include <iostream>
#include <string>
using namespace std;

#define LINELENGTH 80    //一行の長さ
#define END    'E'        //終了
#define ADD    'A'        //追加
#define CUT    'X'        //切り取り
#define LEFT    'L'        //左
#define RIGHT    'R'        //右
#define INSERT   'I'       //挿入 
#define DELETE   'D'      //削除

class Node {            //ノードを表すクラス
public:
	string word;    //ノード格納単語
	Node* pLeft;    //左ノードを参照するポインタ
	Node* pRight;    //右ノードを参照するポインタ
};

//プロトタイプ宣言
void showTree();
void showTreeRecursive(Node* pNode, int nodeLevel);
Node* searchNode(int searchNodeNo);
Node* searchNodeRecursive(Node* pPresentNode, int searchNodeNo);
void addNode(string word, int nodeNo, char direction);
void cutNode(int nodeNo, char direction);
void deleteNodeRecursive(Node* pNode);
void showHelp();
void insertNode(string word, int nodeNo, char direction);
void deleteNode(int nodeNo, char direction);

Node* pRoot;        //根ノードを参照するポインタ
int nodeCounter;    //ノードの番号付けカウンタ

//
//----メイン関数-------
//
void main()
{
	char commandLine[LINELENGTH] = "";    //コマンド行(文字配列）
	char command = ' ';                    //コマンド文字
	char word[LINELENGTH] = "";            //単語（文字配列）
	char direction = LEFT;                //方向指示
	int nodeNo;                            //ノード番号

	//根ノードを生成して、その参照を根ノードポインタに入れる。
	pRoot = new Node;

	//根ノードの左右ポインタにNULLを、単語に"<"を入れる。
	pRoot->pLeft = pRoot->pRight = NULL;
	pRoot->word = "<";

	//現在の木構造を表示する。
	showTree();

	//コマンド行を受け取り、その先頭のコマンド文字を取り出す。
	cout << "> ";
	cin.getline(commandLine, LINELENGTH);
	sscanf_s(commandLine, "%c", &command, 1);

	//コマンドが「プログラム終了」でない限り、以下の処理を繰り返す。
	while (command != END) {

		//コマンドが「追加」であれば、以下を実行する。
		switch (command) {
		case ADD:

			//コマンド行から、コマンド、単語、ノード番号、方向指示を取り出せれば、追加を実行する。
			if (sscanf_s(commandLine, "%c %s %d %c", &command, 1, word, LINELENGTH, &nodeNo, &direction, 1) == 4) {
				addNode(word, nodeNo, direction);
			}
			break;

			//コマンドが「切り取り」であれば、以下を実行する。
		case CUT:

			//コマンド行から、コマンド、ノード番号、方向指示を取り出せたら、切り取りを実行する。
			if (sscanf_s(commandLine, "%c %d %c", &command, 1, &nodeNo, &direction, 1) == 3) {
				cutNode(nodeNo, direction);
			}
			break;

			//コマンドが「挿入」であれば、以下を実行する。
		case INSERT:

			//コマンド行から、コマンド、単語、ノード番号、方向指示を取り出せれば、挿入を実行する。
			if (sscanf_s(commandLine, "%c %s %d %c", &command, 1, word, LINELENGTH, &nodeNo, &direction, 1) == 4) {
				insertNode(word, nodeNo, direction);
			}
			break;

			//コマンドが「削除」であれば、以下を実行する。
		case DELETE:

			//コマンド行から、コマンド、ノード番号、方向指示を取り出せれば、削除を実行する。
			if (sscanf_s(commandLine, "%c %d %c", &command, 1, &nodeNo, &direction, 1) == 3) {
				cutNode(nodeNo, direction);
			}
			break;
			
			//コマンドがどれでもなければ、ヘルプ表示を行う。
		default:
			showHelp();
		}

		//現在の木構造を表示する。
		showTree();

		//コマンド行を受け取り、その先頭のコマンド文字を取り出す。
		cout << "> ";
		cin.getline(commandLine, LINELENGTH);
		sscanf_s(commandLine, "%c", &command, 1);
	}
}

//
//----木構造を表示する。-----
//
void showTree()
{
	int nodeLevel;    //ノードの根からの深さ

	//ノードカウンタ（ノード番号を数える）をリセットする。
	nodeCounter = 0;

	//ノードレベル（根からの深さ）をリセットにする。
	nodeLevel = 0;

	//木の表示再帰を呼び出す。
	showTreeRecursive(pRoot, nodeLevel);
}

//
//----木構造の再帰表示を行う。----
//
void showTreeRecursive(Node* pNode, int nodeLevel)
{
	//ノードポインタがnullならば戻る。
	if (pNode == NULL) return;

	//ノードレベルをインクリメントする。
	nodeLevel++;

	//ノードポインタの指すノード（現ノード)の右ポインタについて木の再帰表示を行う。
	showTreeRecursive(pNode->pRight, nodeLevel);

	//ノードカウンタをインクリメントする。
	nodeCounter++;

	//ノードレベルに合ったインデンションを付け、ノードカウンタと現ノードの単語を表示する。
	for (int i = 0; i < nodeLevel; i++) cout << "\t";
	cout << nodeCounter << ": " << pNode->word << endl;

	//現ノードの左ポインタについて木の再帰表示を行う。
	showTreeRecursive(pNode->pLeft, nodeLevel);
}

//
//----指定番号のノードを探索する。-----
//
Node* searchNode(int searchNodeNo)
{
	//ノードカウンタをリセットする。
	nodeCounter = 0;

	//ノードの再帰探索を行い、その戻り値を持って戻る。
	return searchNodeRecursive(pRoot, searchNodeNo);
}

//
//-----ノードの再帰探索を行う。------
//
Node* searchNodeRecursive(Node* pPresentNode, int searchNodeNo)
{
	Node* pFoundNode;    //発見したノードへのポインタ

	//ノードポインタがNULLならば、戻り値をNULLにして戻る。
	if (pPresentNode == NULL) return NULL;

	//ノードポインタが参照するノード(現ノード）の右ポインタについてノードの再帰探索を行う。
	pFoundNode = searchNodeRecursive(pPresentNode->pRight, searchNodeNo);

	//戻り値がNULLでなければ、その戻り値を持って戻る。
	if (pFoundNode != NULL) return pFoundNode;

	//ノードカウンタをインクリメントする。
	nodeCounter++;

	//ノードカウンタが探索ノード番号に等しければ、現ノードポインタを持って戻る。
	if (searchNodeNo == nodeCounter)    return pPresentNode;

	//現ノードの左ポインタについてノードの再帰探索を行う。
	pFoundNode = searchNodeRecursive(pPresentNode->pLeft, searchNodeNo);

	//その戻り値を持って戻る。
	return pFoundNode;
}

//
//----ノードを追加する。-----
//
void addNode(string word, int nodeNo, char direction)
{
	Node* pParentNode;    //親ノードへのポインタ
	Node* pChildNode;    //子ノードへのポインタ

	//ノード番号に対応する親ノードを探索してノードポインタを得る。
	pParentNode = searchNode(nodeNo);

	//ノードポインタがNULLであれば戻る（探索失敗）。
	if (pParentNode == NULL) return;

	//方向指示の先が空いていなければ戻る。
	if (direction == LEFT && pParentNode->pLeft != NULL)return;
	if (direction == RIGHT && pParentNode->pRight != NULL)return;

	//新しく子ノードのメモリ領域を確保する。
	pChildNode = new Node;

	//子ノードの内容を設定する。
	pChildNode->word = word;
	pChildNode->pLeft = pChildNode->pRight = NULL;

	//子ノードを親ノードの方向指示の先につなぐ。
	if (direction == LEFT)pParentNode->pLeft = pChildNode;
	if (direction == RIGHT)pParentNode->pRight = pChildNode;
}

//
//----ノードを切り取る。-----
//
void cutNode(int nodeNo, char direction)
{
	Node* pNode;    //ノードへのポインタ

	//ノード番号に対応するノードを探索してノードポインタを得る。
	pNode = searchNode(nodeNo);

	//ノードポインタがNULLならば戻る(探索失敗）。
	if (pNode == NULL) return;

	//方向指示が右であれば以下を実行する。
	if (direction == RIGHT) {

		//ノードの右ポインタについて再帰削除を行う。
		deleteNodeRecursive(pNode->pRight);

		//ノードの右ポインタをNULLにする。
		pNode->pRight = NULL;
	}

	//方向指示が左であれば以下を実行する。
	if (direction == LEFT) {

		//ノードの左ポインタについて再帰削除を行う。
		deleteNodeRecursive(pNode->pLeft);

		//ノードの左ポインタをNULLにする。
		pNode->pLeft = NULL;
	}
}

//
//-----ノードの再帰削除を行う。------
//
void deleteNodeRecursive(Node* pNode)
{
	//ノードポインタがNULLならば戻る。
	if (pNode == NULL) return;

	//ノードポインタの右ポインタについてノードの再帰削除を行う。
	deleteNodeRecursive(pNode->pRight);

	//ノードポインタの左ポインタについてノードの再帰削除を行う。
	deleteNodeRecursive(pNode->pLeft);

	//ノードポインタの参照するノードのメモリ領域を解放する。
	delete pNode;
}

//
//----ヘルプを表示する。------
//
void showHelp()
{
	//コマンド一覧を表示する。
	cout << "A word n L|R  = Add：wordをn番の左(L)または右(R)に追加" << endl;
	cout << "X      n L|R  = Cut：n番の(L)または右(R)を切り取り" << endl;
	cout << "E             = End：プログラムを終了" << endl;
}

//
//----ノードを挿入する。-----
//
void insertNode(string word, int nodeNo, char direction) {

	Node* pNode;    //ノードへのポインタ
	
	//ノード番号に対応するノード(以下、現ノード)を探索して、現ノードへのポインタを得る。
	pNode = searchNode(nodeNo);

	//ポインタがNULLならば探索失敗なので戻る。
	if (pNode == NULL) return;

	//挿入する新規ノードのメモリ領域を確保する。
	Node* pNewNode; //新規ノードへのポインタ

	pNewNode = new Node();

	//新規ノードに単語を設定し、左右ポインタをNULLにする。 
	pNewNode->word = word;
	pNewNode->pRight = NULL;
	pNewNode->pLeft = NULL;

	//方向指示が左ならば以下を実行する。
	if (direction == LEFT) {

		//新規ノードの左ポインタに、現ノードの左ポインタを入れる。 (新規ノードの左ポインタ「の変数領域」に、現ノードの左ポインタ「の値」を入れる。) 
		pNewNode->pLeft = pNode->pLeft;

		//現ノードの左ポインタに、新規ノードへのポインタを入れる。
		pNode->pLeft = pNewNode;
	}

	//方向指示が右ならば以下を実行する。
	if (direction == RIGHT) {
		
		//新規ノードの右ポインタに、現ノードの右ポインタを入れる。
		pNewNode->pRight = pNode->pRight;

		//現ノードの右ポインタに、新規ノードへのポインタを入れる。
		pNode->pRight = pNewNode;
	}
}

//
//----ノードを削除する。-----
//
void deleteNode(int nodeNo, char direction) {

	Node* pNode;    //ノードへのポインタ

	//ノード番号に対応するノード(現ノード）を探索してポインタを得る。
	pNode = searchNode(nodeNo);

	//ポインタがNULLならば探索失敗であるので戻る。
	if (pNode == NULL) return;

	//方向指示に対応する左右ポインタから、削除対象ノードへのポインタを得る。
	Node* pDeleteNode=new Node;
	if (direction == RIGHT) pDeleteNode = pNode->pRight;
	if (direction == LEFT) pDeleteNode = pNode->pLeft;

	//ポインタがNULLであれば削除対象ノードが無いので戻る。
	if (pDeleteNode== NULL) return;
	
	//削除対象ノードの下に子ノードが2つあれば削除できないので戻る。
	if (pDeleteNode->pRight != NULL && pDeleteNode->pLeft != NULL)return;
	
	//存在する子ノードへのポインタを得る（子ノードが無いならばNULL）。
	Node* pChildNode=new Node;
	if (direction == RIGHT)pChildNode= pDeleteNode->pRight;
	if (direction == LEFT)pChildNode = pDeleteNode->pLeft;
	if (pDeleteNode->pRight == NULL && pDeleteNode->pLeft == NULL) pChildNode = NULL;

	//子ノードへのポインタを、方向指示に対応して現ノードの左右ポインタのどちらかに入れる。
	if (direction == RIGHT)pNode->pRight = pDeleteNode->pRight;
	if (direction == LEFT)pNode->pLeft = pDeleteNode->pLeft;

	//削除対象ノードのメモリ領域を解放する。
	delete pDeleteNode;
}

このコードで実行すると，削除対象ノードは削除されるのですが，削除対象ノードの子が削除ノードのあった位置に接続されません．
正しく出力されるには，削除する関数のコードをどのように直したら良いでしょうか？
教えてください．よろしくお願いします．

Comments

[episteme]

https://dixq.net/forum/viewtopic.php?f=3&t=20835

teratailはマルチポストを「好ましくない」としています。
https://teratail.com/help#posted-otherservice

Answer 1

指定ノードの左右と、削除対象ノードの左右を混同しています。

void deleteNode(int nodeNo, char direction) {

    Node* pNode;    //ノードへのポインタ

    //ノード番号に対応するノード(現ノード）を探索してポインタを得る。
    pNode = searchNode(nodeNo);

    //ポインタがNULLならば探索失敗であるので戻る。
    if (pNode == NULL) return;

    //方向指示に対応する左右ポインタから、削除対象ノードへのポインタを得る。
    Node* pDeleteNode;
    if (direction == RIGHT) pDeleteNode = pNode->pRight;
    if (direction == LEFT) pDeleteNode = pNode->pLeft;

    //ポインタがNULLであれば削除対象ノードが無いので戻る。
    if (pDeleteNode== NULL) return;

    //削除対象ノードの下に子ノードが2個あれば削除できないので戻る。
    if (pDeleteNode->pRight != NULL && pDeleteNode->pLeft != NULL) return;
    Node* pChildNode; // に、
    //削除対象ノードの下に子ノードが0個ならばNULLをセット。
    if (pDeleteNode->pRight == NULL && pDeleteNode->pLeft == NULL) pChildNode = NULL;
    //それ以外のケースは削除対象ノードの下に子ノードが1個なのでそれをセット
    else pChildNode = pDeleteNode->pRight ? pDeleteNode->pRight : pDeleteNode->pLeft;
    //間違っていた → else pChildNode = pDeleteNode->pRight || pDeleteNode->pLeft;

    //子ノードへのポインタを、方向指示に対応して現ノードの左右ポインタのどちらかに入れる。
    if (direction == RIGHT) pNode->pRight = pChildNode;
    if (direction == LEFT) pNode->pLeft = pChildNode;

    //削除対象ノードのメモリ領域を解放する。
    delete pDeleteNode;
}

でしょうか。ifの後の単文はブレースで囲まない主義なようなので、それはそのままにしてあります。普通は単文でも複数文の時のように囲みます。

あと、直後で捨てるnew Nodeを2つ書いていますが、これはdeleteせずに捨てられるので、解放漏れになるのでは？

Comments

[otn]

deleteNodeの部分だけしか見ていませんので、他の部分にもおかしいところがあるかもしれません。

[otn]

ああ、失礼しました。C/C++だとこういう書き方はだめですね。
else pChildNode = pDeleteNode->pRight ? pDeleteNode->pRight : pDeleteNode->pLeft;
でしょうか。冗長ですが。
回答を直しておきます。

[退会済みユーザー]

otnさんが書いてくださったコードで実行してみましたが，削除対象ノードの子が削除ノードのあった位置に接続されませんでした．
また，Node* pDeleteNode;と書いたところ，「初期化されていないローカル変数 'pDeleteNode' が使用されています」という
エラーが出ます．
削除対象ノードの子を削除ノードのあった位置に接続するには，他にどの部分を修正したらよいのか教えて頂けませんか？
よろしくお願いします．