DataStructure_ThreadTreeFind

线索二叉树的索引

中序二叉树的遍历

找到指定节点p的中序后继

1、p->rtag == 1 说明已经被线索化 
	1、next = p->rchild
2、p->rtag == 0 肯定存在右孩子
	p
  l   r
  	1、中序遍历 左 根 右
  		1.1、右孩子叶子节点 ---右节点为p的后继 next = r
  		1.2、右节点还有非空的节点 ---首先遍历的就是它的左孩子 next = p的右子树中最左下的节点
  		
//代码实现
ThreadNode *FirstNode(ThreadNode *p){
	//循环找到最左下的节点(不一定是叶子节点)
	//从指定的节点出发
	while(p->ltag==0) p=p->lchild;
	return p;
}

//在中序线索二叉树中找到节点p的后继节点
ThreadNode  *NextNode(ThreadNode *p){
    //右子树最左下的孩子
    if (p->rtag==0) return FirstNode(p->rchild);
    else return p->rchild;
}

//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
//T是根节点指针
void Inorder(ThreadNode *T){
    for (ThreadNode *p = FirstNode(T);p!=NULL;p=NextNode(p)){
        visit(p);
    }
}

找到指定节点p的中序前驱

1、p->ltag == 1 说明已经被线索化 
	1、pre = p->lchild
2、p->ltag == 0 肯定存在左孩子
	p
  l   r
  	1、中序遍历 左 根 右
  		1.1、左孩子叶子节点 ---左节点为p的前驱 pre = l
  		1.2、左孩子还有非空的节点 --- 根据中序遍历的过程最后遍历的就是p的前驱
  		即: pre = p的左子树中最后遍历的即是最右下的节点

//代码实现
ThreadNode *LastNode(ThreadNode *p){
    //循环找到最右下的节点(不一定是叶子节点)
    while(p->lchild == 0) p=p->rchild;
    return p;
}

//在中序线索二叉树中找到节点p的前驱接电脑
ThreadNode *PreNode(ThreadNode *p){
    if (p->ltag==0) return LastNode(p->lchild);
    else return p->lchild;
}

//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
    for (ThreadNode *p=LastNode(T);p!=NULL;p=PreNode(p))
        visit(p);
}

先序二叉树的遍历

找到指定节点p的先序后继

1、p->rtag == 1 说明已经被线索化 
	1、next = p->rchild
2、p->rtag == 0 肯定存在右孩子
	p
  l   r
  	1、先序遍历 根 左 右
  		1.1、假设p有左孩子和右孩子(左孩子为叶子节点) next = l
  		1.2、假设p没有左孩子，那必然有右孩子(根 右) next = 右子树第一个访问的节点(右孩子)
  		
//代码实现
ThreadNode *LFirstNode(ThreadNode *p){
    //循环找到最左下的节点(不一定是叶子节点)
    //从指定的节点出发
    if(p->ltag==0) return p = p->lchild;
    else{
        if (p->lchild == NULL && p->rtag == 1)
            p = p->rchild;
    }
    return p;
}

找到指定节点p的先序前驱

1、p->ltag == 1 说明已经被线索化 
	1、pre = p->lchild
2、p->ltag == 0 肯定存在左孩子
		p
 	  l   r
    1、先序遍历 根 左 右 (很明显所有的节点都只可能是p的后继而不可能是前驱)
    2、找不到先序前驱(除非头开始遍历)
    3、引入三叉链表
3、引入三叉链表
    3.1、 先序遍历 根 左 右
    3.2、如果能找到p的父节点且p是左孩子 即：p的父节点为其前驱
    3.3、如果能找到p的父节点且p是右孩子，其左兄弟为null 即：p的父节点为其前驱
    3.4、如果能找到p的父节点，且p是右孩子，其左兄弟非空 即：p的前驱是左兄弟子树中最后一个被前序遍历的节点。其实根据先序遍历找最后一个访问的元素就是优先访问子树的右子树，如果为null再左子树。简单来说就是"[有右先右,再左]"
    3.5、如果p是根节点，则p没有先序前驱    

后序二叉树的遍历

找到指定节点p的后序前驱

1、p->ltag == 1 说明已经被线索化 
	1、pre = p->lchild
2、p->ltag == 0 肯定存在左孩子
    	p
  	  l   r
    1、后序遍历 左 右 根
    2、假设有右孩子，那么后序前驱为右子树后序遍历的最后一个孩子即为右孩子 pre = r
    3、没有右孩子，那么后序前驱为左子树后序遍历的最后一个孩子即为左孩子 pre = l
    
//代码实现
ThreadNode *LastNodeLast(ThreadNode *p){
    //如果p有右孩子 根据左右根(p)
    if (p->rtag == 0) return p=p->rchild;
    //如果没有右孩子
    else if (p->rchild == NULL && p->ltag == 0) return p=p->lchild;
}

找到指定节点p的后序后继

1、p->rtag == 1 说明已经被线索化 
	1、next = p->rchild
2、p->rtag == 0 肯定存在右孩子
    	p
  	  l   r
    1、后序遍历 左 右 根
    2、所有的节点只有可能是它的前驱不肯是他的后继
    3、找不到后序后继(除非头开始遍历)
3、引入三叉链表
    根据：后序遍历 左 右 根
    3.1、如果能找到p的父节点，且p是右孩子 即p的后序后继为其父节点
    3.2、如果能找到p的父节点，且p是左孩子且右兄弟为NULL 即p的后序后继为其父节点
    3.3、如果p是左孩子，且右兄弟非空 即p的后序后继为右兄弟子树中第一个被后序遍历的节点，其实后序遍历的第一个被后序遍历的节点即要[首先左子树优先，再右子树]
    3.4、如果p是根节点，则p没有后序后继