Vấn đề khi thêm node vào cây nhị phân có 2 hoặc >2 node trong cây có giá trị giống nhau

DwarfFungi · March 12, 2022, 9:05am

e có 1 thắc mắc là nếu cây nhị phân(cây nhị phân thường, k phải cây tìm kiếm hay cân bằng) có 2 phần tử trùng nhau , 2 node bằng nhau , thì khi thêm 1 node vào cây nó sẽ như thế nào?
chương trình của e, thêm 1 node vào cây nhị phân với cú pháp
(lựa chọn thêm trái phải_ node cha_node con)
1 = them trái,
2 = thêm phải
ví dụ,
1 40 40
2 40 30
nhưng khi trong cây nhị phân có 2 node 40 chẳng hạn thì thêm bằng cách nào ?
làm sao để vét cạn hết các node và so sánh với 40, hàm tìm sự tồn tại của node cha của e viết tìm được node đầu có giá trị = node cha đưa vào thì sẽ dừng lại và thêm
xincamon

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct tagnode{
	int data;
	tagnode *left, *right;
}*node;   

void createTree(node &); 
node createNode(int )
void createRoot(node &);  
node searchParent(node , int );
void addLeft(node &, int , int );
void addRight(node &, int , int );
void NLR(node );
void LNR(node );
void LRN(node );
//------------------------------------------------
main(){
	node root;

	createTree(root);
	createRoot(root);
	int cha, con, traiphai;
	printf ("Nhap them node cho cay theo cu phap (1,cha,con) hoac (2,cha,con)\n");
	printf ("1 = them vao cay con trai\n2 = them vao cay con phai\ncha = node cha ; con = node con\n");
	printf ("Nhap 0 de thoat\n");
	do{
		scanf("%d", &traiphai);
		if (traiphai == 0 ) break;
		scanf("%d", &cha,&con);
		if (traiphai==1) addLeft(root, cha, con);
		else  addRight(root,cha, con);
	}
	while (1);
	
	printf ("\nDuyet cay theo thu tu truoc NLR\n");
	NLR(root);
	printf ("\nDuyet cay theo thu tu giua LNR\n");
	LNR(root);
	printf ("\nDuyet cay theo thu tu sau LRN\n");
	LRN(root);
	getch();
	return 0;
}
//------------------------------------------------
void createTree(node &root){
	root = NULL;
}
//------------------------------------------------
node createNode(int data){
	node temp; 
	temp = (node)malloc(sizeof(node));  
	temp->data = data;
	temp->left = NULL;
	temp->right = NULL;
	return temp;
}
//------------------------------------------------
void createRoot(node &root){
	if (root == NULL) {
		printf("Cay rong, them root\nNhap data cho node root   ");
		int data;
		scanf ("%d",  &data);
		root = createNode(data);
	}
}
//------------------------------------------------
node searchParent(node root, int cha){
	if (root == NULL) return NULL;
	if (root->data == cha) return root;
	node temp = searchParent(root->left, cha);
	if (temp == NULL) searchParent(root->right, cha);
	return temp;
}
//------------------------------------------------
void addLeft(node &root, int cha, int con){
	node temp = searchParent(root, cha);
	if (temp == NULL){
		printf("Node cha khong ton tai\n");
		return;
	}
	if (temp->left != NULL){
		printf("Node %d da co cay con trai\n", cha);
		return;
	}
	node son = createNode(con);
	temp->left = son;	
}
//------------------------------------------------
void addRight(node &root, int cha, int con){
	node temp = searchParent(root, cha);
	if (temp == NULL){
		printf("Node cha khong ton tai\n");
		return;
	}
	if (temp->right != NULL){
		printf("Node %d da co cay con phai\n", cha);
		return;
	}
	node son = createNode(con);
	temp->right = son;	
}
//------------------------------------------------
void NLR(node root){
	if (root != NULL){
		printf ("%d\t", root->data);
		NLR(root->left);
		NLR(root->right);
	}
}
//------------------------------------------------
void LNR(node root){
	if (root != NULL){
		NLR(root->left);
		printf ("%d\t",  root->data);
		NLR(root->right);
	}
}
//------------------------------------------------
void LRN(node root){
	if (root != NULL){
		NLR(root->left);
		NLR(root->right);
		printf ("%d\t",  root->data);
	}
}
//------------------------------------------------

Gio · December 16, 2015, 2:56pm

Thêm 1 thuộc tính vào node đó là dem để đếm các giá trị giống nhau. Khi insert, tìm thấy thì tăng dem, khi xoá thì giảm dem , dem==0 thì xoá node

Minh_Meo · December 16, 2015, 3:10pm

với cây nhị phân thông thường thì nếu gía tri thêm mới đã có trong cây thì sẽ không thêm nữa
còn nếu bạn muốn biết một gía trị có bao nhiêu phần tử thì có thể cài đặt cấu trúc dạng:

//c++
typedef struct Data{
    int value;
    data *next;
}
typedef struct TagNode{
   Data data;
  TagNode *left, *right; 
}

trong đó mỗi node data là một link list.

hoặc đơn giản là thêm số lần xuất hiện của các gíá trị lặp:

typedef struct TagNode{
   int data;
   int soLanXuatHien;
  TagNode *left, *right; 

}

DwarfFungi · December 16, 2015, 3:13pm

nhưng mình muốn tìm ra node đó để thêm cây con trái hoặc cây con phải ấy
ví du

thì trong cây có 2 node 50

Minh_Meo · December 16, 2015, 3:13pm

điều kiên của cây tìm kiếm nhị phân chuẩn là không có 2 node giống hệt nhau nhé

DwarfFungi · December 16, 2015, 3:21pm

mình đang làm cây nhị phần thường bạn à, trên mình có nói rồi mà

Minh_Meo · December 16, 2015, 4:44pm

nết bạn thích vét cạn:

//c++
node result[100];
int count = 0;
node[] search(node root, int key,node result[], int &count){
	if (root == NULL) return NULL;
	if(root.data == key){
              
               count++;
        }
        result = search(root->left, key, result, count);
	resuult = search(root->right, key, result, count);
	return result;
}

cơ bản là thế, nhưng bạn nên tham khảo thêm trong các tại liệu nhé