DataStructure_ThreadTree

线索二叉树的实现

线索二叉树的声明

#include "iostream"
using namespace std;
//树的声明
typedef char ElemType;
typedef struct ThreadNode{
    ElemType data;                         //数据域
    struct ThreadNode *lchild,*rchild;     //左孩子指针与右孩子指针
    int ltag,rtag;
}ThreadNode,* ThreadTree;

中序遍历求线索二叉树的算法

// "中序遍历对二叉树线索化算法" <左根右>
// "其实这个过程就是中序遍历的过程的升级版本"
void InThread(ThreadTree &p,ThreadTree &pre){
    if (p!=NULL){
        InThread(p->lchild,pre);        	//递归，线索化左子树
        if (p->lchild!=NULL){               //左子树为空，建立前驱索引
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre->rchild!=NULL){             //右子树为空，建立后继索引
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre=p;                               //p交给pre p继续向下执行
        InThread(p->rchild,pre);    		 //递归，线索化右子树
    }
}

注意:
	在进行线索二叉树的原理是:
		1、节点的左右孩子为空那么分别指向他中序遍历的前驱和后继
		2、在进行遍历的时候pre是p的前驱，如果p节点的左孩子为空那么p->lchild = pre。
		3、在进行遍历的时候pre节点的左孩子肯定已经被p处理掉了，那么只需要处理pre的右孩子，假设为空
		就指向它的后继，pre的后继就是p即:pre->rchild = p
		

中序遍历建立中序线索二叉树

//通过中序遍历建立中序线索二叉树
void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if (T!=NULL){
        InThread(T,pre);           		    //非空二叉树，线索化
        pre->rchild=NULL;                   //处理最后一个节点 最后一个节点肯定没有右孩子
        pre->rtag = 1;
    }
}

注意:
	1、本次采用的是中序遍历的方法。前序遍历和后序遍历都是在方法中进行我们所谓的"增强"。这里就不进行展开
	2、这里的处理最后一个节点的的方式直接拿了出来，是因为我们的pre最后都会指向p那么在进行中序遍历的时候
	肯定没有右孩子，换句话说就是哪怕右孩子非空那么最后一个访问的节点肯定最后一个节点
	3、举例
		1、若我们需要赋值的树为
			A
		B		 C
      D  E     F   G
    # #	 # #  # # #  H
    				# #
    此时我们的中序遍历是: DBEAFCHGH 这里是中序遍历的特征我们就不进行展开