二叉树的线索化,这几天以来我很难掌握,今天终于想通了,哈哈,首先我们来看看二叉树线索化之后会变成什么样子,这里我们以图中的二叉树为例,图如下:
画的太糙,各位看官讲究着看吧- -。所谓二叉树的线索化,就是当一个节点的左右指针为空时,就让它的左右指针指向该节点的前驱或者后继(一般来说左指针指向前驱,右指针指向后继)。这里不论指向前驱或者后继,我们都应该线索化时,至少要明确两个节点指针的值,当前节点和当前节点的前驱/后继。这也是线索化的两种思路:
保存前驱:访问当前节点时若当前节点的左指针为空,则令左指针指向前驱,若前驱的右指针为空,则令前驱的右指针指向当前节点,代码描述如下:
void visit(NODE* cur,NODE* &prev)//当前指针的前驱在当前指针访问时会改变,故传引用用来改变//prev { if(prev->right==NULL; prev->right=cur; if(cur->left==NULL) cur->left=prev; prev=cur; }
这里我们要注意的是应该先进行访问,最后再改变prev的值。
保存后继:这种方法很难做到,并且个人觉得没有什么意义,因为在遍历整个数的过程中我们始终都会访问到一个节点的后继,若将要访问后继那我们如何保存到未来的东西,即使通过类似栈的数据结构通过压栈来强行访问,效率也是不高的,在此不推荐。
接下来献上c++完整的线索二叉树结构以及中序线索化过程,通过递归与非递归两种方式实现,其他的都大同小异。
节点类定义如下:
typedef char Datatype; enum NodeType { LINK, THERAD }; struct TheardBinaryTreeNode { TheardBinaryTreeNode* _left; TheardBinaryTreeNode* _right; NodeType _leftTag; NodeType _rightTag; Datatype _data; TheardBinaryTreeNode(const Datatype & data) :_left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) ,_data(data) {} TheardBinaryTreeNode() : _left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) ,_data((Datatype)0) {} };
中序线索化如下:
void InTherad() { NODE* prev = NULL; _InTherad(_root, prev); //stack<NODE*>s;//借助栈来实现非递归的中序线索化 //NODE* cur = _root; //NODE* prev = NULL; //while (!s.empty()||cur) //{ // while (cur) // { // s.push(cur); // cur = cur->_left; // } // NODE* top = s.top(); // s.pop(); // if (top->_left == NULL&&top->_leftTag == LINK) // { // top->_left = prev; // top->_leftTag = THERAD; // } // prev = top; // if (top->_right == NULL&&top->_rightTag==LINK) // { // top->_rightTag = THERAD; // if (!s.empty()) // top->_right = s.top(); // } // else // cur = top->_right; //} } void _InTherad(NODE*root, NODE* &prev)//递归的中序线索化 { if (root == NULL) return; _InTherad(root->_left, prev); if (prev&&prev->_rightTag == LINK&&prev->_right == NULL) { prev->_right = root; prev->_rightTag = THERAD; } if (root->_leftTag == LINK&&root->_left == NULL) { root->_leftTag = THERAD; root->_left = prev; prev = root; } _InTherad(root->_right,prev); }
如有不足或者疑问希望留言提出。3Q -3-。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。