[C++] Thắc mắc về thuật toán chèn vào cây nhị phân

[tara95]

Chào mọi người, mình có bài tập thắc mắc mong mọi người giải thích giùm mình

#include <iostream>
#include <conio.h>

using namespace std;
typedef struct tagTNode
{
	int Key;
	struct tagTNode* pLeft;
	struct tagTNode* pRight;
}TNode;
typedef TNode* Tree;


TNode *CreateTNode (int x)
{
	TNode *p;
	p = new TNode;
	if (p == NULL)
	{
		cout << "\nHet bo nho";
		getch ();
		exit (1);
	}
	p -> pLeft = NULL;
	p -> pRight = NULL;
	p -> Key = x;
	return p;
}

int insertNode (Tree &T, int x)
{
	if (T)
	{
		if (T->Key == x) return 0;       // Da ton tai khoa trong cay
		if (T->Key > x) return insertNode (T->pLeft,x);
		else
			return insertNode (T->pRight,x);
	}
	T = new TNode;
	if (T == NULL)                  // Het bo nho
	{
		cout << "\nHet bo nho";
		return -1;
	}       
	T -> Key = x;
	T -> pLeft = NULL;
	T -> pRight = NULL;
	return 1;
}

int insertTNode (Tree &T, TNode *a)           // [COLOR="#FF0000"]Mình debug thấy hàm này có vấn đề, mà không nhận ra vấn đề ở đâu mặc dù tuơng tự hàm trên[/COLOR]
{
	if (T)
	{
		if (T->Key == a->Key) return 0;
		if (T->Key > a->Key) insertTNode (T->pLeft,a);
		else 
			insertTNode (T->pRight,a);
	}
	T = new TNode;
	if (T == NULL)
	{
		cout << "\nThieu bo nho";
		return -1;
	}
	T->Key = a->Key;
	T->pLeft = NULL;
	T->pRight = NULL;
	return 1;
}
int main ()
{
	Tree T = NULL;
	T = CreateTNode (0);
	TNode *a = CreateTNode (3);
	insertNode (T,1);
	insertNode (T,2);
	insertTNode (T,a);

	TNode *p = T;
	while (p != NULL)
	{
		cout << p->Key << "  ";
		p = p->pRight;
	}

	getch ();
	return 0;
}

Kết quả mình muốn in ra là 0 1 2 3, nhưng chạy thì chỉ ra mỗi 3. Lỗi này đối với bài này mình đã sửa được. Nhưng có điều mình thắc mắc là thử DEBUG cả 2 hàm trên, chúng hoàn toàn tương tự nhau, nhưng cách nhảy và xử lý lại khác nhau.

[13520797]

#include <iostream>
#include <conio.h>

using namespace std;
typedef struct tagTNode
{
    int Key;
    struct tagTNode* pLeft;
    struct tagTNode* pRight;
}TNode;
typedef TNode* Tree;


TNode *CreateTNode (int x)
{
    TNode *p;
    p = new TNode;
    if (p == NULL)
    {
        cout << "\nHet bo nho";
        getch ();
        exit (1);
    }
    p -> pLeft = NULL;
    p -> pRight = NULL;
    p -> Key = x;
    return p;
}

int insertNode (Tree &T, int x)
{
    if (T)
    {
        if (T->Key == x) return 0;       // Da ton tai khoa trong cay
        if (T->Key > x) return insertNode (T->pLeft,x);
        else
            return insertNode (T->pRight,x);
    }
    T = new TNode;
    if (T == NULL)                  // Het bo nho
    {
        cout << "\nHet bo nho";
        return -1;
    }       
    T -> Key = x;
    T -> pLeft = NULL;
    T -> pRight = NULL;
    return 1;
}

int insertTNode (Tree &T, TNode *a)           // Mình debug thấy hàm này có vấn đề, mà không nhận ra vấn đề ở đâu mặc dù tuơng tự hàm trên
{
    if (T)
    {
        if (T->Key == a->Key) return 0;
        if (T->Key > a->Key) return insertTNode (T->pLeft,a);         [COLOR=#ff0000]//them chu return[/COLOR]
        else 
            return insertTNode (T->pRight,a);               [COLOR=#ff0000] //them chu return[/COLOR]
    }
    T = new TNode;
    if (T == NULL)
    {
        cout << "\nThieu bo nho";
        return -1;
    }
    T->Key = a->Key;
    T->pLeft = NULL;
    T->pRight = NULL;
    return 1;
}

}

đó là do bạn đệ qui đi xuống sâu mà ko nghĩ rằng khi gọi tiếp thì phải qua cái đoạn dưới nó.làm nó đè lên.
mình thì làm như sau:

int add_key_tree(tree &T,int x)
{
    if(T)
    {
        if(T->key==x)    {
            return 0;    //ko xu li truong hop bi trung
        }
        if(T->key>x)    add_key_tree(T->l,x);
        if(T->key<x)    add_key_tree(T->r,x);

    }
    else                //rong thi tao
    {
        T = new node;
        if(T==NULL    )    return -1;
        else
        {
            T->key=x;
            T->l=T->r=NULL;
        }
        return 1;

    }
}

phần mình return là khi nó tìm ra đúng chổ để add vào thì nó quay về vs đệ qui mẹ thì bị cái return ấy sẽ kéo nó qua khỏi cái đám ở dưới

[tara95]

Thank cậu, thì ra thiếu chữ return.