第4关：非递归实现二叉树左右子树交换

#include <iostream>
#include "binary_tree.h"

BiTreeNode* CreatBiTree(char* s, int &i, int len)
// 利用先序遍历创建二叉树
// 参数：先序遍历字符串s，字符串初始下标i=0，字符串长度len。
// 返回：二叉树
{
    BiTreeNode* root;
    char item = s[i++];
    if(i>=len || item=='#')
    {
        root=NULL;
    }
    else
    {
        root = new BiTreeNode(item);
        root->left = CreatBiTree(s, i, len);
        root->right = CreatBiTree(s, i, len);
    }
    return root;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    char str[200];
    scanf("%s", str);
    
    int i = 0;
    int len = int(strlen(str));
    BiTreeNode* root = CreatBiTree(str, i, len);

    root = BiTreeChangeStack(root);

    PostOrder(root);
    
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#ifndef binary_tree_h
#define binary_tree_h

#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct BiTreeNode {
    char data;              //  树节点元素
    BiTreeNode* left;       //  左子树指针
    BiTreeNode* right;      //  右子树指针
    BiTreeNode(){           //  树节点初始化
        left=NULL;
        right=NULL;
    }
    BiTreeNode(char item){  //  用元素初始化树节点
        data=item;
        left=NULL;
        right=NULL;
    }
    ~BiTreeNode(){          //  释放树节点内存
        left=NULL;
        right=NULL;
    }
};

BiTreeNode* CreatBiTree(char* s, int &i, int len);
// 利用先序遍历创建二叉树
// 参数：先序遍历字符串s，字符串初始下标i=0，字符串长度len。
// 返回：二叉树

BiTreeNode* BiTreeChangeStack(BiTreeNode* root);
// 实现二叉树左右子树的交换（栈实现）
// 参数：二叉树根节点root
// 返回：二叉树

void PostOrder(BiTreeNode* root);
// 二叉树的后序遍历
// 参数：二叉树根节点root
// 输出：二叉树的后序遍历，中间没有空格，末尾不换行。

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include "binary_tree.h"
#include<bits/stdc++.h>

BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换（栈实现）
// 参数：二叉树根节点root
// 返回：二叉树
{
   
    stack<BiTreeNode*>s;
    BiTreeNode*temp=NULL,*node=root;
    if(root==NULL)return NULL;
    s.push(root);
    while(!s.empty()){
    	temp=node->left;
    	node->left=node->right;
    	node->right=temp;
    	if(node->right!=NULL){
    		s.push(node->right);
		}
		if(node->left!=NULL){
			node=node->left;
		}else{
			node=s.top();
        	s.pop();
		}
	}
	return node;
    
}


void PostOrder(BiTreeNode* root)
// 二叉树的后序遍历
// 参数：二叉树根节点root
// 输出：二叉树的后序遍历，中间没有空格，末尾不换行。
{
 
    if(root==NULL)return;
    if(root->left!=NULL){
    	PostOrder(root->left);
	}
	if(root->right!=NULL){
		PostOrder(root->right);
	}
	cout<<root->data;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48