이진트리삽입삭제문제...

dlwogh8046의 이미지

중위순회로 삽입하고 후위순회로 삭제하려는데요..
코딩오류문제는 없음에도 불구하고 출력결과가 이상하게 나오네요..
어디쪽에 문제가 있는건가요?? ㅠㅠ 답답합니다;;

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
 
typedef struct TreeNode{
	int key;
	struct TreeNode *left,*right;
}TreeNode;
 
void insertNode(TreeNode *root, int key)
{
 
 
	TreeNode *p, *t;
	TreeNode *n,*succ;
 
	t=root;
	p=NULL;
 
	if(root)
	{
	insertNode(root->left ,key);
	while(t!=NULL)
	{
		if(key == t->key) return;
		p=t;
		if(key<p->key) 
			t=p->left;
		else 
			t=p->right;
	}
	n = (TreeNode*)malloc(sizeof(TreeNode));
	if(n==NULL) return;
	n->key = key;
	n->left = n->right = NULL;
	if(p!=NULL)
		if(key<p->key)
			p->left=n;
		else
			p->right=n;
	else root = n;
	insertNode(root->right ,key);
	}
}
 
void deleteNode(TreeNode *root, int key)
{
	TreeNode *p, *child, *succ, *succ_p, *t;
	p=NULL;
	t=root;
 
	if(root)
	{
	deleteNode(root->left,key);
	deleteNode(root->right,key);
	while(t!=NULL && t->key != key)
	{
		p=t;
		t=(key < p->key)? p->left : p->right;
	}
	if(t==NULL)
	{
		printf("찾고자하는 Key가 이진 트리에 없습니다.");
		return;
	}
	if((t->left==NULL)&&(t->right==NULL))
	{
		if(p!=NULL){
			if(p->left == t)
				p->left=NULL;
			else
				p->right=NULL;
		}
		else
			root=NULL;
	}
	else if((t->left==NULL)||(t->right=NULL))
	{
		child=(t->left!=NULL) ? t->left:t->right;
		if(p!=NULL)
		{
			if(p->left==t)
				p->left=child;
			else
				p->right=child;
		}
		else
			root=child;
	}
	else
	{
		succ_p=t;
		succ=t->right;
		while(succ->left!=NULL)
		{
			succ_p=succ;
			succ=succ->left;
		}
		if(succ_p->left==succ)
			succ_p->left=succ->right;
		else
			succ_p->right=succ->right;
		t->key = succ->key;
		t=succ;
	}
	free(t);
	}
}
 
void displayNode(TreeNode *root)
{
if(root!=NULL)
{
	displayNode(root->left);
	printf("%d ",root->key);
	displayNode(root->right);
}
}
 
int main()
{
int *n,i,r;
TreeNode *root = NULL;
srand((unsigned)time(NULL));
n = (int*)malloc(100*sizeof(int));
for(i=0; i<100; i++)
{
	r=(rand()%100)+1;
	n[i]=r;
	insertNode(root,n[i]);
}
displayNode(root);
}
yukariko의 이미지

insertnode 에서 노드를 찾는것을 2번 수행하네요.
중위순회를 하면서 그 안에서 이진탐색.. 이것은 이진트리에서 삽입하는 방법이 아닙니다. 특별한 목적이 있는게 아니라면요.
노드를 찾는 것은 이진탐색 1번으로 수행하는 것입니다.
main을 보니 root가 초기값이 null인데 insertnode 에선 null일경우의 처리가 없습니다.
그 외에도 이상한? 코드들이 몇몇 보이는데,
소스가 나와있는 책을 보고 다시 한번 따라해보시길 바랍니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.