如何在二叉树中查找内部节点？

Question

我已经找到了查找外部节点的方法，但我不知道如何计算内部节点，所以请有人帮忙。

Answer 1

你可以试试这个算法

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

Answer 2

您可以根据自己的喜好将以下伪代码转换为任何语言。

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)

如何在二叉树中查找内部节点？

How to find internal nodes in binary tree?

binary-tree

data-structures