目录
结构体及头文件：
1.二叉树的前序遍历
题目描述：
思路分析：
源码：
2.二叉树的翻转
题目描述：
思路分析：
源码：
3.另一颗子树
题目描述：
思路分析：
源码：
4.二叉树的遍历
题目描述：
思路分析：
源码：
结构体及头文件：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
1.二叉树的前序遍历
题目描述：
给你二叉树的根节点
root，返回它节点值的前序遍历
思路分析：
设计条件：按照前序遍历（根——左子树——右子树）的方式遍历这棵树，访问左子树和右子树的时候同样按照这样的方式遍历，直到完整遍历这棵树。
判断条件设计：如果节点为空，直接返回。
成立条件设计：定义preorder表示当前遍历到root节点的答案，将root节点的值加入答案，递归调用preorder（root->left）来遍历这颗root节点的左子树，再调用preorder（root->right）遍历root节点右子树即可。
源码：
void preorder(BTNode * root, int* res, int* resSize)
{
if (root == NULL) {
return;
}
res[(*resSize)++] = root->val;
preorder(root->left, res, resSize);
preorder(root->right, res, resSize);
}
int* preorderTraversal(BTNode * root, int* returnSize)
{
int* res = malloc(sizeof(int) * 2000);
*returnSize = 0;
preorder(root, res, returnSize);
return res;
}2.二叉树的翻转
题目描述：
给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点
思路分析：
设计条件：从根节点开始对树进行遍历，并从叶子节点开始翻转。
判断条件设计：如果节点为空，直接返回。
成立条件设计：遍历到的节点的root的左右两课子树都已经翻转，只需交换两课子树的位置，完成以root为根节点的整颗子树的翻转。
源码：
BTNode* invertTree(BTNode* root)
{
if (root == NULL)
{
return NULL;
}
BTNode* left = invertTree(root->left);
BTNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}3.另一颗子树
题目描述：
给你两棵二叉树
root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。二叉树
tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
思路分析：
源码：
bool isSametree(BTNode * A, BTNode * B)
{
//递归终止
if (A == NULL && B == NULL)
{
return true;
}
if ((A == NULL && B != NULL) || (A != NULL && B == NULL))
{
return false;
}
//递归处理子问题
if (A->val == B->val)
{
if ((isSametree(A->left, B->left)) && isSametree(A->right, B->right))
{
return true;
}
}
//最上层尾操作
return false;
}
bool isSubtree(BTNode * root, BTNode * subRoot)
{
//递归终止
if (root == NULL)
{
return false;
}
//递归处理子问题
if (root->val == subRoot->val)
{
if (isSametree(root, subRoot))
{
return true;
}
}
if (isSubtree(root->left, subRoot))
{
return true;
}
if (isSubtree(root->right, subRoot))
{
return true;
}
//最上层尾操作
return false;
}4.二叉树的遍历
题目描述：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果
思路分析：
设计条件：分治思想，递归构建二叉树，构建二叉树先malloc出根节点然后再构建左子树，右子树即可。
判断条件设计：如果节点为空，直接返回。
成立条件设计：字符串需要构建之后指针向后移动找到下一个字符，需要一个count指针标记字符位置，构建之后指针向后移动，指针指向’#‘或者'\0'代表到了空节点了完成返回NULL即可。
源码：
BTNode* maketree(char* arr, int* count)
{
if (arr[*count] == '#' || arr[*count] == '\0')
{
return NULL;
}
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->val = arr[(*count)++];
newnode->left = maketree(arr, count);
(*count)++;
newnode->right = maketree(arr, count);
return newnode;
}
void Inorder(BTNode* root)
{
if (root == NULL)
{
return;
}
Inorder(root->left);
printf("%c ", root->val);
Inorder(root->right);
}
int main()
{
char arr[101];
scanf("%s", arr);
int count = 0;
BTNode* tree = maketree(arr, &count);
Inorder(tree);
return 0;
}
