C++实现线索化二叉树
当以二叉树作为存储结构时,只能找到节点的左右孩子信息,不能直接得到结点在任一序列中的前驱和后继信息,只有在遍历过程中才能得到这种信息。我们知道,在n个结点的二叉链表栈必定存在n+1个空链域,因此,可以利用这些空链域来存放这些结点信息。所以作如下规定:若结点右左子树,则其lchild域指向其左孩子,否则令lchild域指向其前驱;若结点有右子树,其rchild域指向其右孩子,否则指向其后继。以这种结构构成的二叉链表叫做线索链表。
威远ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:13518219792(备注:SSL证书合作)期待与您的合作!
前序线索化:
源代码:
#define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; enum PointerTag { THREAD, LINK, }; template struct BinaryTreeNodeThd { T _data; BinaryTreeNodeThd *_left; BinaryTreeNodeThd *_right; PointerTag _leftTag; PointerTag _rightTag; BinaryTreeNodeThd(const T&data)//线索化 :利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息 :_data(data) , _left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) {} }; template class BinaryTreeThd { typedef BinaryTreeNodeThd Node; private: Node* _root; public: BinaryTreeThd() :_root(NULL) {} BinaryTreeThd(const T* a, size_t size,size_t index,const T& invalid) { _root = _CreateBinaryTreeThd(a, size, index, invalid); } //中序线索化 void InorderThreading() { Node* prev=NULL; _InorderThreading(_root,prev); } //先序线索化 void PrevtorderThreading() { Node* prev=NULL; _PrevorderThreading(_root,prev); } //中序线索化遍历 void _InorderThd() { Node* cur=_root; while(cur) { // 访问最左边的叶子节点 while(cur->_leftTag ==LINK) { cur=cur->_left ; } cout< _data <<" "; while(cur->_rightTag ==THREAD) { cur=cur->_right ; cout< _data <<" "; } //访问右子树 cur=cur->_right ; } } //先序线索化遍历二叉树 void _Prevorderthd( ) { Node*cur=_root; if(cur==NULL) { return; } while(cur) { //输出左边的节点 while(cur->_leftTag ==LINK) { cout< _data <<" "; cur=cur->_left ; } cout< _data <<" "; //转移到右边的节点 cur=cur->_right; /*while(cur->_rightTag ==THREAD ) { cur=cur->_right ; cout< _data<<" " ; }*/ } } protected: // Node* _CreateBinaryTreeThd(const T*a, size_t size, size_t& index, const T& invalid) { Node* root=NULL; if(index _left = _CreateBinaryTreeThd(a,size,++index,invalid); root->_right =_CreateBinaryTreeThd(a,size,++index,invalid); } return root; } //中序线索化子树 void _InorderThreading(Node* cur,Node*& prev) { if(cur==NULL) { return; } //递归遍历左子树 _InorderThreading(cur->_left ,prev); if(cur->_left ==NULL) { cur->_leftTag =THREAD; cur->_left =prev; } if(prev&&prev->_right ==NULL) { prev->_rightTag =THREAD ; prev->_right =cur; } prev=cur; //递归遍历右子树 _InorderThreading(cur->_right ,prev); } //先序线索化子树 void _PrevorderThreading(Node* cur,Node*& prev) { if(cur==NULL) return; //置前线索化 if(cur->_left ==NULL) { cur->_leftTag =THREAD ; cur->_left =prev; } //置后线索化 if(prev&&prev->_right ==NULL) { prev->_rightTag =THREAD; prev->_right =cur; } prev=cur; if(cur->_leftTag ==LINK) { _PrevorderThreading(cur->_left ,prev); } if(cur->_rightTag ==LINK) { _PrevorderThreading(cur->_right ,prev); } } };
测试代码:
void test() { int a1[10]={1,2,3,'#','#',4,'#','#',5,6}; int a2[15]={1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8}; BinaryTreeThdbtt1(a1,10,0,'#'); BinaryTreeThd btt2(a2,15,0,'#'); cout<<"中序线索化遍历二叉树:"; btt1.InorderThreading (); btt1._InorderThd(); cout<
文章题目:C++实现线索化二叉树
本文来源:http://pwwzsj.com/article/pdheoo.html