二叉树三种遍历方式的非递归写法/构建二叉树

1 参考链接 这里

2 利用原二叉树的扩展二叉树的前序遍历序列构建二叉树,并对该二叉树进行中序遍历（非递归）

#include <cstdio>
#include <stack>
#include <iostream>
using namespace std;

//树节点表示
typedef struct BiTNode
{
    int value;
    struct BiTNode *lchild,*rchild;
}BiTNode ,*BiTree;

//中序遍历的非递归写法
void inorder_circle(BiTree root)
{
    if(root==NULL)
        return;
    BiTree node=root;
    stack<BiTree> s;
    while(!s.empty()||node)
    {
        while(node)
        {
            s.push(node);
            node=node->lchild;
        }

        if(!s.empty())
        {
            node=s.top();
            s.pop();
            printf("%c",node->value);
            node=node->rchild;
        }
    }
    printf("\n");
}

//前序遍历构建二叉树
void PreCreateTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=new BiTNode;
        (*T)->value=ch;
        PreCreateTree(&(*T)->lchild);
        PreCreateTree(&(*T)->rchild);

    }
}

int main()
{
    BiTree p;

    printf("前序遍历构建二叉树\n");
    PreCreateTree(&p);
    printf("中序遍历输出二叉树\n");
    inorder_circle(p);
    return 0;
}
           

3 二叉树的镜像（剑指offer面试题27）

解法一：前序遍历的递归写法(把遍历节点打印节点值的操作改为判断节点左右孩子是否同时为空指针，若不是那么交换左右孩子)

void Mirror(BinaryTreeNode *pNode)
{
    if(pNode!=NULL)
    {
        if(pNode->left!=NULL||pNode->right!=NULL)
        {
             BinaryTreeNode *temp=pNode->left;
             pNode->left=pNode->right;
             pNode->right=temp;
        }
        Mirror(pNode->left);
        Mirror(pNode->right);
    }
}
           

解法二：前序遍历的非递归写法

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot!=nullptr)
        {
            stack<TreeNode *> s;
            TreeNode *p=pRoot;
            while(!s.empty()||p)
            {
                while(p)
                {
                    if(p->left!=nullptr||p->right!=nullptr)
                    {
                        TreeNode *temp=p->left;
                        p->left=p->right;
                        p->right=temp;

                    }
                    s.push(p);
                    p=p->left;
                }
                if(!s.empty())
                {
                    p=s.top();
                    s.pop();
                    p=p->right;
                }
            }
        }
        
        
    }
};
           

解法三：后序遍历的递归形式。

解法四：后序遍历的非递归形式。