线索二叉树

二叉树是非线性结构，但二叉树的遍历为二叉树的节点集导出了一个线性序列。若希望很快找到某一节点的前驱或后继，可以增加一个前驱指针域和一个后继指针域，但这样做显然浪费不少空间。如果利用原有的空指针域来存放前驱和后继指针，再加上两个标识指针指向左右子女还是前驱后继的字段，就构成了线索二叉树。下面以中序线索二叉树为例进行讨论。

#成员函数

返回以current为根的中序线索二叉树中序序列下的第一个节点。

template <class T>
ThreadNode<T> *ThreadTree<T>::First(ThreadNode<T> *current) {
	ThreadNode<T> *p = current;
	while (p->ltag == 0) {
		p = p->leftChild;
	}
	return p;
};

返回current在中序下的后继节点。

template <class T>
ThreadNode<T> *ThreadTree<T>::Next(ThreadNode<T> *current) {
	ThreadNode<T> *p = current->rightChild;
	if (current->rtag == 0) {
		return First(p);
	} else {
		return p;
	}
};

返回以current为根的中序线索二叉树在中序序列下的最后一个节点。

template <class T>
ThreadNode<T> *ThreadTree<T>::Last(ThreadNode<T> *current) {
	ThreadNode<T> *p = current;
	while (p->rtag == 0) {
		p = p->rightChild;
	}
	return p;
};

返回current在中序下的前驱节点。

template <class T>
ThreadNode<T> *ThreadTree<T>::Prior(ThreadNode<T> *current) {
	ThreadNode<T> *p = current->leftChild;
	if (current->ltag == 0) {
		return Last(p);
	} else {
		return p;
	}
};

利用中序线索遍历二叉树时可以不使用栈。

template <class T>
void ThreadTree<T>::InOrder(void (*visit)(ThreadNode<T> *p) {
	ThreadNode<T> *p;
	for (p = First(root); p != NULL; p = Next(p)) {
		visit(p);
	}
};

再稍加改动，可以对一个已存在的二叉树按中序遍历进行线索化的算法。

template <class T>
void ThreadTree<T>::createInThread(){
    ThreadNode<T> *pre = NULL;
    if (root != NULL) {
        createInThread(root, pre);
        pre->rightChild = NULL;
        pre->rtag = 1;
    }
};

template <class T>
void ThreadTree<T>::createInThread(ThreadNode<T> *current, TheadNode<T> *& pre) {
    if (current == NULL) {
        return;
    }
    createInThread(current->leftChild, pre);
    if(current->leftChild == NULL) {
        current->leftChild = pre;
        current->ltag = 1;
    }
    if (pre != NULL && pre->rightChild == NULL) {
        pre->rightChild = current;
        pre->rtag = 1;
    }
    pre = current;
    createInThread(current->rightChild, pre);
};

利用中序线索信息，实现前序遍历。

template <class T>
void ThreadTree<T>::PreOrder(void (*visit)(ThreadNode<T> *p)) {
    ThreadNode<T> *p = root;
    while (p != NULL) {
        visit(p);
        if (p->ltag == 0) {
            p = p->leftChild;
        } else if (p->rtag == 0) {
            p = p->rightChild;
        } else {
            while (p != NULL && p->rtag == 1) {
                p = p->rightChild;
            }
            if (p != NULL) {
                p = p->rightChild;
            }
        }
    }
}

利用中序线索实现后序遍历。

template <class T>
void ThreadTree<T>::PostOrder(void(* visit)(ThreadNode<T> *p)) {
    ThreadNode<T> *t = root;
    while (t->ltag == 0 || t->rtag == 0) {
        if (t->ltag == 0) {
            t = t->leftChild;
        } else if (t->rtag == 0) {
            t = t->rightChild;
        }
    }
    visit(t);
    ThreadNode<T> *p;
    while ((p = parent(t)) != NULL) {
        if (p->rightChild == t || p->rtag == 1) {
            t = p;
        } else {
            t = p->rightChild;
            while (t->ltag == 0 || t->rtag == 0) {
                if (t->ltag == 0) {
                    t = t->leftChild;
                } else if (t->rtag == 0) {
                    t = t->rightChild;
                }
            }
        }
        visit(t);
    }
};