二叉树的遍历
 

 我们知道知道
 前序遍历 + 中序遍历 --------------- 可以确定唯一一棵二叉树
 后序遍历 + 中序遍历 --------------- 可以确定唯一一颗二叉树
 前序遍历 + 中序遍历 --------------- 不能唯一确定
 
！因为先序后序遍历都是确定根的位置，但不能确定左右子树的位置，一颗二叉树的建立需要根的位置也需要左右子树的位置。
 
根据前序遍历和中序遍历重建二叉树
 
首先来看下这两种遍历的方式， 前序遍历的遍历是：根节点 – 左子树 – 右子树 , 中序遍历是 左子树 – 根节点 – 右子树. 故前序遍历的第一个节点必然是二叉树的根节点， 来看上面二叉树的前序遍历 :
 a - b - d - e - c - f - g; 故可以确定a就是二叉树的根节点。 然后我们在中序遍历中找到a这个节点。
 d - b - e - (a) - f - c - g; 根据中序遍历先遍历左子树，再遍历根节点最后遍历右子树的这个特点，我们就知道了中序遍历中a的左边 d b e 是a的左子树部分， 因为中序遍历必定先遍历完根节点的左子树部分再遍历根节点， 故a的右边部分 f c g 就是a的右子树部分。 故接下来的过程就是找到a的左子树节点和a的右子树节点， 故a的左子树节点必然在中序遍历的 a 左边的部分， a 的右子树节点必定在中序遍历的a的右半部分, 以找a左子树节点为例子，此时我们知道了其左子树就是 d - b - e， 这三个节点， 而再看前序遍历， 前序遍历要先遍历根节点再遍历左子树， 故前序遍历中a后面的三个节点即为左子树的三个节点，其第一个节点即为左子树根节点。故b为a的左子树节点，同样我们以b为根节点的子树在中序遍历找到b的位置， 其位置为 d - （b） - e - a - f - c - g; 其左边为只有一个d为其左子树，右边只有一个e为其右子树。 同样找a右子树的时候， 由中序遍历知道了 f - c - g 是 a 的右子树， 故在前序遍历中知道了第一个是根节点a, 又知道其先遍历了3个左子树节点，故第五个节点开始遍历右子树，其第五个节点就是右子树的根节点。 以此递归，看下面的代码实现
 
/*
这里并没有专门写一个类或者结构体，表示一个节点(包括存放的数据和左右子树的指针)
直接用map表示每一个节点的左子树是那个节点和右子树是那个节点. 
*/
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
constexpr int N = 40;
int pre[N], in[N];
unordered_map<int, int> l, r, pos;

int Recstr_Tree(int il, int ir, int pl, int pr)
{
    int root = pre[pl];            // 可知前序遍历最先遍历根节点
    int k = pos[root];             // pos用 map快速找到根节点在中序遍历的位置 
    
    // 若il < k，即中序遍历的左边界小于当前根节点在中序遍历的节点位置，说明该根节点存在左子树, 进行递归
    // 故此时递归时, 左边子树的中序范围为 il ~ k - 1, 前序遍历的左边界要向前移动故 pl + 1, 然后前序的
    // 右边界如何确定， 可得 (k - 1) - il = x - (pl + 1)  -->  x = pl + k - il;
    if(il < k) l[root] = Recstr_Tree(il, k - 1, pl + 1, pl + k - il);   


    if(ir > k) r[root] = Recstr_Tree(k + 1, ir, pl + k - il + 1, pr);
    
    return root;          
} 

// 层序遍历 
auto level_traversal(int root)
{
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int node = q.front(); q.pop();
        cout << node << " ";
        if(l[node]) q.push(l[node]);
        if(r[node]) q.push(r[node]);
    }
}

auto main() -> int
{
    int n; cin >> n;
    for(int i = 0; i < n; ++i) cin >> pre[i];    // 输入前序遍历
    for(int i = 0; i < n; ++i)
    {
        cin >> in[i];                           // 输入中序遍历
        pos[in[i]] = i;                         // 保存每个节点在中序遍历的位置
    }
    int root = Recstr_Tree(0, n - 1, 0, n - 1); // 重建树
    level_traversal(root);                      // 进行层序遍历
    cout << endl;
    return 0;
}
 
根据后序遍历和中序遍历重建二叉树
 
相关题目的链接 ： AcWing 1497. 树的遍历
 
同样的话根据后序遍历 和 中序遍历重建二叉树也是同理，后序遍历是先遍历左子树 – 遍历右子树 – 最后遍历根节点， 故每次确定根节点应该是用后序遍历的右边界来确定， 故代码实现基本差不多 .
 
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
constexpr int N = 40;
int post[N], in[N];
unordered_map<int, int> l, r, pos;

int Recstr_Tree(int il, int ir, int pl, int pr)
{
    int root = post[pr];
    int k = pos[root];
    if(il < k) l[root] = Recstr_Tree(il, k - 1, pl, pl + k - il - 1);
    if(ir > k) r[root] = Recstr_Tree(k + 1, ir, pl + k - il, pr - 1); 
    return root;
}

auto level_traversal(int root)
{
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int node = q.front(); q.pop();
        cout << node << " ";
        if(l[node]) q.push(l[node]);
        if(r[node]) q.push(r[node]);
    }
}

auto main() -> int
{
    int n; cin >> n;
    for(int i = 0; i < n; ++i) cin >> post[i]; 
    for(int i = 0; i < n; ++i)
    { 
        cin >> in[i]; 
        pos[in[i]] = i;
    }
    int root = Recstr_Tree(0, n-1, 0, n-1);
    level_traversal(root);
    cout << endl;
    return 0;
}

二叉树的遍历规则主要有三种：前序遍历，中序遍历，后序遍历。它们是根据访问根节点的先后顺序来划分的。
 
前序遍历：
 
 
 
1.访问根节点
 2.前序遍历左子树
 3.右序遍历右子树
 
 
中序遍历：
 
 
 
1.中序遍历左子树
 2.访问根节点
 3.中序遍历右子树
 
 
后序遍历：
 
 
 
1.后序遍历左子树
 2.后序遍历右子树
 3.访问根节点
 
 

 如上图
 
前序遍历：1 2 4 8 9 5 3 6 7
 中序遍历：8 4 9 2 5 1 6 3 7
 后序遍历：8 9 4 5 2 6 7 3 1
 层次遍历：1 2 3 4 5 6 7 8 9
 
class Node():
    # 节点类
    def __init__(self, data=-1):
        self.data = data
        self.left = None
        self.right = None


class Tree():
    # 树类
    def __init__(self):
        self.root = Node()

    def add(self, data):
        # 为树加入节点
        node = Node(data)
        if self.root.data == -1:  # 如果树为空，就对根节点赋值
            self.root = node
        else:
            myQueue = [self.root]
            while myQueue:  # 对已有的节点进行层次遍历
                treeNode = myQueue.pop(0)
                if not treeNode.left:
                    treeNode.left = node
                    return
                elif not treeNode.right:
                    treeNode.right = node
                    return
                else:
                    myQueue.append(treeNode.left)
                    myQueue.append(treeNode.right)

    def pre_order_recursion(self, root):  # 递归实现前序遍历
        if not root:
            return
        print(root.data)
        self.pre_order_recursion(root.left)
        self.pre_order_recursion(root.right)

    def in_order_recursion(self, root):  # 递归实现中序遍历
        if not root:
            return
        self.in_order_recursion(root.left)
        print(root.data)
        self.in_order_recursion(root.right)

    def post_order_recursion(self, root):  # 递归实现后序遍历
        if not root:
            return
        self.post_order_recursion(root.left)
        self.post_order_recursion(root.right)
        print(root.data)


    def pre_order_stack(self, root):  # 堆栈实现前序遍历（非递归）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:
            while node:  # 从根节点开始，一直寻找他的左子树
                print(node.data)
                myStack.append(node)
                node = node.left
            node = myStack.pop()  # while结束表示当前节点node为空，即前一个节点没有左子树了
            node = node.right  # 开始查看它的右子树

    def in_order_stack(self, root):  # 堆栈实现中序遍历（非递归）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:  # 从根节点开始，一直寻找它的左子树
            while node:
                myStack.append(node)
                node = node.left
            node = myStack.pop()  # while结束表示当前节点node为空，即前一个节点没有左子树了
            print(node.data)

            node = node.right  # 开始查看它的右子树

    def post_order_stack(self, root):  # 堆栈实现后序遍历（非递归）
        # 先遍历根节点，再遍历右子树，最后是左子树，这样就可以转化为和先序遍历一个类型了，最后只把遍历结果逆序输出就OK了。
        if not root:
            return
        myStack1 = []
        myStack2 = []
        node = root
        while myStack1 or node:
            while node:
                myStack2.append(node)
                myStack1.append(node)
                node = node.right
            node = myStack1.pop()
            node = node.left
        while myStack2:
            print(myStack2.pop().data)

    def level_order_queue(self, root):  # 队列实现层次遍历（非递归）
        if not root:
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print(node.data)
            if node.left:
                myQueue.append(node.left)
            if node.right:
                myQueue.append(node.right)


if __name__ == '__main__':
    # 主函数
    datas = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    tree = Tree()  # 新建一个树对象
    for data in datas:
        tree.add(data)  # 逐个加入树的节点
    #
    print('递归实现前序遍历：')
    tree.pre_order_recursion(tree.root)

    print('\n堆栈实现前序遍历')
    tree.pre_order_stack(tree.root)

    print("\n\n递归实现中序遍历：")
    tree.in_order_recursion(tree.root)

    print("\n堆栈实现中序遍历：")
    tree.in_order_stack(tree.root)

    print('\n\n递归实现后序遍历：')
    tree.post_order_recursion(tree.root)

    print('\n堆栈实现后序遍历：')
    tree.post_order_stack(tree.root)

    print('\n\n队列实现层次遍历：')
    tree.level_order_queue(tree.root)

 给树的后序和中序遍历，求先序遍历
 假设有一棵树长这样
 
 很容易写出他的后序遍历DBAGFEC
 也很容易写出他中序遍历DABCGEF
 
 
1.后序遍历是前后根，根节点永远是最后一个，因此我们可以找到根节点c
 2.要我们输出前序遍历，因为根节点永远在前面，所以每次找到就输出就好了
 3.之后用find函数找到根节点c在中序遍历中的位置，划分为两段DAB GEF，然后中序遍历这两段，注意一定要是先递归DAB再递归GEF不然的话就是根后前而不是根前后了
 4.也将后序遍历划分为两段DAB GFE，用后序遍历递归下去
 
好了，直接上代码
 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void dg(string a,string b) {
	if (a.size() > 0) {
		char c = b[b.size() - 1];
		cout << c;
		int k = a.find(c);
		dg(a.substr(0, k), b.substr(0, k));
		dg(a.substr(k + 1), b.substr(k ,b.size()-k-1));
	}·
}
int main() {
	ios::sync_with_stdio(false);
	string in,aft;
	cin >> in >> aft;
	dg(in, aft);
}
 
给出前序遍历和中序遍历求后序遍历
 
#include<iostream>

using namespace std;
void dfs(string a, string b) {
	if (a.size() <= 0)return;
	char c = b[0];
	
	int x = a.find(c);
	dfs(a.substr(0, x), b.substr(1, x));
	dfs(a.substr(x + 1), b.substr(b.size()-x));
	cout << c;
}
int main() {
	string a, b;
	cin >> a >> b;
	dfs(a, b);
}
 
 
给出前序遍历和后序遍历求中序遍历
 

描述
 
 
 
输入某二叉树的后序遍历和中序遍历的结果，请输出前序遍历序列。假设输入的后序遍历和中序遍历的结果中都不含重复的数字。例如输入后序遍历序列{7,1,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6}，重建二叉树并返回后序遍历序列
 
 
输入
 
 
 
输入某二叉树的后序遍历和中序遍历的结果
 
 
输出
 
 
 
输出前序遍历序列
 
 
输入样例 1 
 
 
 
7 4 2 5 8 6 3 1
 4 7 2 1 5 3 8 6
 
 
输出样例 1
 
 
 
1 2 4 7 3 5 6 8
 
 
参考题目详解：已知前序遍历和中序遍历求二叉树 
 
实现代码：
 
#include<stdio.h>
#include<stdlib.h> 
#include<string.h>
typedef struct node* BinTree; 
struct node{
	int date;
	BinTree left;
	BinTree right;
};
BinTree Build(int post[] ,int in[],int size)
{
	if(size<=0)return NULL;
	//先在中序中找到根节点
	int i=0;
	for(i=0;i<size;i++)
	{
		if(in[i]==post[size-1])break;
	} 
	BinTree tree=(BinTree)malloc(sizeof(struct node));
	tree->date=post[size-1];
	tree->left=Build(post,in,i);
	tree->right=Build(post+i,in+i+1,size-1-i);
	return tree;
}
 
void preorder(BinTree T)  //前序遍历
{
	if(T==NULL)return;
	else{
	    printf("%d ",T->date);
		preorder(T->left);
		preorder(T->right);
	}
	
} 
int main()
{
	char postt[800],inn[800];  
	gets(postt);
	gets(inn);  
	int size=strlen(postt);  
	int post[800],in[800];
	int postcount=0; 
	int i;
	for(i=0;i<size;i++)
	{
		if(i==0)
		{
			post[postcount]=postt[i]-'0';
		}
		else
		{
			if(postt[i]>='0'&&postt[i]<='9')
			{
				//此if-else 用来转换多位数为int类型 
				if(postt[i-1]==' ')  //如果前一个元素为空格 
				{
					postcount++;
				    post[postcount]=postt[i]-'0';
				}
				
				else  //如果前一个元素不是空格，那么说明与前一个元素一同构成的数  例如：10 
				{
					post[postcount]=post[postcount]*10+(postt[i]-'0');
				}
			}
			
		}
		
	}
	int incount=0;
	for(i=0;i<size;i++)
	{
		if(i==0)
		{
			in[incount]=inn[i]-'0'; 
		}
		else
		{
			if(inn[i]>='0'&&inn[i]<='9')
			{
				if(inn[i-1]==' ')
				{
					incount++;
				    in[incount]=inn[i]-'0';
				}
				
				else
				{
					in[incount]=in[incount]*10+(inn[i]-'0');
				}
			}
			
		}
		
	}  
    //如果后序遍历的结点数与中序遍历的结点数相同且不为0，那么可以找到对应二叉树 
    if(postcount==incount&&postcount!=0)  
    {
    	BinTree T;
		T=Build(post,in,postcount+1);
		preorder(T);
	}
	
    
	return 0;

}