二叉树是非线性结构,但二叉树的遍历为二叉树的节点集导出了一个线性序列。若希望很快找到某一节点的前驱或后继,可以增加一个前驱指针域和一个后继指针域,但这样做显然浪费不少空间。如果利用原有的空指针域来存放前驱和后继指针,再加上两个标识指针指向左右子女还是前驱后继的字段,就构成了线索二叉树。下面以中序线索二叉树为例进行讨论。
成员函数
返回以current为根的中序线索二叉树中序序列下的第一个节点。
1 2 3 4 5 6 7 8
| 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在中序下的后继节点。
1 2 3 4 5 6 7 8 9
| 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为根的中序线索二叉树在中序序列下的最后一个节点。
1 2 3 4 5 6 7 8
| 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在中序下的前驱节点。
1 2 3 4 5 6 7 8 9
| 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; } };
|
利用中序线索遍历二叉树时可以不使用栈。
1 2 3 4 5 6 7
| 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); } };
|
再稍加改动,可以对一个已存在的二叉树按中序遍历进行线索化的算法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| 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); };
|
利用中序线索信息,实现前序遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| 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; } } } }
|
利用中序线索实现后序遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| 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); } };
|