中序遍历线索化二叉树思路分析

void InOrderCuleTree(node* root)
{
    if(root == null)
    {
        cout<<结点为空<<endl ;
        return;
    }
    node* tmpnode = root;
    
    while(tmpnode不为空)
    {
//先找到左边的第一个线索化节点，并进行打印
         while(tmpnode.lefttag!=1)
        {
            tmpnode = tmpnode.rightchild
        }
//打印结点数据
        cout<<"此时输出的是第一个结点"<<endl ;

如果该节点右子节点也是线索化节点，则打印它
//一直是就一直打印
        while(tmpnode.righttag == 1)
        {
            cout<<tmpnode.rightchild.data;
            tmpnode = tmpnode.rightchild;
        }
        tmpnode = tmpnode.rightchild;//走到这步是因为下一个结点并不是后继结点，因此要继续寻找上一个结点的后续结点。
    }
   
    
    
}

代码实现

#include<iostream>
#include<string.h>

using namespace std;

typedef int datatype;
struct BitNode
{
	datatype Data;
	struct BitNode* leftChild;
	struct BitNode* rightChild;
	int lefttag;
	int righttag;
};
#pragma region 中序递归线索化
BitNode* previous = NULL;
void PreOrderIterative(BitNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BitNode* tmpnode = NULL;
	tmpnode = root;
	PreOrderIterative(tmpnode->leftChild);
	if (tmpnode->leftChild == NULL)
	{
		tmpnode->leftChild = previous;//左孩子指向前驱
		tmpnode->lefttag = 1;
	}
	/*如果想指向后继，必须返回到前一层结点 才能让当前层的*/
	if (previous != NULL && previous->rightChild == NULL)
	{
		previous->rightChild = tmpnode;
		previous->righttag = 1;
	}
	previous = tmpnode;
	PreOrderIterative(tmpnode->rightChild);
}
#pragma endregion
#pragma region 中序遍历线索化二叉树
void PreOrderCuleTree(BitNode* root)
{
	if (root == NULL)
	{
		cout << "结点为空!" << endl;
		return;
	}
	BitNode* tmpnode = NULL;
	tmpnode = root;
	while (tmpnode != NULL)
	{
		while (tmpnode!=NULL)
		{
			/*找到左边的第一个线索化的结点*/ 
			while (tmpnode->lefttag != 1)
			{
				tmpnode = tmpnode->leftChild;
			}
			/*输出该结点的数据*/
			cout << tmpnode->Data << endl;
			/*如果该结点的右子树结点一直是线索化结点，那么就需要一直打印 因为都是串联的*/
			while (tmpnode->righttag == 1)
			{
				cout << tmpnode->rightChild->Data << endl;
				tmpnode = tmpnode->rightChild;
			}
			/*走到这步表示 接下来的结点非线索化结点 需要跳过 寻找该节点的左结点*/
			tmpnode = tmpnode->rightChild;
		}
	}
		
}
#pragma endregion
#pragma region 主实现函数

int main(void)
{
	BitNode* n1 = new BitNode();
	BitNode* n3 = new BitNode();
	BitNode* n6 = new BitNode();
	BitNode* n8 = new BitNode();
	BitNode* n10 = new BitNode();
	BitNode* n14 = new BitNode();
	n1->Data = 1, n3->Data = 3, n6->Data = 6, n8->Data = 8, n10->Data = 10,n14->Data = 14;
	n1->leftChild = n3;
	n1->rightChild =n6;
	n3->leftChild = n8;
	n3->rightChild = n10;
	n6->leftChild = n14;
	PreOrderIterative(n1);
	PreOrderCuleTree(n1);
	return 0;
}

最终实现结果：