(c语言)Tree Traversals Again (25分)

关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！

浙大Mooc数据结构的解题集

---

---

---

下面是关于这道题的谷歌翻译

关于这道题的闲谈

我是真的吐了 这道题明明我记得我是上传了的 而且还写了很久很久的思路解析 但是我在整理文章解题专栏的时候 竟然找不到这道题的博客！ 他跑哪里去了？ 我真的吐了！ 哎 我现在还得写一遍 看一遍题 看看吧- -
那道题我当时真的花了很久时间写的 真的解析很详细很详细的
因为我做出来就不是很容易啊… 难过

---

---

---

关于这道题的思路

首先我们再理一遍这道题要干什么吧
利用我们的Push和Pop操作从而确定唯一的二叉树
且我们不难发现Push和Pop操作的规律
在这之前我们先确定一个事情

前序+中序 ->后序
后序+中序 ->前序
前序+后序 -> 中序个???? 不一定的

然后在这道题中我还记得当时解题的突破口是发现
每次我们Push的时候 如果没有左节点 则生成左节点
如果有了左节点 则生成右节点 （重点！）
而这道题我看了看后面的代码
我是利用的堆栈来解决的问题

而Pop是以前序来Pop的 就这两点从而解决问题
希望大家能够通过下面代码（有注释的）理解一下思路吧
主要是重新回顾这道题 太久了 太详细的东西不是很记得到了
只记得到最重点的解题突破口了 请原谅我

---

---

---

下面是代码实现

#include <stdio.h>
#include <stdlib.h>//用来清空缓冲区的
#include <string.h>
#define Max 30
typedef int tree;
typedef int Element;

//我看了下后面的代码 这里主要是为了
//后面找Root根节点而设置的bool true false
//当第一个Push进入时 则确定了Root
typedef int bool;
#define true 1
#define false -1
#define Null -1

typedef struct TreeNode
{
    Element Data;
    tree Left;
    tree Right;
} Tree;

//以结构体数组建立的树 最大有30个结点
Tree T[Max];
int Maxnumber;

tree ReBuild(Tree T[])
{
	
    tree Root;

	//count计数进行了几次操作 从而确定后面的退出操作
    int count=0;
    
    scanf("%d",&Maxnumber);
    int stack[Max];
    int top = -1, bottom = -1;
    bool Judge = false;
    int tempnumber;

	//确定当前位置的工具人
    tree Position;
	
	//用来检测操作的字符串
    char tempstr[4];
    Position = Null;
    do
    {
		
		
		//清空缓冲区 防止后面读入被干扰 我喜欢这样保个险hhh
        fflush(stdin);

		//这里注意一下 细节 先读入字符串
		//如果是Push则在读入数字
		//如果是Pop则不读入
        scanf("%4s",&tempstr);
        if(!strcmp(tempstr,"Push"))
        {
            scanf("%d",&tempnumber);
            if(Judge == false)
            {
                Judge = true;
                Root = tempnumber;
            }
            else
            {

				//先看左边结点是不是空的
				//左边不是空的再看右边
				//赋值左右结点
                if(T[Position].Left == Null)
                    T[Position].Left = tempnumber;
                else
                   T[Position].Right = tempnumber;
				
            }
				   //在堆栈上面存储该数字
                   stack[++top] = tempnumber;
                   
                   /*其实Position可以理解为指标
                   工具人作用 表示指向当前哪个位置
                   也方便了赋值操作
                   其实堆栈操作的Position也就是方便了
                   记录当前节点走到什么位置的功能
                   因为可以记录节点走到了什么位置
                   此时就可以实现右节点的赋值功能
             	   希望大家可以手画一下堆栈了进行手动的出栈入栈
             	   再结合代码来分析一下
             	   我仔细想了一下还是挺清晰的
             	   Push没有左节点就赋值左节点
             	   堆栈为确认当前位置来设置
             	   Position表示当前位置
             	   希望大家能够理解:)*/
                   Position = stack[top];

				   //T[Position].Data = Position;
				   //注意就是这个地方 向数组进行了赋值
                   T[Position].Data = Position;
                   T[Position].Left = Null;
                   T[Position].Right = Null;
        }
        else if(!strcmp(tempstr,"Pop"))
        {
            Position = stack[top];
            top--;
        }
        count++;
    } while(count != 2*Maxnumber );
    return Root;
}

//基本的输出操作
void printtree(tree position)
{
    if(position == Null)
        return;
    else
    {
        printtree(T[position].Left);
        printtree(T[position].Right);

		//这里防止了多打出空格
        if(--Maxnumber)
        printf("%d ",position);
        else
        printf("%d",position);
    }
}

//主函数尽量简洁 基本功能都在上面实现了
int main()
{
    tree Root;
    Root = ReBuild(T);
    printtree(Root);
    return 0;
}

因为是很久以前做的这道题了
肯定有些地方我也没有第一次写的那么细了
真不知道是哪个人给我把之前的博客删了 qswl
但大体思路还是讲明了 希望能对大家有所帮助吧