Tìm phần tử dương nhỏ nhất trên cây nhị phân tìm kiếm

[VietReam]

cho cây nhi phân tìm kiếm viết hàm trả về node chứ phần tử dương nhỏ nhất , nếu ko có trả về null

#include <iostream>
typedef int item; //kieu item la kieu nguyen
struct Node
{
	item key; //truong key cua du lieu
	Node* Left, * Right; //con trai va con phai
};
typedef Node* Tree;  //cay

int insertNode(Tree& T, item x)	// chen 1 Node vao cay
{
	if (T != NULL)
	{
		if (T->key == x) return -1; 	// Node nay da co
		if (T->key > x) return insertNode(T->Left, x);	// chen vao Node trai
		else if (T->key < x) return insertNode(T->Right, x);	// chen vao Node phai
	}
	T = (Node*)malloc(sizeof(Node));
	if (T == NULL) return 0;	// khong du bo nho
	T->key = x;
	T->Left = T->Right = NULL;
	return 1;	// ok
}

void CreateTree(Tree& T)		// nhap cay
{
	int x;
	while (1)
	{
		printf("Nhap vao Node: ");
		scanf_s("%d", &x);
		if (x == 0) break; 	// x = 0 thi thoat
		int check = insertNode(T, x);
		if (check == -1) printf("Node da ton tai!");
		else if (check == 0) printf("Khong du bo nho");

	}
}

// Duyet 
Node* Min(Tree T)
{
	if (T->Left != NULL && T->Right != NULL)
	{
		if (T->key < 0) {
			Node* rs = Min(T->Right);
			return  rs == NULL ? NULL : rs;
		}
		else {
			Node* rs = Min(T->Left);
			return  rs == NULL ? T : rs;
		}
	}
	else if (T->Left == NULL && T->Right != NULL) {
		if (T->key > 0) { return T; }
		else {
			Node* rs = Min(T->Right);
			return  rs == NULL ? NULL : rs;
		}
	}
	else if (T->Right == NULL && T->Left != NULL) {
		if (T->key > 0) {
			Node* rs = Min(T->Left);
			return  rs == NULL ? T : rs;
		}
		else {
			return NULL;
		}
	}
	else {
		if (T->key > 0) { return T; }
		else {
			return NULL;
		}
	}
}

int main()
{
	Tree T;
	T = NULL; //Tao cay rong

	CreateTree(T); //Nhap cay
	Node* x = Min(T);
	printf("\n");
}

đây là code của em chạy thì được nhưng em thấy nó chưa đc tối ưu ạ , anh nào có cách giải khác chỉ em với

[rogp10]

Nên chia theo node hiện tại là <=0 hay >0 trước, như vậy chỉ còn có hai nhánh lớn thôi.

Dùng tính chất các node ở cây con trái đều < cha và các node ở cây con phải đều > cha.

[VietReam]

nhưng node có thể nhận cả giá trị âm và dương nên node dương nhỏ nhất có thể nằm ở cả nhánh trái và phải luôn anh

[tntxtnt]

vì cây ko balance nên trường hợp xấu nhất nó chỉ có node 1 bên thì cái tree nó như 1 dslk, duyệt kiểu nào cũng mất O(n) à, ko tối ưu hơn được đâu :V

viết vậy cho ngắn gọn :V

 Node* Min(Tree T) {
    if (!T) return NULL;
    Node* L = Min(T->Left);
    Node* R = Min(T->Right);
    if (L && L->key >= 0) return L;
    if (T->key >= 0) return T;
    if (R && R->key >= 0) return R;
    return NULL;
}