二叉樹的前序、中序、后序線索化及遍歷

前序線索化:

創(chuàng)新互聯(lián)企業(yè)建站,十余年網(wǎng)站建設(shè)經(jīng)驗(yàn)，專注于網(wǎng)站建設(shè)技術(shù)，精于網(wǎng)頁(yè)設(shè)計(jì)，有多年建站和網(wǎng)站代運(yùn)營(yíng)經(jīng)驗(yàn)，設(shè)計(jì)師為客戶打造網(wǎng)絡(luò)企業(yè)風(fēng)格，提供周到的建站售前咨詢和貼心的售后服務(wù)。對(duì)于網(wǎng)站設(shè)計(jì)、做網(wǎng)站中不同領(lǐng)域進(jìn)行深入了解和探索，創(chuàng)新互聯(lián)在網(wǎng)站建設(shè)中充分了解客戶行業(yè)的需求，以靈動(dòng)的思維在網(wǎng)頁(yè)中充分展現(xiàn)，通過對(duì)客戶行業(yè)精準(zhǔn)市場(chǎng)調(diào)研，為客戶提供的解決方案。

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;
    _PrevOrderThreading(cur->_left, prev);
    _PrevOrderThreading(cur->right, prev);
    
}

前序遍歷：

void PrevOrderThd()
{
    Node *cur = _root;
    while(cur)
    {
        while(cur->_leftTag == LINK)
        {
            cout << cur->_data << " ";
            cur = cur->_left;
        }
        cout << cur->_data << " ";
        
        
        cur = cur->right;
              
//      
//      while(cur->_rightTag == THREAD)
//      {
//          cur = cur->_right;
//          cout << cur->_data << " ";
//      }
//      if(cur->_leftTag == LINK)
//      {
//          cur = cur->_left;
//      }
//      else
//      {
//          cur = cur->_right;
//      }

    }
}

中序線索化：

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 InOrderThd()
{
    Node *cur = _root;
    while(cur)
    {
        //找最左節(jié)點(diǎn)
        while(cur->_leftTag == LINK)
        {
            cur = cur->_left;
        }
        cout << cur->_data << " ";
        //訪問連續(xù)后繼
        while(cur->_rightTag == THREAD)
        {
            cur = cur->_right;
            cout << cur->_data << " ";
        }
        cur = cur->_right;
    }
}

后序線索化：

	void _PostOrderThreading(Node *root, Node *&prev)
	{
		if (root == NULL)
		{
			return;
		}
		_PostOrderThreading(root->_LChild, prev);
		_PostOrderThreading(root->_RChild, prev);
		if (root->_LChild == NULL)
		{
			root->_LTag = THREAD;
			root->_LChild = prev;
		}
		if (prev->_RChild == NULL)
		{
			prev->_RTag = THREAD;
			prev->_RChild = root;
		}
		prev = root;
	}

后序遍歷：

采用三叉鏈
或?qū)懸粋€(gè)查找根節(jié)點(diǎn)的方法

分享題目：二叉樹的前序、中序、后序線索化及遍歷
新聞來源：http://bm7419.com/article30/gijsso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、搜索引擎優(yōu)化、虛擬主機(jī)、云服務(wù)器、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

搜索引擎優(yōu)化