c语言数据结构 二叉树（三）

1.二叉树的遍历

题目要求：

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

例：

代码实现如下：

#include
#include

//定义二叉树结构
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.前序遍历、中序遍历得到的数据可以确定唯一的一棵二叉树。前序遍历确定根，中序遍历确定左右子树区间。

后序遍历、中序遍历得到的数据可以确定唯一的一棵二叉树。后序遍历倒着确定根，中序遍历确定左右子树区间。

前序遍历、后序遍历得到的数据不可以确定唯一的一棵二叉树，可能会得到多个树。前序遍历确定根，后序遍历倒着确定根。

怎么我觉得在学校学习好不方便啊？各位老铁，有没有这样的感受呢？