您好,登錄后才能下訂單哦!
二叉樹的線索化,這幾天以來我很難掌握,今天終于想通了,哈哈,首先我們來看看二叉樹線索化之后會(huì)變成什么樣子,這里我們以圖中的二叉樹為例,圖如下:
畫的太糙,各位看官講究著看吧- -。所謂二叉樹的線索化,就是當(dāng)一個(gè)節(jié)點(diǎn)的左右指針為空時(shí),就讓它的左右指針指向該節(jié)點(diǎn)的前驅(qū)或者后繼(一般來說左指針指向前驅(qū),右指針指向后繼)。這里不論指向前驅(qū)或者后繼,我們都應(yīng)該線索化時(shí),至少要明確兩個(gè)節(jié)點(diǎn)指針的值,當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的前驅(qū)/后繼。這也是線索化的兩種思路:
保存前驅(qū):訪問當(dāng)前節(jié)點(diǎn)時(shí)若當(dāng)前節(jié)點(diǎn)的左指針為空,則令左指針指向前驅(qū),若前驅(qū)的右指針為空,則令前驅(qū)的右指針指向當(dāng)前節(jié)點(diǎn),代碼描述如下:
void visit(NODE* cur,NODE* &prev)//當(dāng)前指針的前驅(qū)在當(dāng)前指針訪問時(shí)會(huì)改變,故傳引用用來改變//prev { if(prev->right==NULL; prev->right=cur; if(cur->left==NULL) cur->left=prev; prev=cur; }
這里我們要注意的是應(yīng)該先進(jìn)行訪問,最后再改變prev的值。
保存后繼:這種方法很難做到,并且個(gè)人覺得沒有什么意義,因?yàn)樵诒闅v整個(gè)數(shù)的過程中我們始終都會(huì)訪問到一個(gè)節(jié)點(diǎn)的后繼,若將要訪問后繼那我們?nèi)绾伪4娴轿磥淼臇|西,即使通過類似棧的數(shù)據(jù)結(jié)構(gòu)通過壓棧來強(qiáng)行訪問,效率也是不高的,在此不推薦。
接下來獻(xiàn)上c++完整的線索二叉樹結(jié)構(gòu)以及中序線索化過程,通過遞歸與非遞歸兩種方式實(shí)現(xiàn),其他的都大同小異。
節(jié)點(diǎn)類定義如下:
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;//借助棧來實(shí)現(xiàn)非遞歸的中序線索化 //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-。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。