Thêm dữ liệu vào cây

[quan01 (Anh Quân)]

thầy cho e hỏi tại sao chương trình của e ko in ra dữ liệu

#include<iostream>

using namespace std;

struct node{
	int data;
	node* left;
	node* right;	
};

class BST{
	node *root;
	public:
		BST(){
			root = NULL;
		}
		
		node* Add(int x){
			node* t = root;
			t = insert(x,t);	
			return t;
		}
		node* insert(int x, node* root){
			if(root==NULL){
				root = new node();
				root -> data = x;
				root -> left = NULL;
				root -> right = NULL;

			}
			if(x<root->data){
				root->left = insert(x,root->left);
			}
			else if(x>root->data){
				root->right = insert(x,root->right);
			}
			return root;
		}
		
		void Display(){
			return inOrder(root);
		}
		void inOrder(node *root){
			if(root==NULL) return;
			inOrder(root->left);
			cout<<" "<<root->data;
			inOrder(root->right);
		}
};


int main(){

	BST tree;
	tree.Add(3);
	tree.Add(5);
	tree.Add(2);
	tree.Add(1);
	tree.Display();
	
	return 0;
}

``````````````

[kisuluoibieng (Tên Gì Cũng Được)]

code này có chạy được không nhỉ?

[tntxtnt]

@quan01

node* t = root;
t = insert(x,t);
return t;

tại sao lại cần t ở đây :V Viết thế kia thì t = ... chứ có phải root = ... đâu

[quan01 (Anh Quân)]

ok thank bạn

node* Add(int x){			
				return insert(x,root);				
		}

vẫn sai

[tntxtnt]

sao ở dưới ghi thế này

root->left = insert(x,root->left);

tại sao hàm insert trả về node* làm gì?

tại sao cần gán root->left = ...; mà ko viết là insert(x,root->left);?

[quan01 (Anh Quân)]

if(x<root->data){
	 insert(x,root->left);
}

bởi vì nếu như làm như thế này thì cây chỉ hiển thị giá trị đầu tiên

[tntxtnt]

:V

phải gán root->left = ... là vì nếu trường hợp root->left == NULL thì trong hàm insert, root->left sẽ được gán = new node();. Như vậy giá trị root->left thay đổi. Mà truyền root->left vào insert(...) là truyền theo tham trị, nên thực tế giá trị root->left ko thay đổi mà chỉ có copy của nó là bị thay đổi :V Vì vậy hàm insert phải trả về root truyền vào đó, để bên ngoài gán lại: root->left = insert(...) đề phòng trường hợp root->left bị thay đổi giá trị :V

ví dụ:

• root->left có giá trị là 0, hay NULL
• truyền vào hàm insert(22, root->left) tương đương insert(x=22, root=NULL) trong đó root là 1 bản copy của root->left, ko phải root->left
• trong hàm insert, ktra thấy root == NULL, nên gán root = new node();, lúc này ví dụ root = 0x12345600, trỏ tới node nằm ở địa chỉ 0x12345600
• xong xuôi trả về root tức là insert trả về giá trị 0x12345600
• lúc này bên ngoài root->left vẫn chứa giá trị NULL, ko thay đổi gì. Phải gán root->left = insert(22, root->left); tức là gán root->left = 0x12345600 thì lúc này root->left mới trỏ tới node được cấp phát mới trong insert.

vì vậy phải viết là root = insert(x, root) trong hàm Add

nếu ko muốn gán như vậy thì truyền root vào hàm insert theo tham chiếu:

void insert(int x, node*& root) // trả về void ko cần trả về node* nữa

// nếu truyền theo tham chiếu như vậy thì Add ko còn trả về node* được nữa :V 
void add(int x) { insert(x, root); }
void insert(int x, node*& root) {
  ...
  if (x < root->data) {
    insert(x, root->left);
  } else if(x > root->data) {
    insert(x, root->right);
  }
}

[quan01 (Anh Quân)]

cảm ơn bạn nhưng bạn nhìn lại mk dùng void hay node* ạ

[rogp10]

Hàm thêm xóa sẽ trả về mã lỗi hoặc không trả về gì cả. Ngoài ra không nên trả về những gì có liên quan đến cấu trúc nội tại.

[tntxtnt]

nếu ko xài tham chiếu thì phải gán root = insert(x, root) trong hàm Add. Có đọc hết những gì mình giải thích ko