计算 BST 中单个 child 的节点

Question

我有这个问题：实现函数 int countSingle()，它使用 Breadth-First 遍历 (BFT) 来计算树中有多少节点具有单个 child。

所以下面的代码是我想到的解决它的方法，是否有另一种方法或我错过的更有效的方法？

template <class T>
        int BST<T>::countSingle()
        {
            QueueDLL<BSTNode<T>*> queue;
            BSTNode<T>* node = root;

            // If the tree is empty, there will be no nodes to traverse.
            if(node == NULL) return -1;

            // Initially, put the root in the queue
            queue.Enqueue(node);
            int counter = 0 ;

            while(queue.IsEmpty() == false)
            {
                // Take a node out of the queue, process it and then insert
                // its children into the queue.
                node = queue.Dequeue();

                // if the node has one only one child wether its the left or the right , increase counter
                if((node->left == NULL && node->right != NULL) || (node->right== NULL && node->left!=NULL))
                    counter++;

                if(node->left != NULL)
                    queue.Enqueue(node->left);
                if(node->right != NULL)
                    queue.Enqueue(node->right);
            }
            return counter;
        }

Answer 1

这看起来还不错。你不能真正提高你所做的事情的复杂性，因为操作的数量是线性的。

几个实施要点：

计数是非修改操作，因此您可能需要考虑 consting 一些东西。
你基本上已经自己实现了类似于编译器在递归中所做的事情。如果那是意图 - 很好（并且有一些性能点对您有利）。仅供参考，您可以使用很少的 LOC 进行递归。

计算 BST 中单个 child 的节点

Counting Nodes with single child in BST

c++

tree-traversal

binary-search-tree