题目：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），将遍历序列输出到显示器上。

【基本要求】从键盘输入一棵二叉树的先序序列，以二叉链表作为存储结构，建立二叉树并对其进行遍历（先序、中序和后序），然后将遍历结果打印输出。

代码如下：

#include<stdio.h>
#include<stdlib.h>
//定义二叉树链表结点结构
typedef struct Node
{
    char data;
    struct Node* Lchild;
    struct Node* Rchild;
}BiTree, * PBiTree;

//创建二叉树
void CreateBiTree(PBiTree* bt)    //此时bt为二级指针
{                                 
    char ch;
    ch = getchar();
    if (ch == '*')
    {
        *bt = NULL;
    }
    else
    {
        *bt = (PBiTree)malloc(sizeof(BiTree));
        (*bt)->data = ch;
        CreateBiTree(&((*bt)->Lchild));   //一级指针值为空，二级指针要把地址传入
        CreateBiTree(&((*bt)->Rchild));
    }
}
//先序遍历
void PreOrder(PBiTree root)
{
    if (root != NULL)
    {
        printf("%c", root->data);
        PreOrder(root->Lchild);
        PreOrder(root->Rchild);
    }
}
//中序遍历
void InOrder(BiTree* root)
{
    if (root != NULL)
    {
        InOrder(root->Lchild);
        printf("%c", root->data);
        InOrder(root->Rchild);
    }
}
//后序遍历
void PostOrder(BiTree* root)
{
    if (root != NULL)
    {
        PostOrder(root->Lchild);
        PostOrder(root->Rchild);
        printf("%c", root->data);
    }
}

int main()
{
    PBiTree bt = NULL;//创建一个空树
    printf("输入先序二叉树结点(子树为空输入*)：\n");
    CreateBiTree(&bt);
    printf("\n输出先序遍历：");
    PreOrder(bt);
    printf("\n输出中序遍历：");
    InOrder(bt);
    printf("\n输出后序遍历：");
    PostOrder(bt);
    return 0;
}

运行结果：

思路：有个很关键的条件就是树的大小能定下来，而且是按照一个个顺序放的。

回想由中序遍历和后序遍历确定二叉树，我们每次都找下一个更小的左右子树范围的区间进行递归。

那么这个思路延续。根据完全二叉树来先递归建立好空树，在建立过程中push_up每个节点子树的siz.

然后在输入的数组中进行递归找到子树，最后用bfs输出一下就好。

感觉是最近线段树主席树做魔怔了，上来就套。但是如果去模拟就知道，线段树和这个树完全对应的情况只有满树的时候，不然建出来的树对应的状态是不同的。

因为线段树是由区间来划分的，而这些课上的树是节点来划分的。 

注意：代码中递归的边界都是用左子树当前来算的。（这个bug我调了好久

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5;
typedef int LL;
LL n;
struct Tree{
    LL lson,rson;
    LL val;
    LL siz;
}tree[maxn*4];
LL a[maxn];
LL build(LL p){///先建好对应的空树
    if(p>n) {
        tree[p].siz=0;
        return -1;
    }
    tree[p].siz=1;
    tree[p].val=-1;
    tree[p].lson=build(p*2);
    tree[p].rson=build(p*2+1);
    tree[p].siz=tree[p*2].siz+tree[p*2+1].siz+1;
    return p;
}
void update(LL p,LL l,LL r){
    if(p>n) return;
    tree[p].val=a[r];

    update(p*2,l,l+tree[p*2].siz-1);
    update(p*2+1,l+tree[p*2].siz,r-1);
}
void bfs(){
    queue<LL>que;
    que.push(1);///树根节点
    while(!que.empty()){
        LL p=que.front();que.pop();

        if(p>n) break;
        que.push(p*2);
        que.push(p*2+1);
    }
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>n;
  LL root=build(1);
  for(LL i=1;i<=n;i++) cin>>a[i];

  update(root,1,n);
  bfs();
return 0;
}

提供一些其他做法：

旺哥人工打表，也就是人工确定每个n对应的树的深度形态，然后打表输出。 

dfs直接将节点存好。

%%%zx聚聚(zx聚聚太强拉

线索二叉树后序线索化，后序遍历输出

一.写码思路

1. 我们要进行后序遍历的化，需要记录每个结点的 Parent 结点，我之前觉得可能不需要这个，直接用前驱就行了，但是后序遍历结点的前驱不一定是他的 Parent 结点。
   例如下面这个例子
   
   B的Parent结点是A，但他的前驱是E
   因此我们这个结点设定为如下

template<class T>
struct TreeNode
{
	T Data;
	TreeNode* Lkid;
	TreeNode* Rkid;
	TreeNode* Parent;	       //指向该节点的父母节点
	int Ltag;
	int Rtag;
};

Ltag和Rtag记录是否有孩子，并定义

#define Link	0	//表示该节点有孩子节点
#define Thread	1   //表示该节点指向后续节点

①我们可以用一个类来封装这个二叉树，所以要进行构造，析构等函数
析构的时候我们可以用一个栈来储存这些结点，最后在析构的时候 delete 掉

②由于后序遍历的时候我们还要记录上一个访问过的结点，方便让结点指向他的前驱
我们设定为Pre_Node
然而这个 Pre_Node 在遍历的时候要一直记录上一个访问的结点，所以我们把他设为私有类

因此我们的类中就有这些成员

template<class T>
class Thread_tree
{
private:
	TreeNode<T>* Pre_Node;
	TreeNode<T>* Tree_Node_Stack[maxsize];
	
public:
    TreeNode<T>* Tree;   //也可以写一个函数将这个成员数据 return 出来 ；其实也可以不把这个数据封装起来，直接在主函数设定一个Tree结点也完全ok的
	Thread_tree();       //构造函数 
	~Thread_tree();      //析构函数 
	void PostOrder_Thread(TreeNode<T>* &Tree);   //后序线索化 
	void PostOrder(TreeNode<T>* &Tree);          //后序遍历 
	void Create_Thread_Tree(TreeNode<T>* &Tree,TreeNode<T>* Parent);    //构造线索二叉树 
};

二.写准备遍历前的代码

1. 创造二叉树函数

//创造二叉树 
template<class T>
void Thread_tree<T>::Create_Thread_Tree(TreeNode<T>* &Tree,TreeNode<T>* Parent_Node)
{
	char Data;
	cin >> Data;
	if (Data =='#')
		Tree = NULL;
	else
	{
		Tree = new TreeNode<T>;             //记得 delete 掉
		Tree->Parent = Parent_Node;        //指向父母节点
		Tree->Data = Data;
		Tree->Ltag = Link;
		Tree->Rtag = Link;
		Create_Thread_Tree(Tree->Lkid,Tree);  //Tree是孩子的父母节点
		Create_Thread_Tree(Tree->Rkid,Tree);
	}
}

这个函数中 Tree 是根节点，由于在后面的函数中我们还要使用这个变化后的根节点，也就是说在之后的函数中，只要用到Tree，那他指的就是根节点，所以我们将这个Tree设为引用，不然在这个构造函数后，我们没有记录根节点是谁。
其次还要设定一个Parent_Node，用来记录父结点，用来连接父节点和孩子结点。我们将这个结点赋值给每个结点的 Parent 结点，递归的时候再将上一层的结点设定为 Parent_Node，这样这个结点在递归的时候就能赋值给他孩子结点的 Parent 结点。(注意 Parent_Node 和 Parent 结点不要弄混，Parent_Node只是个传值的，Parent指向每个结点的父节点指针，作用相当于左 ，右孩子指针）

2.构造函数

//初始化二叉树  
template<class T>
Thread_tree<T>::Thread_tree():
	Pre_Node(NULL)
{
	
}

3.析构函数

//析构二叉树 
template<class T>
Thread_tree<T>::~Thread_tree()
{
	while (!Tree_stack.empty())
	{
		Tree_stack.pop();
	}
}

我们在后面的后序遍历的时候，每遍历一个结点，我们就入栈一个结点，最后用上述的循环一个一个 delete。

三.后序线索化二叉树

我们遍历线索化的顺序是 左 右 根
所以先递归左孩子，再递归右孩子
最后来线索化根

template<class T>
void Thread_tree<T>::PostOrder_Thread(TreeNode<T>* &Tree)
{
	if (Tree == NULL)
		return;
	
	PostOrder_Thread(Tree->Lkid);		//左
	PostOrder_Thread(Tree->Rkid);		//右
 
	if (Tree->Lkid == NULL)		        //根
	{
		Tree->Lkid = Pre_Node;
		Tree->Ltag = Thread;
	}
	if (Pre_Node != NULL && Pre_Node->Rkid == NULL)
	{
		Pre_Node->Rkid = Tree;
		Pre_Node->Rtag = Thread;
	}
 
	Pre_Node = Tree;
}

1. 递归出口
   当遍历的结点是NULL的时候，结束

2. 左孩子为空的时候
   左指针指向前驱，就是我们再类里面定义的 Pre_Node
   左标识设定为 Thread，就是指向线索的意思

3.右孩子是难点
右孩子为空的时候，要指向他的后继结点
但是这个时候我们这个结点不好指向他的后继结点
只有这一层递归结束以后，我们才能来到这个结点的后继
如：

D 结点的后继是 J，但这个时候 D 与 J 无联系，只有这一层递归结束，我们才能来到J结点
因此我们需要将当前结点设定为 Pre_Node,就是 Pre_Node = Tree;
这样我们来到 J 结点时，他的前一个结点的右孩子为空的话，就让他指向当前结点，也就是 Pre_Node的后继，再把右标识设定好。
再把当前节点设定为 Pre_Node。
如D是 Pre_Node，它指向当前结点，也就是 D 指向了 J。

四.后序遍历线索二叉树

①
后序遍历也是按照 左 右 中
所以我们先要找到最左边的结点
设定一个当前结点 Cur_Node
因此从根结点开始，一个一个判断，有左孩子，就往左。

	while (Cur_Node->Ltag == Link)//change,找到起始节点（在左树的最左边）
		{
			Cur_Node = Cur_Node->Lkid;
		}

（来到 H 结点）

②
之后访问他的后继
不过在访问后继之前先要把当前结点存到栈里面，方便后面析构
同时先输出当前结点

while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点
		{
			Tree_stack.push(Cur_Node)  ;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新
			Cur_Node = Cur_Node->Rkid;
		}

（先到 I ,再来到 D 结点，因为 I 结点的后继是 D，但 D 的右指针又指向了 I ）

③
这样我们的当前节点就来到了子树的根节点
不过还需要判断 ， 判断条件就是 根节点的右指针是刚刚访问过的结点

while (Cur_Node != NULL && Cur_Node->Rkid == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该子树只差根就遍历完成
		{
			Tree_stack.push(Cur_Node) ;
			cout << Cur_Node->Data << " ";
			
			if(Cur_Node==Tree)
			return;
			Pre_Node = Cur_Node;
			Cur_Node = Cur_Node->Parent;		//访问子树后回到上一层
		}

当然如果这个根节点是整个树的根节点，输出完之后结束程序
否则就指向这个子树根节点的父节点，为什么要指向父节点？因为D的右指针指向的是 I 结点
这样我们就来到了上一层树
最后记录访问过的结点

（来到 B 结点，但不能输出）

④
这个时候我们要先遍历 B 结点右树的最左下结点，也就是 J

if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子
		{
			Cur_Node = Cur_Node->Rkid;
		}

但其实我们这个时候先到的是 E 结点，但是这一次最外面的循环就结束了，再从开头继续执行程序
记得我们循环开始的程序是什么吗？ 就是找到他最左下的结点，也就是 J

这样所有的结点就连起来了

这一部分的完整代码如下：

  //后序遍历二叉树 
template<class T>
void Thread_tree<T>::PostOrder(TreeNode<T>* &Tree)
{
	TreeNode<T> *Cur_Node = Tree;
	Pre_Node = NULL;
	while (Cur_Node != NULL)
	{
		while (Cur_Node->Ltag == Link)//change,找到起始节点（在左树的最左边）
		{
			Cur_Node = Cur_Node->Lkid;
		}
 
		while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点
		{
			Tree_stack.push(Cur_Node)  ;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新
			Cur_Node = Cur_Node->Rkid;
		}
 
		while (Cur_Node != NULL && Cur_Node->Rkid == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该子树只差根就遍历完成
		{
			Tree_stack.push(Cur_Node) ;
			cout << Cur_Node->Data << " ";
			
			if(Cur_Node==Tree)
			return;
			Pre_Node = Cur_Node;
			Cur_Node = Cur_Node->Parent;		//访问子树后回到上一层
		}
 
		if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子
		{
			Cur_Node = Cur_Node->Rkid;
		}
	}
}

五.完整代码

#include<iostream>
#include<stack>
using namespace std;
#define Link	0	//表示该节点有孩子节点
#define Thread	1	//表示该节点有后续节点

template<class T>
struct TreeNode
{
	T Data;
	TreeNode* Lkid;
	TreeNode* Rkid;
	TreeNode* Parent;	       //指向该节点的父母节点
	int Ltag;
	int Rtag;
};
 
template<class T>
class Thread_tree
{
private:
	TreeNode<T>* Pre_Node;
	stack<TreeNode<T>*> Tree_stack;
	
public:
    TreeNode<T>* Tree;   //也可以写一个函数将这个成员数据 return 出来 
	Thread_tree();       //构造函数 
	~Thread_tree();      //析构函数 
	void PostOrder_Thread(TreeNode<T>* &Tree);   //后序线索化 
	void PostOrder(TreeNode<T>* &Tree);          //后序遍历 
	void Create_Thread_Tree(TreeNode<T>* &Tree,TreeNode<T>* Parent);    //构造线索二叉树 
};
 
 //创造二叉树 
template<class T>
void Thread_tree<T>::Create_Thread_Tree(TreeNode<T>* &Tree,TreeNode<T>* Parent_Node)
{
	char Data;
	cin >> Data;
	if (Data =='#')
		Tree = NULL;
	else
	{
		Tree = new TreeNode<T>;
		Tree->Parent = Parent_Node;        //指向父母节点
		Tree->Data = Data;
		Tree->Ltag = Link;
		Tree->Rtag = Link;
		Create_Thread_Tree(Tree->Lkid,Tree);  //Tree是孩子的父母节点
		Create_Thread_Tree(Tree->Rkid,Tree);
	}
}
 

 
 //初始化二叉树  
template<class T>
Thread_tree<T>::Thread_tree():
	Pre_Node(NULL)
{
	
}
 
 //析构二叉树 
template<class T>
Thread_tree<T>::~Thread_tree()
{
	while (!Tree_stack.empty())
	{
		Tree_stack.pop();
	}
}
 
  //后序线索化二叉树 
template<class T>
void Thread_tree<T>::PostOrder_Thread(TreeNode<T>* &Tree)
{
	if (Tree == NULL)
		return;
	
	PostOrder_Thread(Tree->Lkid);		//左
	PostOrder_Thread(Tree->Rkid);		//右
 
	if (Tree->Lkid == NULL)		        //根
	{
		Tree->Lkid = Pre_Node;
		Tree->Ltag = Thread;
	}
	if (Pre_Node != NULL && Pre_Node->Rkid == NULL)
	{
		Pre_Node->Rkid = Tree;
		Pre_Node->Rtag = Thread;
	}
 
	Pre_Node = Tree;
}

  //后序遍历二叉树 
template<class T>
void Thread_tree<T>::PostOrder(TreeNode<T>* &Tree)
{
	TreeNode<T> *Cur_Node = Tree;
	Pre_Node = NULL;
	while (Cur_Node != NULL)
	{
		while (Cur_Node->Ltag == Link)//change,找到起始节点（在左树的最左边）
		{
			Cur_Node = Cur_Node->Lkid;
		}
 
		while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点
		{
			Tree_stack.push(Cur_Node)  ;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新
			Cur_Node = Cur_Node->Rkid;
		}
 
		while (Cur_Node != NULL && Cur_Node->Rkid == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该子树只差根就遍历完成
		{
			Tree_stack.push(Cur_Node) ;
			cout << Cur_Node->Data << " ";
			
			if(Cur_Node==Tree)
			return;
			Pre_Node = Cur_Node;
			Cur_Node = Cur_Node->Parent;		//访问子树后回到上一层
		}
 
		if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子
		{
			Cur_Node = Cur_Node->Rkid;
		}
	}
}
 
int main()
{
	Thread_tree<char> MyTree;
	TreeNode <char> *parent;
	MyTree.Create_Thread_Tree(MyTree.Tree,parent);
	MyTree.PostOrder_Thread(MyTree.Tree);
	MyTree.PostOrder(MyTree.Tree);
	return 0;
}

六.测试数据

就用上面的例子来吧
abdh##i##ej###cf##g##

再找个新例子，简单一点
12##34###

到这里我们的后序遍历就完成了，希望能帮到你
反正我之前是把这个理解了好久

那之后能点个赞就更好了！！！