数据结构----二叉树非递归实现

/*********构造二叉树*********/

输入一串以二叉树先序序列遍历的字符，空格表示空指针。

比如这串字符：ABD123CE4F5G678（为方便阅读，以数字代替空格），以先序顺序逆推出的二叉树应是：

从中观察出构造二叉树的算法：

以字符串的遍历为循环条件，构造一个栈来存放左右孩子指针都未被赋值的节点，空指针不允许入栈。

（1）循环开始前，让头节点先入栈

（2）str[i]表示当前字符（i初始值为1），若str[i-1]不是空格，那么str[i]一定是str[i-1]的左孩子；

若是空格，那么str[i]一定不是它的左孩子，即：str[i]一定是str[i-1]的右孩子，当右孩子被连接之后，

表明双亲节点的左右孩子指针均已赋值，那么就可以将这个双亲节点弹出，简化版：

if(str[i-1] != ' '){top->leftchild = creat_node(str[i]);}else{top->rightchild = creat_node(str[i]);pop(top);}

（3）如果str[i]不是空格，在一次循环完毕之前，还应将它入栈

Warning：

这里有个问题，我们是将节点从栈中弹出来修改其左右孩子指针的，仔细一想便会发现这些栈中的“节点”

并不是真正的二叉树节点，它们只是在内存中申请了一块连续的空间来寄存真正二叉树的节点，所以我们

是不能将节点直接连到栈中的元素的

Solution：

在每个节点里附设一个指向它本身的this指针，在连接的时候在this指针的内容里赋值，这样就可以保护

真正节点的内存地址了

/*********几种遍历二叉树*********/

一、前序遍历

以上图为例，前序遍历的顺序就是：ABDCEFG

前序遍历的算法依旧要借助栈来实现：

（1）栈中存放已被访问的节点

（2）先要往左走到最底端，也就是此时节点的左孩子为NULL

（3）然后向右走一步（通过出栈来获得其双亲节点数据，将当前指针指向它的右孩子即可）

（4）以这个右孩子为新的头节点，如果它为NULL，则继续出栈获得上一个双亲节点，在向右一步，重复

这个过程，直到栈为空或者有一个节点的右孩子不为NULL

（5）有了新的头节点后，重复（2）（3），直到栈为空，也就是遍历完毕

Waring：

这里的为什么不像构造二叉树那样利用this指针？因为这里的遍历不需要改变二叉树的结构、属性，如果

遇到线索化二叉树这种需要改变其本身的遍历就应该使用this指针了

二、中序遍历

中序遍历的顺序为：DBACEFG

算法：

（1）构造栈，头节点入栈，栈中元素为存放着未被访问的节点

（2）向左走到最底端，退栈，访问这个节点，然后向右走一步

（3）以右节点为新的头节点，继续（2），直到栈为空，表示遍历结束

Waring：

中序遍历和先序遍历都需要用到栈，但是栈中元素的性质却不一样，先序遍历中栈元素需要是已被访问的节点，

这是因为双亲节点应该被首先访问；而中序遍历中栈元素须是未被访问的节点，是因为双亲节点的访问应该后于

其左孩子。

（后序遍历在其后的销毁二叉树中总结）

三、层次遍历

层次遍历顺序：ABCDEFG

算法：

（1）我们需要的不是栈了，而是队列

（2）当访问一个节点的时候，我们要考虑其左右孩子，若有不为空的孩子就让它入队列，在其双亲节点后面排队

（3）采取从左到右、从上到下的层次，每让最前端的出队列被访问时，就应该让它的不为空的孩子指针入队列

（4）当队列为空的时候，就表示遍历完毕了

/********遍历的应用**********/

一、计算节点数目

通过层次遍历可以计算，每次出队列访问一个就++count，到层次遍历结束的时候，节点数目就自然出来了

二、求二叉树深度

如果用递归的方法很简单：先求其左子树深度，再求其右子树深度，深度大的为二叉树深度

（非递归的还没想出来，求大神指教）

三、销毁二叉树

二叉树的构造是通过内存申请完成的，销毁它是必须滴～～～

采用后序遍历来销毁二叉树要简单一些，因为销毁二叉树必须要从下到上销毁，不得破坏二叉树结构，否则将不能销毁；

而后序遍历正好是这种模型

算法：

（1）利用栈，向左走到最深处

（2）这时栈顶元素的左孩子肯定为NULL，so 考虑其右孩子是否也为NULL，如不为NULL，就向右走一步；如果是NULL，

说明找到的是叶子节点，pop一下，free它，当然应该free的是this指针，因为此时我们必须改变二叉树的结构。

（3）然后再次获取栈顶元素，我们需要改变栈顶元素的左右孩子指针，我们应该修改它的左孩子还是右孩子？我们不知道

刚才free的是哪一个孩子，但是有一个定律：后序遍历同样采用从左到右的顺序，如果它的左孩子不为NULL，就应该让它的

左孩子为NULL，如果已经是NULL了，就应该让它的右孩子为NULL

（4）循环中。。。。直到栈为空、头节点被释放，表明销毁成功

四、线索化二叉树

算法：

（1）一般采用中序线索化二叉树，一个节点的左孩子指针不为空时方可进行线索化

（2）中序遍历中，我们将访问节点的部分改为对节点进行线索化，若其左孩子指针不为NULL，就让它指向其前驱，若其

右孩子指针不为NULL，就让它指向其后继，这里同样要改变二叉树结构，所以也需用到this指针

（3）确定前驱后继：附设两个遍历指针，cur指针指向当前遍历的节点，pre指针指向刚刚访问过的节点，就是cur的前驱，在

中序遍历中，就有这种相互关系来找到一个节点的前驱后继，pre是cur的前驱，cur是pre的后继