数据结构----二叉树非递归实现
/*********构造二叉树*********/
输入一串以二叉树先序序列遍历的字符，空格表示空指针。
比如这串字符：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的后继