树使用递归遍历非常方便,如果将代码拉伸开来,我们能否是否非递归代码来实现呢?当然是可以的,我们只要把递归的循环步骤修改为while就可以了。但我们需要借用到STL的栈模型来实现这个需求,具体的步骤如下:
- 步骤1:
如果结点有左子树,该结点入栈,并放弃其左子树;
如果结点没有左子树,访问该结点; - 步骤2:
如果结点有右子树,重复步骤1;
如果结点没有右子树(结点访问完毕),根据栈顶指示回退,访问栈顶元素,并访问右子树,重复步骤1
如果栈为空,表示遍历结束。
【实现代码】
TirTNode* findLeft(TirTNode* tree, std::stack<TirTNode*>& st) { if (nullptr == tree) return nullptr; // 持续遍历,到没有左子树为止 while (tree->leftChild != nullptr) { // 该结点入栈 st.push(tree); // 并继续向下找左子树 tree = tree->leftChild; } // 返回传递进来的 tree 最深的左子树 return tree; } void myTreeOrder(TirTNode* tree) { std::stack<TirTNode*> st; TirTNode* pLeft = findLeft(tree, st); // 返回回来的是没有左子树的节点 while (nullptr != pLeft) { // 打印没有左子树的节点 printf("%c ", pLeft->data); // 判断节点是否有右子树 if (nullptr != pLeft->rightChild) { // 如果有,则遍历这个树下最深的左子树 pLeft = findLeft(pLeft->rightChild, st); } else //如果节点没有右子树(节点访问完毕),弹出并访问栈顶元素,并且访问右子树 { // 判断栈是否为空 if (!st.empty()) { // 访问栈顶元素 pLeft = st.top(); // 弹出 st.pop(); } else { // 遍历完成 return; } } } }
调用时,只需给 myTreeOrder 函数传递一个树根节点的地址就可以了。在函数内部会自动打印出每个节点的内容。
myTreeOrder(&treeA);