Как найти внутренние узлы в двоичном дереве?

Question

У меня уже есть способ найти внешние узлы, но я понятия не имею, чтобы подсчитывать внутренние узлы, чтобы кто-то помог вам.

Answer 1

Вы можете преобразовать следующий псевдокод на любой язык в соответствии с вашими предпочтениями.

function count_internal_nodes(curr): 
     if curr == null: return 0 
     else if curr is leaf: return 0 
     else: return 1 + count_internal_node(curr.left) + 
         count_internal_nodes(curr.right) 

Answer 2

Вы можете попробовать этот Algo

getInteriorNodes(self) 
    count = 0 
    hasLeft, hasRight = self.left<>null, self.right <>null 
    if (hasLeft) 
     count += self.left.getInteriorNodes() 
    else if (hasRight) 
     count += self.right.getInteriorNodes() 
    else if ((hasLeft || hasRight) && self.parent) 
     count += 1 
return count