c语言数据结构 二叉树（三）
1.二叉树的遍历
题目要求：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
例：
代码实现如下：
#include<stdio.h>
#include<stdlib.h>
//定义二叉树结构
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
//a是先序遍历字符串名称 pi是先序遍历字符串的下标传址调用
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
//如果结点为空 向上一级函数返回NULL
if(a[*pi]=='#')
{
//少了此处也是致命的错误
(*pi)++;
return NULL;
}
//如果结点不为空，创建一个结点存储数据，并且将自身的地址传给上一级函数
BTNode* root=(BTNode*)malloc(sizeof(BTNode));
if(root==NULL)
{
perror("malloc fail");
return NULL;
}
root->data=a[*pi];
(*pi)++;
//子问题思想解决方法 处理完根，紧接着就要处理左右子树
root->left=BinaryTreeCreate(a,pi);
root->right=BinaryTreeCreate(a,pi);
return root;
}
//二叉树的中序遍历 左子树 根 右子树
void InOrder(BTNode* root)
{
if(root==NULL)
{
return;
}
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
//主体思路是将先序遍历得到的二叉树的数据构建一个二叉树，再以中序遍历的形式读取打印出来
int main()
{
//字符串长度是'\0'前字符个数
//如果用数组形式定义字符串就要考虑到‘\0’同样也是字符，数组长度要比字符串长度加一
char str[101]={0};
scanf("%s",str);
int i = 0;
BTNode* root=BinaryTreeCreate(str,&i);
InOrder(root);
}
在这里还穿插一个问题，在定义 BinaryTreeCreate的参数是数组下标传址调用，而不是char*。
char*是字符型指针，如果选择其作为参数，str相当于进行传值调用，形参只是实参的一份拷贝，并不会改变实参的值。要想对str直接传址调用，就必须用二级指针。是很麻烦的，不建议使用。
***二叉树的广度遍历
从根节点开始，沿着树的宽度遍历树的节点，直到所有节点都被遍历完为止。
如二叉树的广度遍历。
***二叉树的深度遍历
沿着树的深度遍历结点，尽可能深的搜索树的分支。如果当前的节点所在的边都被搜索过，就回溯到当前节点所在的那条边的起始节点。一直重复直到进行到发现源节点所有可达的节点为止。
如二叉树的前序遍历、中序遍历、后序遍历。
二叉树地前序遍历，严格地讲，是最符合深度优先遍历的准则。
2.二叉树的销毁
3.二叉树的层序遍历
思路：利用队列先进先出的原则，将二叉树的根先代入队列，将其取出后再带入其孩子结点代入队列。
在二叉树项目中并不包括对队列的定义和实现，可以将队列项目中重要的.c、.h文件粘贴复制到二叉树项目所在的文件夹中去，做一个快乐的cv工程师哈哈。
代码实现
对了，你的队列代码是有问题的。记得及时更改！！！
4.二叉树的层序遍历的变形
判断二叉树是否为完全二叉树
思路：依旧使用层序遍历的思想，当存入的数据出现NULL时，其后不会再出现非空的数据，则证明该二叉树为完全二叉树。
代码实现如下：
5.前序遍历、中序遍历得到的数据可以确定唯一的一棵二叉树。前序遍历确定根，中序遍历确定左右子树区间。
后序遍历、中序遍历得到的数据可以确定唯一的一棵二叉树。后序遍历倒着确定根，中序遍历确定左右子树区间。
前序遍历、后序遍历得到的数据不可以确定唯一的一棵二叉树，可能会得到多个树。前序遍历确定根，后序遍历倒着确定根。
怎么我觉得在学校学习好不方便啊？各位老铁，有没有这样的感受呢？