コマンドは、以下の形式とします.
「 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;
if (pDeleteNode->pRight == NULL && pDeleteNode->pLeft == NULL) pChildNode = NULL;
else pChildNode = pDeleteNode->pRight ? pDeleteNode->pRight : pDeleteNode->pLeft;
//子ノードへのポインタを、方向指示に対応して現ノードの左右ポインタのどちらかに入れる。
if (direction == RIGHT)pNode->pRight = pChildNode;
if (direction == LEFT)pNode->pLeft = pChildNode;
//削除対象ノードのメモリ領域を解放する。
delete pDeleteNode;
}
正しく出力されるには,削除する関数のコードをどのように直したら良いでしょうか?
教えてください.よろしくお願いします.