Đếm inner node trong tree structure

#1

Cho mình hỏi có cách nào để đếm số node trong (inner node) của một cây. Mình có tìm hiểu nhưng chỉ thấy đếm luôn cả root node.
Tks all

#2

Việc đếm hết tất cả các node rồi trừ đi 1 node root có làm hài lòng bạn không?

3 Likes
#3

Ý mình là dùng thuật toán ý

#4

mình thử bằng python đây bạn

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

def count_inner_nodes(node):
    if len(node.children) == 0:
        return 0
    else:
        count = 1
        for child in node.children:
            count += count_inner_nodes(child)
        return count

# Tạo cây mẫu
root = Node(1)
child1 = Node(2)
child2 = Node(3)
child3 = Node(4)
root.children = [child1, child2, child3]
child4 = Node(5)
child5 = Node(6)
child1.children = [child4, child5]

# Đếm số inner node
inner_node_count = count_inner_nodes(root)
print("Số inner node trong cây là:", inner_node_count)
#5

Bạn có vấn đề gì với thuật toán đếm số node của 1 cây???

#6

Nếu chỉ trừ 1 thì vẫn còn trường hợp cây 0 hay 1 node, nếu ko muốn trừ 1 thì dùng hàm trên quét hết cây con của root.

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