二叉树的创建和销毁

💦 二叉树的创建和销毁

//二叉树创建
BTNode* BinaryCreatBinaryTree();
// 二叉树销毁
void BinaryTreeDestroy(BTNode* root);

❗ BinaryCreatBinaryTree && BinaryTreeDestroy ❕

    注意对于 BinaryTreeDestroy 使用后序的方式销毁

#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}
//创建二叉树
BTNode* BinaryCreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;

	return node1;
}
//后序销毁二叉树
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}
int main()
{
	BTNode* root = BinaryCreatBinaryTree();
	BinaryTreeDestroy(root);
	root = NULL;
	return 0;
}

💦 二叉树的构建及遍历＜难度系数⭐＞

📝 题述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

   输入包括1行字符串，长度不超过 100。

输出描述：

   可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个
   空格。 每个输出结果占一行。

💨 示例 ：

   输入：abc##de#g##f###

   输出：c b e g d f a

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

❗ 注意此题不同于上面的几道接口题，这里是 I/O 类型的题需要我们自己创建树 ❕

根据题意中先序遍历的字符串可以得到：

先前序构建树，再中序输出树

nowcode原题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

struct TreeNode
{
	char val;
	struct TreeNode* left;
	struct TreeNode* right;
};
//前序构建树
struct TreeNode* CreatTree(char* str, int* pi)
{
	if (str[*pi] == '#')
	{
		//空树数组的下标也要++，且为它malloc空间
		(*pi)++;
		return NULL;
	}
	//malloc空间
	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
	//前序递归
	root->val = str[(*pi)++];
	root->left = CreatTree(str, pi);
	root->right = CreatTree(str, pi);

	return root;
}
//中序输出树
void InOrder(struct TreeNode* root)
{
	if (root == NULL)
		return;
	InOrder(root->left);
	printf("%c ", root->val);
	InOrder(root->right);
}
int main()
{
	char str[100];
	scanf("%s", str);
	int i = 0;
	struct TreeNode* root = CreatTree(str, &i);
	InOrder(root);
	return 0;
}