二叉樹三種周遊方式的非遞歸寫法/建構二叉樹

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;
                }
            }
        }
        
        
    }
};
           

解法三：後序周遊的遞歸形式。

解法四：後序周遊的非遞歸形式。