数据结构 课件 线索二叉树.ppt

第五章 树与二叉树 数据结构电子教案 第五章 树与二叉树 线索化二叉树 线索化二叉树 (Threaded Binary Tree) 又称为穿线树。 通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。 希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。 线索 (Thread) 这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。 改造树结点，将 pred 指针和 succ 指针压缩到 leftChild 和 rightChild 的空闲指针中，并增设两个标志 ltag 和 rtag，指明指针是指示子女还是前驱／后继。后者称为线索。 ltag (或rtag) = 0，表示相应指针指示左子女（或右子女结点）；当ltag (或rtag) = 1, 表示相应指针为前驱（或后继）线索。 线索化二叉树及其链表表示 线索化二叉树的类定义 template class T struct ThreadNode { //线索二叉树的结点类 int ltag, rtag; //线索标志 ThreadNodeT *leftChild, *rightChild; //线索或子女指针 T data; //结点数据 ThreadNode ( const T item) //构造函数 : data(item), leftChild (NULL), rightChild (NULL), ltag(0), rtag(0) {} }; template class T class ThreadTree { //线索化二叉树类 protected: ThreadNodeT *root; //树的根指针 void createInThread (ThreadNodeT *current, ThreadNodeT * pre); //中序遍历建立线索二叉树 ThreadNodeT *parent (ThreadNodeT *t); //寻找结点t的双亲结点 public: ThreadTree () : root (NULL) { } //构造函数 void createInThread(); //建立中序线索二叉树 ThreadNodeT *First (ThreadNodeT *current); //寻找中序下第一个结点 ThreadNodeT *Last (ThreadNodeT *current); //寻找中序下最后一个结点 ThreadNodeT *Next (ThreadNodeT *current); //寻找结点在中序下的后继结点 ThreadNodeT *Prior (ThreadNodeT *current); //寻找结点在中序下的前驱结点 ……… }; 寻找当前结点在中序下的前驱 if (current-ltag == 1) 前驱为current-leftChild else //current-ltag == 0 前驱为当前结点左子树 中序下的最后一个结点 在中序线索化二叉树中部分成员函数的实现 template class T ThreadNodeT * ThreadTree T :: First (ThreadNodeT * current) { //函数返回以*current为根的线索化二叉树中的中 //序序列下的第一个结点 ThreadNodeT * p = current; while (p-ltag == 0) p = p-leftChild; return p; }; 通过中序遍历建立中序线索化二叉树 template class T void ThreadTreeT::createInThread () { ThreadNodeT *pre = NULL; //前驱结点指针 if (root != NULL) { //非空二叉树, 线索化 cr