数据结构 课件 线索二叉树

《数据结构 课件 线索二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章树与二叉树数据结构电子教案1第五章树与二叉树线索化二叉树2线索化二叉树(ThreadedBinaryTree)又称为穿线树。通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。3线索(Thread)增加前驱Pred指针和后继Succ指针的二叉树predleftChilddatarightChildsuccabcdepredp

2、redpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc4这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。改造树结点，将pred指针和succ指针压缩到leftChild和rightChild的空闲指针中，并增设两个标志ltag和rtag，指明指针是指示子女还是前驱／后继。后者称为线索。ltag(或rtag)=0，表示相应指针指示左子女（或右子女结点）；当ltag(或rtag)=1,表示相应指针为前驱（或后继）线索。leftChildlt

3、agdatartagrightChild5leftChildltagdatartagrightChildabcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111线索化二叉树及其链表表示6线索化二叉树的类定义templatestructThreadNode{//线索二叉树的结点类intltag,rtag;//线索标志ThreadNode*leftChild,*rightChild;//线索或子女指针Tdata;//结点数据ThreadNod

4、e(constTitem)//构造函数:data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0){}};7templateclassThreadTree{//线索化二叉树类protected:ThreadNode*root;//树的根指针voidcreateInThread(ThreadNode*current,ThreadNode*&pre);//中序遍历建立线索二叉树ThreadNode*parent(ThreadNode*

5、t);//寻找结点t的双亲结点public:ThreadTree():root(NULL){}//构造函数8voidcreateInThread();//建立中序线索二叉树ThreadNode*First(ThreadNode*current);//寻找中序下第一个结点ThreadNode*Last(ThreadNode*current);//寻找中序下最后一个结点ThreadNode*Next(ThreadNode*current);//寻找结点在中序下的后继结点ThreadNode*Pri

6、or(ThreadNode*current);//寻找结点在中序下的前驱结点………};9if(current->rtag==1)后继为current->rightChildelse//current->rtag==0后继为当前结点右子树的中序下的第一个结点寻找当前结点在中序下的后继ABDECFHIKGJ10寻找当前结点在中序下的前驱if(current->ltag==1)前驱为current->leftChildelse//current->ltag==0前驱为当前结点左子树中序下的最后一个结点ABDECFHIKGJL11在中

7、序线索化二叉树中部分成员函数的实现templateThreadNode*ThreadTree::First(ThreadNode*current){//函数返回以*current为根的线索化二叉树中的中//序序列下的第一个结点ThreadNode*p=current;while(p->ltag==0)p=p->leftChild;returnp;};12template//另一个版本见面课本198ThreadNode*ThreadTree::Next(ThreadN

8、ode*current){//函数返回在线索化二叉树中结点*current在中序//下的后继结点ThreadNode*p=current->rightChild;if(current->rtag==0)ret