《数据结构与算法设计PPT (25).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (25).pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 树6.5 线索二叉树线索二叉树二叉树有很多浪费的空间：-叶子节点每个都有2个空指针可以使用空指针来帮助提高遍历效率在空指针中存储遍历要使用的后继结点的指针-称为线索指针是指向孩子的指针还是线索，需要增加一个布尔值用以区分Data StructureSoftware College Northeastern University线索树的数据结构leftChildPreddata SuccrightChildPred=0 /lchild points to its left child1 /lchild points to its predecessorSucc=0 /rchild poi
2、nts to its right child1 /rchild points to its successortypedef enum PointerTagLink,Thread;/Link：指向孩子的指针/Thread:指向遍历顺序中的前驱或者后继typedef struct BiThrNodeType data;struct BiThrNode*leftChild,*rightChild;PointerTag Pred,Succ;BiThrNode,*BiThrTree；0A00B00C11D11E11F1NIL先根序线索树ABDEFCACNILTTTBDFE0A00B00C11D11E1
3、1F1NILNILABDEFCACENILNILTTTBDF中根序线索树0A00B00C11D11E11F1NILABDEFCACENILNILTTTBDF后根序线索树0A00B00C11D11E11F1thrt10标头：指向前后节点的指针Pred：0 leftChild：指向根的指针Succ：1 rightChild 指向尾结点的指针在第一个被访问的结点：Pred：1 leftChild：指向表头结点尾节点：Succ：1 rightChild：指向表头结点带头结点的线索树利用线索树做中根序遍历中根序的遍历从树的最左边最下面的结点开始，访问之后通过rightChild进入到右子树 再进入到最左
4、最下面的结点开始遍历如果右孩子不存在，顺着rightChild找到后继结点利用线索树进行中根序遍历87531113169从最左最下面的1开始访问Output187531113169沿着1的rightChild后继指针访问3Output13利用线索树进行中根序遍历87531113169进入到3的右子树，到右子树的最左面结点开始Output135利用线索树进行中根序遍历87531113169沿着5的rightChild的后继指针访问6Output1356利用线索树进行中根序遍历87531113169进入到右子树的最左下的7Output13567利用线索树进行中根序遍历87531113169沿着7的
5、后继指针访问8Output135678利用线索树进行中根序遍历87531113169进入到8的右子树的最左下的9Output1356789利用线索树进行中根序遍历87531113169沿着9的后继指针访问11Output135678911利用线索树进行中根序遍历87531113169访问11的右孩子Output13567891113利用线索树进行中根序遍历在二叉树中添加线索先根线索中根线索后根线索7 710101 12 23 34 45 56 69 98 8中序线索化二叉树的类定义template class ThreadNodefriend classThreadTree;private:i
6、ntleftThread,rightThread;ThreadNode*leftChild,*rightChild;Typedata;public:ThreadNode(const Typeitem):data(item),leftChild(NULL),rightChild(NULL),leftThread(0),rightThread(0);template class ThreadTreefriend classThreadInorderIterator;public:voidInorder();voidCreateThread();private:ThreadNode*root;中序线
7、索化二叉树的类定义if(currentrightThread=1)if(currentrightChild!=T.root)后继为currentrightChildelse 无后继else/currentrightThread!=1 if(currentrightChild!=T.root)后继为当前结点右子树的中序下的第一个结点else出错情况寻找当前结点在中序下的后继ABDECGJif(currentleftThread=1)if(currentleftChild!=T.root)前驱为currentleftChildelse无前驱else/currentleftThread=0if(cu
8、rrentleftChild!=T.root)前驱为当前结点左子树的中序下的最后一个结点else出错情况寻找当前结点在中序下的前驱ABDECGJtemplate void ThreadTree:Inorder()/线索化二叉树的中序遍历ThreadNode*current=root;while(currentleftThread=0)current=currentleftChild;while(current!=T.root)cout pdata endl;if(currentrightThread=0)while(currentleftThread=0)current=currentleft
9、Child;elsecurrent=currentrightChild;线索化二叉树遍历的实现template voidThreadTree:InThread(ThreadNode*current,ThreadNode*pre)if(current!=NULL)InThread(currentleftChild,pre);if(currentleftChild=NULL)currentleftChild=pre;currentleftThread=1;通过中序遍历建立中序线索化二叉树if(prerightChild=NULL)prerightChild=current;prerightThre
10、ad=1;pre=current;InThread(currentrightChild,pre);template voidThreadTree:CreateInThread()ThreadNode*pre;root=new ThreadNode;rootleftThread=1;rootrightThread=0;if(this=NULL)rootleftChild=root;rootrightChild=root;else current=rootleftChild=this;rootleftThread=0;pre=root;InThread(current,pre);prerightChild=root;prerightThread=1;