- // 定义二叉树结点
- struct BiTreeNode
- {
- int data;
- BiTreeNode* left;
- BiTreeNode* right;
- };
一, 递归实现
- // 先序
- void preOrder(BiTreeNode *root){
- cout<<root->data;
- preOrder(root->left);
- preOder(root->right);
- }
- // 中序
- void inOrder(BiTreeNode *root){
- preOrder(root->left);
- cout<<root->data;
- preOder(root->right);
- }
- // 后序
- void postOrder(BiTreeNode *root){
- preOrder(root->left);
- preOder(root->right);
- cout<<root->data;
- }
以上的 cout<<root->data; 是对结点的一种操作, 这里可以对结点做任意想做的操作.
二, 非递归实现
- // 先序
- void preOrderS(Node *root)
- {
- stack<Node*> s;
- Node *p=root;
- while(p!=NULL||!s.empty())
- {
- // 沿着左支走到底
- // 用栈记录走过的路径
- while(p!=NULL)
- {
- cout<<p->data<<" ";
- s.push(p);
- p=p->left;
- }
- // 当左支走到尽头时, 若栈里边还有结点
- // 则退栈, 后退到跟结点, 并且向右支前进
- // 此时 p!=NULL, 会进入以上 while 循环
- if(!s.empty())
- {
- p=s.top();
- s.pop();
- p=p->right;
- }
- }
- }
- // 注: 在 if(!s.empty()) 中, 获取根结点只是为了得到往右支的中转,
- // 当获得右支指针后, 将根结点从栈中弹出, 以便返回的时候直接
- // 回到爷爷结点
- // 中序
- void inOrderS(Node *root){
- stack<Node*> s;
- Node *p=root;
- while(p!=NULL||!s.empty()){
- while(p!=NULL)){
- s.push(p);
- p=p->left;
- }
- if(!s.empty()){
- p=s.top();
- s.pop();
- cout<<p->data;
- p=p->right;
- }
- }
- }
- // 中序遍历和先序遍历的代码几乎一致, 除了访问点的位置不一样
- // 中序遍历是在退栈的时候访问根结点
- // 后序
- void PostOrderS(Node *root) {
- Node *p = root, *r = NULL;
- stack<Node*> s;
- while (p!=NULL || !s.empty()) {
- if (p!=NULL) {// 走到最左边
- s.push(p);
- p = p->left;
- }
- else {
- p = s.top();
- if (p->right!=NULL && p->right != r)// 右子树存在, 未被访问
- p = p->right;
- else {
- s.pop();
- visit(p->val);
- r = p;// 记录最近访问过的节点
- p = NULL;// 节点访问完后, 重置 p 指针
- }
- }//else
- }//while
- }
- // 因为后序非递归遍历二叉树的顺序是先访问左子树, 再访问右子树, 最后访问根节点. 当用
- // 堆栈来存储节点, 必须分清返回根节点时, 是从左子树返回的, 还从右子树返回的. 所以,
- // 使用辅助指针 r, 其指向最近访问过的节点. 也可以在节点中增加一个标志域, 记录是否已被
- // 访问
来源: http://www.bubuko.com/infodetail-2872175.html