序二叉树遍历是如何工作的?c++

Question

void IntBinaryTree::insert(TreeNode*& tree, int num) {
//[1] Base Case: is the node empty?
if (!tree) {  // if node is empty, create one
tree = new TreeNode(num);
return;
}
//[2] Does the value already exist in the tree?
if (tree->value == num)
return;
//[3] node passed not empty? If less than head pass left otherwise right
if (tree->value > num)
insert(tree->left, num);
else
insert(tree->right, num);
}
void IntBinaryTree::displayInOrder(TreeNode* root) {
if (root) {
displayInOrder(root->left);
std::cout << root->value << " ";
displayInOrder(root->right);
}
}

我想了解为什么displayInOrder函数工作?假设有一个这样的树:

5
/ 
3    7
/   / 
1  4 6  8

为了按数字顺序显示这棵树，你需要先读取左边最左边的值，然后是根，然后是右边最左边的值，然后是最右边的值。

现在，displayinorder函数以if条件开始。简单地说，如果输入不等于false，那么继续向左。我的问题是，一旦我们得到了最左边的值(1，在我上面的例子中)，下一次调用"displayInOrder(root->left);";等于最左边的值1(默认是NULL)，NULL不会使if条件为假吗?

为什么这个函数似乎知道不调用1的最左边的值?

Answer 1

这是因为递归。在displayInOrder(root->left)的递归调用中，当前根指针被设置为指向root->left。但是我们知道根(在这个上下文中，它是前一个调用留下的根)指向null。因此，if块不会被执行，并且递归会回溯到它的调用函数(当根不为空且值为1时)。然后执行下一行代码，将1打印到控制台。然后类似的过程继续下去，直到递归结束。希望这对你有帮助!

Answer 2

它实际上调用显示节点(1)的左子节点，但这是NULL或nullptr，我们知道if(NULL)等同于if(false)，因此displayinorder(node1->left)的调用将不会进入if并直接返回到调用方displayinorder(node1)。

// stack of function calls
display(5)
->display(3)
-> display(1)
-> display(NULL)
print 1
-> display(NULL)
print 3
-> display(4)
-> display(NULL)
print 4
-> display(NULL)
print 5
-> display(7)
// ...