题解 | 二叉树遍历 分治法创建树+递归中序遍历

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;

struct TreeNode {
	char data;
	TreeNode* left;
	TreeNode* right;
};

// 分治法
TreeNode* RecursiveBuildTree(int &i,char str[]) {
	char c = str[i];
	i++;
	if (c == '#') {
		return NULL;  // 此子树为空子树
	}
	else {
		TreeNode* pNew = new TreeNode;  // 有意义的字符(创建结点存数据)
		pNew->data = c;  // 数据域
		pNew->left = RecursiveBuildTree(i, str); // 左指针指向递归得到
		pNew->right = RecursiveBuildTree(i, str); // 右指针指向递归得到 左边完成下一个字符到右边
		return pNew;  // 所有子树都构建好，返回根节点
	}
}

void InOrder(TreeNode* proot) {
	if (proot == NULL) {  // 叶子节点下层
		return;
	}
	else {
		InOrder(proot->left);
		printf("%c ",proot->data);
		InOrder(proot->right);
	}
}

int main() {
	char str[1000] = { 0 };
	while (scanf("%s", str) != EOF) {
		int i = 0;
		TreeNode* proot = RecursiveBuildTree(i,str); // 得到树的根节点
		InOrder(proot);
	}
	
	return 0;
}