当前位置: 代码迷 >> 综合 >> 非递归实现二叉树的各种遍历
  详细解决方案

非递归实现二叉树的各种遍历

热度:50   发布时间:2024-01-16 13:38:33.0

逛知乎看到有人去微软面试遇到让白板写非递归的二叉树的中序遍历,自己想了一下,非递归基本上就是用栈模拟,其他还好,后序遍历比较难写。

参考博客:点击打开链接


#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
typedef struct treenode
{char data;treenode *left,*right;
}treenode,*Bitree;void CreateTree(Bitree &ptree)//创建树,因为要改变指针(形参),所以使用引用或者二级指针
{char ch;scanf("%c", &ch);if (ch == ' '){ptree = NULL;return;}else{ptree = (treenode*)malloc(sizeof(treenode));ptree->data = ch;CreateTree(ptree->left);CreateTree(ptree->right);}
}
void InorderStack(treenode *ptree)//利用栈实现中序遍历
{stack<Bitree> Stack;while (ptree || !Stack.empty()){while (ptree != NULL){Stack.push(ptree);ptree = ptree->left;}ptree = Stack.top();Stack.pop();printf("%c", ptree->data);ptree = ptree->right;}
}
void PreorderStack(treenode *ptree)//非递归先序遍历
{stack<Bitree> Stack;while (ptree || !Stack.empty()){while (ptree){Stack.push(ptree);printf("%c", ptree->data);ptree = ptree->left;}ptree = Stack.top();Stack.pop();ptree = ptree->right;}
}
void PostorderStack(treenode *ptree)//非递归后序遍历
{int flag[100];//用flag数组标记该节点的右子树是否已经遍历过stack<Bitree> Stack;while (ptree){Stack.push(ptree);flag[Stack.size()] = 0;ptree = ptree->left;}while (!Stack.empty()){ptree = Stack.top();while (ptree&&ptree->right&&flag[Stack.size()] == 0)//ptree可能为空指针,此时没有ptree->right{flag[Stack.size()] = 1;//右子树已遍历ptree = ptree->right;while (ptree){Stack.push(ptree);flag[Stack.size()] = 0;ptree = ptree->left;}}ptree = Stack.top();printf("%c", ptree->data);Stack.pop();}}
int main()
{treenode *tree;CreateTree(tree);PreorderStack(tree);printf("\n");InorderStack(tree);printf("\n");PostorderStack(tree);printf("\n");return 0;
}


  相关解决方案