ツリーがうまくできません【初心者】

[nyu]

任意のノードを消したいのですがうまくいきません
どのように修正したらよいでしょうか

コード:

#include "stdafx.h"
#include <stdlib.h>
#include <string.h>
#pragma warning (disable:4996)

struct tnode {
	struct tnode *left;
	char          name[256];
	struct tnode *right;
};


typedef struct tnode NODE;

NODE *Search(NODE *p, char *dat);
void  Del(NODE *p);
NODE *gentree(NODE *, char *);
void  treewalk(NODE *);
NODE *talloc(void);



int main()
{
	char dat[256], command[256];
	NODE *root;

	root = NULL;

	while (1) {
		printf("command: ");
		scanf("%s", command);

		
		switch (command[0]) {
		case 'i': // 1ノードの追加
			printf("Name? ");
			scanf("%s", dat);
			root = gentree(root, dat);
			break;
		case 'w': // 木のトラバーサル
			printf("Tree:\n");
			treewalk(root);
			break;
		case 'd': // 部分木の削除
			printf("Name? ");
			scanf("%s", dat);
			root = Search(root, dat);
			break;
		case 'q': // プログラム終了
			exit(0);
			break;
		default: // ヘルプ表示
			printf("i: input / w: walk / ");
			printf("d: delete\n");
		}
	}

}

NODE *Search(NODE *p, char *dat)
{
	if (p == NULL) return p;

	if (strcmp(dat, p->name) == 0) {
		Del(p);
		return NULL;
	}

	if (strcmp(dat, p->name) < 0) {
		p->left = Search(p->left, dat);
		return p;
	}
	else {
		p->right = Search(p->right, dat);
		return p;
	}
}


void Del(NODE *p)
{
	NODE *sp;
	sp = NULL;

	if ((p->right == NULL)&&(p->left == NULL)) {
		free(p),p=NULL;
	}


	if ((p->right !=NULL && p->left != NULL)) {
		sp = p->right;

		if (sp->left == NULL) {
			sp->left = p->left;
			sp = p;
			p=p->right;
			free(sp);
		
		}
		else {
			while (sp->left->left != NULL)sp = sp->left;
			sp->left->left = p;
			p = sp->left;
			sp->left = p->right;
			p->right = p->left->right;
			sp = p->left;
			p->left = p->left->left;
		}
	}

	else {
	sp = p;
	if (p->left != NULL)p = p->left,free(sp);
	else if (p->right != NULL)p = p->right,free(sp);
	}
}


NODE *gentree(NODE *p, char w[])
{
	if (p == NULL) {
		p = talloc();
		strcpy(p->name, w);
		p->left = p->right = NULL;
	}
	else if (strcmp(w, p->name) < 0)
		p->left = gentree(p->left, w);
	else
		p->right = gentree(p->right, w);

	return p;
}


void treewalk(NODE *p)
{
	if (p != NULL) {
		treewalk(p->left);
		printf("%s\n", p->name);
		treewalk(p->right);
	}
}


NODE *talloc(void)
{
	NODE *p;

	p = (NODE *)malloc(sizeof(NODE));
	if (p == NULL) {
		fprintf(stderr,
			"Cannot allocate memory.\n");
		exit(1);
	}
	return p;
}

ノードのデリートは以下の部分です

コード:

void Del(NODE *p)
{
	NODE *sp;
	sp = NULL;

	if ((p->right == NULL)&&(p->left == NULL)) {
		free(p),p=NULL;
	}


	if ((p->right !=NULL && p->left != NULL)) {
		sp = p->right;

		if (sp->left == NULL) {
			sp->left = p->left;
			sp = p;
			p=p->right;
			free(sp);
		
		}
		else {
			while (sp->left->left != NULL)sp = sp->left;
			sp->left->left = p;
			p = sp->left;
			sp->left = p->right;
			p->right = p->left->right;
			sp = p->left;
			p->left = p->left->left;
		}
	}

	else {
	sp = p;
	if (p->left != NULL)p = p->left,free(sp);
	else if (p->right != NULL)p = p->right,free(sp);
	}
}

[みけCAT]

コード:

void Del(NODE *p)
{
	NODE *sp;
	sp = NULL;

	if ((p->right == NULL)&&(p->left == NULL)) {
		free(p),p=NULL;
	}


	if ((p->right !=NULL && p->left != NULL)) {

とりあえずすぐにわかることは、これだと最初の条件式を満たすときにNULL->rightを読み出そうとして死ぬので、
2番めのifをelse ifにした方がいいということですね。

[みけCAT]

コード:

	else {
	sp = p;
	if (p->left != NULL)p = p->left,free(sp);
	else if (p->right != NULL)p = p->right,free(sp);
	}
}

ここでどうせ消えるpに対する意味のない代入が行われている上、参照されているノードを開放してしまい誤動作の原因になりそうです。
DelとSearchの第一引数をNODE*型のデータを指すポインタにして、呼び出し元のデータを書き換えられるようにするべきである気がします。

[nyu]

コード:

void Del(NODE *p){ 
     }

のまま消したいときはどうしたら良いでしょうか

[nyu]

連投すみません

関数Del内を以下のコードのみにしてから(p->left != NULL && p->right == NULL　の場合だけ想定)

コード:

while (p->left){
				*(p->name) = *(p->left->name);
				p = p->left;
　　　　　　　　　　　　　　}

入力{ i, F, i, E, i, D, i, C, i, B, i, A}を順に与えた(i : ノード追加)
ツリー構造【A←B←C←D←E←F】の状態に対して

入力{ d, E}や{d, D}などの次に{w}を与えると　(d : デリート, w : ツリーの表示 )
削除対象以下も全て消え、表示上は親以上しか残っていない状態となるのですが
その理由がわかりません


（最左ノードが余分に残ることを無視すると
削除対象のnameの情報だけを上書きによって消しているだけのつもりなのですが...）

[かずま]

Del() を変更。addtree() を追加です。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable:4996)
 
struct tnode {
    struct tnode *left;
    char          name[256];
    struct tnode *right;
};
 
 
typedef struct tnode NODE;
 
NODE *Search(NODE *p, char *dat);
NODE *Del(NODE *p);                   /* 変更 */
NODE *addtree(NODE *p, NODE *q);      /* 追加 */
NODE *gentree(NODE *, char *);
void  treewalk(NODE *);
NODE *talloc(void);
 
 
int main()
{
    char dat[256], command[256];
    NODE *root;
 
    root = NULL;
 
    while (1) {
        printf("command: ");
        scanf("%s", command);
        
        switch (command[0]) {
        case 'i': // 1ノードの追加
            printf("Name? ");
            scanf("%s", dat);
            root = gentree(root, dat);
            break;
        case 'w': // 木のトラバーサル
            printf("Tree:\n");
            treewalk(root);
            break;
        case 'd': // 部分木の削除
            printf("Name? ");
            scanf("%s", dat);
            root = Search(root, dat);
            break;
        case 'q': // プログラム終了
            exit(0);
            break;
        default: // ヘルプ表示
            printf("i: input / w: walk / ");
            printf("d: delete\n");
        }
    }
}
 

NODE *Search(NODE *p, char *dat)
{
    if (p == NULL) return p;
 
    if (strcmp(dat, p->name) == 0) {
        return Del(p);               /* 変更 */
    }
 
    if (strcmp(dat, p->name) < 0) {
        p->left = Search(p->left, dat);
        return p;
    }
    else {
        p->right = Search(p->right, dat);
        return p;
    }
}
 
 
NODE *Del(NODE *p)
{
    NODE *sp;

    if (p->right == NULL)
        sp = p->left == NULL ? NULL : p->left;
    else if (p->left == NULL) 
        sp = p->right;
    else  {
        sp = p->left;
        p->left = addtree(sp, p->right);
    }
    free(p);
    return sp;
}
 

NODE *addtree(NODE *p, NODE *q)
{
    if (p == NULL)
        p = q;
    else if (strcmp(q->name, p->name) < 0) 
        p->left = addtree(p->left, q);
    else
        p->right = addtree(p->right, q);
    return p;
}
 
 
NODE *gentree(NODE *p, char w[])
{
    if (p == NULL) {
        p = talloc();
        strcpy(p->name, w);
        p->left = p->right = NULL;
    }
    else if (strcmp(w, p->name) < 0)
        p->left = gentree(p->left, w);
    else
        p->right = gentree(p->right, w);
 
    return p;
}
 
 
void treewalk(NODE *p)
{
    if (p != NULL) {
        treewalk(p->left);
        printf("%s\n", p->name);
        treewalk(p->right);
    }
}
 
 
NODE *talloc(void)
{
    NODE *p;
 
    p = (NODE *)malloc(sizeof(NODE));
    if (p == NULL) {
        fprintf(stderr,
            "Cannot allocate memory.\n");
        exit(1);
    }
    return p;
}

[かずま]

Del() を次のように修正します。

コード:

NODE *Del(NODE *p)
{
    NODE *sp;

    if (p->right == NULL)
        sp = p->left;
    else if (p->left == NULL) 
        sp = p->right;
    else
        sp = addtree(p->left, p->right);
    free(p);
    return sp;
}

もっと短く書くなら

コード:

NODE *Del(NODE *p)
{
    NODE *sp = !p->right ? p->left :
               !p->left ? p->right : addtree(p->left, p->right);
    free(p);
    return sp;
}

[nyu]

ありがとうございました

[かずま]

解決なら、何が悪かったのかをちゃんと書いてください。

私は、No.1 の「どのように修正したらよいでしょうか」という質問に回答しただけです。
この回答を元に、No.5 の次の質問の答えを見つけてほしかったのです。

入力{ i, F, i, E, i, D, i, C, i, B, i, A}を順に与えた(i : ノード追加)
ツリー構造【A←B←C←D←E←F】の状態に対して

入力{ d, E}や{d, D}などの次に{w}を与えると　(d : デリート, w : ツリーの表示 )
削除対象以下も全て消え、表示上は親以上しか残っていない状態となるのですが
その理由がわかりません

元のプログラムは、Search() でツリーをどんどん降りて行って、削除対象の
ノードを見つけ、Del() を呼び出して、そのノードを削除しています。
削除したら、その削除したノードにぶら下がっているノードをつなぎ直さないと
いけないのに、67行目で NULL を返しています。
これでは、削除したノードの下はすべて消えたことになります。

ぶら下がっていたノードのアドレスを Del() が返し、それを Search() が返すと、
71行目や 75行目でちゃんと繋ぎ直してくれます。
削除したノードの左にも右にも子があるときは、
それらをひとつにまとめないといけません。

そこで addtree() の登場ですが、これは悪いアルゴリズムで、右のノードが
左のノードの右の一番下のノードにぶら下がることになり、ツリーの高さが
高くなってしまいます。改良の余地ありです。