题解 | 二叉树遍历

#include<bits/stdc++.h>
#define int long long
#define _for(i, a, b) for(int i = a;i < b;++i)
#define _rep(i, a, b) for(int i = a;i <= b;++i)
int readll(){int x; scanf("%lld", &x); return x;}
using namespace std; 

typedef struct TNode{
	char val;
	struct TNode *left, *right, *up;
}*Tree;

void pre_traversal(Tree p){
	if(p -> val != '#')	cout<<p -> val<<' ';
	if(p -> left != NULL) pre_traversal(p -> left);
	if(p -> right != NULL) pre_traversal(p -> right);	
}

void in_traversal(Tree p){
	if(p -> left != NULL) in_traversal(p -> left);
	if(p -> val != '#')	cout<<p -> val<<' ';
	if(p -> right != NULL) in_traversal(p -> right);	
}

void post_traversal(Tree p){
	if(p -> left != NULL) post_traversal(p -> left);
	if(p -> right != NULL) post_traversal(p -> right);
	if(p -> val != '#')	cout<<p -> val<<' ';
}

signed main(){
	Tree PNode = new TNode;
	string preorder;
	cin>>preorder;
	int len = preorder.size();
	Tree temp;
	int direction = 0;
	TNode * t = new TNode;
		//initialize
	t -> left = NULL;
	t -> right = NULL;
	t -> up = NULL;
	t -> val = preorder[0];
	temp = t;
	PNode = t;//point to the first node;
	_for(i, 1, len - 1){
		//cout<<i<<endl;
		TNode * t2 = new TNode;
		//initialize
		t2 -> left = NULL;
		t2 -> right = NULL;
		t2 -> up = NULL;
		t2 -> val = preorder[i];
		
		if(direction == 0){
			t2 -> up = temp;
			temp -> left = t2;
		}
		if(direction == 1){
			t2 -> up = temp;
			temp -> right = t2;
		}
		if(preorder[i] != '#')	temp = t2;
		else	while(temp->left != NULL && temp->right != NULL)	{temp = temp -> up;}
		
		if(temp -> left == NULL)	direction = 0;
		else if(temp -> right == NULL)	direction = 1;
	}
	//pre_traversal(PNode);
	in_traversal(PNode);
	//post_traversal(PNode);
	return 0;
}