如何计算二进制search树中的比较？

我有一个类的二进制节点，二叉树和二叉search树，它们包含您的基本树函数，如查找节点，添加节点，删除节点，获取高度，getnumberof节点，以及其他类似的。 我试图添加一个新的函数来计算在树中查找某个特定节点的比较次数，但是我迷惑了自己。 我能做的最好的是检查节点是否在树中，但我无法弄清楚如何使计数器与每个比较增量。 我试图做的方法只是很难翻译成我现在的代码。 我只是不认为我这样做是正确的。 如果有人能帮我解决这个问题，我真的会赞赏它。

int counter = 0; template<class ItemType> ItemType BinarySearchTree<ItemType>::IsInTree(BinaryNode<ItemType>* BinTreePtr, const ItemType& item) { BinaryNode<ItemType>* tmp = BinTreePtr; counter++; if (tmp == NULL) { printf("Number of comparisons: \n", counter); return 1; } else { counter++; if (&tmp->getItem == item) { printf("Number of comparisons: \n", counter); return 0; } else { counter++; if (item < &tmp->g) return IsInTree(tmp->leftChildPtr, item); else return IsIntree(tmp->rightChildPtr, item); } } } int main(){ BinarySearchTree<string>* tree1Ptr = new BinarySearchTree<string>(); tree1Ptr->add("10"); tree1Ptr->add("20"); tree1Ptr->add("30"); tree1Ptr->add("40"); tree1Ptr->add("50"); tree1Ptr->add("60"); tree1Ptr->add("70"); tree1Ptr->add("80"); counter = 0; tree1Ptr->IsInTree(tree1Ptr, "10"); } 

Answer 1

初始化计数器值为1，并且在条件内的每个比较之前递增计数器到if语句

 if (tmp == NULL) { printf("Number of comparisons: \n", counter-1); return 1; } else { if (counter++ && &tmp->getItem == item) { printf("Number of comparisons: \n", counter-1); return 0; } else { if (counter++ && item < &tmp->g) return IsInTree(tmp->leftChildPtr, item); else return IsIntree(tmp->rightChildPtr, item); } } 

计数器1会给你计数，希望这有助于