Tính tổng trong 1 lần duyệt cây nhị phân

#1

Anh chị cho em hỏi có cách làm tính tổng được các giá trị của nút trong 1 lần diệt , mà không cần phải lưu các nút của cây vào ( như danh sách liên kết ) để tính tổng không ạ ?

#2

Dùng giải thuật Depth First Search hoặc Breadth First Search. Theo mình thì dùng cái thứ nhất dễ hơn.
Bạn học cây Nhị Phân chắc cũng biết 2 cái giải thuật này nhỉ ? :grin:

#3

mình đã thử 2 cách rồi , nhưng không ra :frowning:

#4

Bạn post code lên đi, có thể code của bạn gặp vấn đề gì chăng ?

#5 
int sumTree(BstNode *root) {
	int result = 0;
	if (root == NULL)
		return 0;
	else {
		result += root->data;
		sumTree(root->left);
		sumTree(root->right);
	};
	return result;
}

Code của mình :slight_smile:

#6

sumTree của left right bạn phải cộng vào result nữa chứ

1 Like
#7

em cảm ơn anh , em hiểu ra vấn đề rồi :smiley:

#8

À, thì ra phương thức của bạn dùng đệ quy :grin:
Phương thức này gập 1 vấn đề là: giả sử mình bắt đầu gọi đệ quy với tham số là root thì kết quả trả về là data của root thôi còn hàm: [quote=“Khang_Viet, post:5, topic:37411”]
sumTree(root->left);
sumTree(root->right);
[/quote]

2 phương thức trên bạn gọi nhưng không lấy giá trị trả về của chúng thì sao cộng tiếp được :grin:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?