- #include <iostream>
- #include "tree.h"
- using namespace std;
- BTNode *pre;
- void Thread(BTNode *&p) //当tag为1 的时候，表示指向的是前驱 或者 后继， 当其值为0的时候，表示指向的是左右子孩子
- {
- if(p != NULL) //采用中序遍历
- {
- Thread(p->lchild); // 此处开始遍历左子树
- if(p->lchild == NULL) //最节点的左子节点进行操作， 如果其值为空的话，就把其指向 前驱节点，并且设置tag值
- {
- p->lchild = pre;
- p->ltag = 1;
- }else
- p->ltag = 0;
- if(pre->rchild == NULL) //此处对 前驱节点 的右节点进行操作，如果其右节点为空的话，就把它指向其后继节点，也就是p节点
- {
- pre->rchild = p;
- pre->rtag = 1;
- }else
- pre->rtag = 0;
- pre = p; //对pre进行赋值
- Thread(p->rchild);
- }
- }
- BTNode * CreateThread(BTNode *b) //此函数是创建线索化二叉树
- {
- BTNode *root = (BTNode *)malloc(sizeof(BTNode)); //此为头结点
- if(b != NULL)
- {
- root->lchild = b; //把头结点的左子树指向 根节点
- pre = root; //pre 的含义为前驱， 初始值为root
- Thread(b); //进行线索化
- pre->rchild = root; //经过线索化后，pre为最后一个节点， 把最后一个节点的右子树指向root
- pre->rtag = 1;
- root->rchild = pre; //修改root头结点的右指向
- root->rtag = 1;
- }else
- {
- root->lchild = root; //如果b为空的话，那么头结点的左子树，直接指向其自身
- }
- return root;
- }
- BTNode *first(BTNode *root) //此函数是返回root为根的中序线索树 的第一个节点
- {
- if(root != NULL)
- {
- while(root->ltag == 0) //规定当tag==0 的时候表明其有左 或者 右子树， 所以此处循环直到其没有左子树的时候，就是求得
- root = root->lchild; //其值的时候， 也就是其有前驱的时候
- return root;
- }
- return NULL;
- }
- BTNode *next(BTNode *root, BTNode *q) //此函数是返回q节点的后继节点
- {
- BTNode *p = q->rchild; //此处把p指向q的右子节点， 但是q的右子节点不一定是右孩子节点， 还有可能是其后继节点， 当是其后继节点的时候，就达到了访问其祖先节点的目的
- if(q->rtag == 0) //当q有右孩子的时候
- while(p->ltag == 0) //怎么求后继节点也是遍历左子树？？？
- p = p->lchild; //p = p->rchild;
- if(p == root)
- return NULL;
- else return p;
- }
- void forward(BTNode *root) //正向遍历线索树
- {
- BTNode *p;
- for(p = first(root); p != NULL; p = next(root,p))
- cout<<p->data<<' ';
- cout<<endl;
- }
- BTNode *last(BTNode *root) //此函数是返回以root为根的中序线索树中的最后节点
- { //最后一个节点就是 头结点的右子树
- if(root != NULL)
- return root->rchild;
- return NULL;
- }
- BTNode *last2(BTNode *root) //此函数同样实现上述功能但是， 是通过向右遍历实现的
- {
- if(root != NULL)
- { root = root->lchild;
- while(root->rtag == 0)
- root = root->rchild;
- return root;
- }
- return NULL;
- }
- BTNode *prior(BTNode *root, BTNode *q) //此函数是求的q节点的前驱节点
- {
- BTNode *p = q->lchild; //把p指向q的左节点，且左节点 可能是左孩子节点 也可能是 前驱
- if(q->ltag == 0) //此处判断 q其是否有左孩子节点
- while(p->rtag == 0)
- p = p->rchild; //奇怪这里是对右子树进行判断的， 而求后继的时候是对左子树进行判断的， 想想也是因为他们是连续的
- if(p == root)
- return NULL;
- else return p;
- }
- void backward(BTNode *root)
- {
- BTNode *p;
- for(p = last(root); p != root; p = prior(root,p))
- cout<<p->data<<' ';
- cout<<endl;
- }