前序线索化:

成都创新互联主要从事网页设计、PC网站建设（电脑版网站建设）、wap网站建设（手机版网站建设）、成都响应式网站建设公司、程序开发、网站优化、微网站、小程序开发等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了丰富的网站建设、成都做网站、网站设计、网络营销经验，集策划、开发、设计、营销、管理等多方位专业化运作于一体。

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)
    {
        //找最左节点
        while(cur->_leftTag == LINK)
        {
            cur = cur->_left;
        }
        cout << cur->_data << " ";
        //访问连续后继
        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;
	}

后序遍历：

采用三叉链
或写一个查找根节点的方法

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

文章标题：二叉树的前序、中序、后序线索化及遍历-创新互联
文章转载：http://lswzjz.com/article/djpiid.html