实现二叉树先序，中序和后序遍历

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* lch;
    TreeNode* rch;
    TreeNode(int x):val(x),lch(NULL),rch(NULL){}
};
void createTree(TreeNode* root, int& cnt){
    if(cnt == 0)
        return;
    int p, l, r;
    cin >> p >> l >> r;
    if(l != 0){
        TreeNode* lch = new TreeNode(l);
        root->lch = lch;
        createTree(root->lch, --cnt);
    }
    if(r != 0){
        TreeNode* rch = new TreeNode(r);
        root->rch = rch;
        createTree(root->rch, --cnt);
    }
}
void preVisit(TreeNode* root){
    if(!root) return;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty()){
        TreeNode* cur = s.top();
        s.pop();
        cout << cur->val << " ";
        if(cur->rch) s.push(cur->rch);
        if(cur->lch) s.push(cur->lch);
    }
    cout << endl;
    return;
}
void inVisit(TreeNode* root){
    if(!root) return;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while(!s.empty() || cur){
        while(cur){
            s.push(cur);
            cur = cur->lch;
        }
        cur = s.top();
        cout << cur->val << " ";
        s.pop();
        if(cur->rch) cur = cur->rch;
        else cur = NULL;
    }
    cout << endl;
    return;
}
void postVisit(TreeNode* root){
    if(!root) return;
    stack<TreeNode*> s;
    TreeNode* temp = NULL;
    TreeNode* cur = root;
    while(!s.empty() || cur){
        while(cur){
            s.push(cur);
            cur = cur->lch;
        }
        cur = s.top();
        if(cur -> rch && temp != cur->rch){
            cur = cur->rch;
        }
        else{
            cout << cur->val << " ";
            temp = cur;
            s.pop();
            cur = NULL;
        }
    }
    cout << endl;
    return;
}
int main(){
    int n, root_val;
    cin >> n >> root_val;
    TreeNode* root = new TreeNode(root_val);
    for(int i = 0; i < n; i++){
        createTree(root, n);
    }
    preVisit(root);
    inVisit(root);
    postVisit(root);
}

#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int value):val(value),left(nullptr),right(nullptr){}
};
// 建树
void createTree(TreeNode* root,int cnt)
{
    if(!cnt) return;
    int p,l,r;
    cin>>p>>l>>r;
    if(l)
    {
         TreeNode* left = new TreeNode(l);
         root->left = left;
         createTree(root->left,cnt-1);
    }
    if(r)
    {
        TreeNode* right = new TreeNode(r);
        root->right = right;
        createTree(root->right,cnt-1);
    }
   
}
// 前序非递归
void preOrder(TreeNode* root,vector<int>& ans)
{
    if(!root) return;
    stack<TreeNode*>s;
    TreeNode* p = root;
    while(!s.empty() || p)
    {
// 一直往左走
        while(p)
        {
// 先访问再入栈
            ans.push_back(p->val);
            s.push(p);
            p = p->left;
        }
                // 已经到最左边，出栈一个结点
        p = s.top();
        s.pop();
                // 如果当前结点有右子树，则进入右子树
        if(p->right) p = p->right;
                // 否则将访问指针p置空
        else p = nullptr;
    }
}
// 中序非递归
void inOrder(TreeNode* root,vector<int>& ans)
{
    if(!root) return;
    stack<TreeNode*>s;
    TreeNode* p = root;
    while(!s.empty() || p)
    {
                
        while(p)
        {
            s.push(p);
            p = p->left;
        }
                // 此处与先序不同，这里是先入栈，出栈的时候再访问
        p = s.top();
        ans.push_back(p->val);
        s.pop();
        if(p->right) p = p->right;
        else p = nullptr;
    }
}
// 后序非递归
void postOrder(TreeNode* root,vector<int>& ans)
{
    if(!root) return ;
    stack<TreeNode*>s;
    TreeNode* p = root;
        // 与先序中序有所不同，使用了一个标志量来保存刚刚访问过的结点
    TreeNode* r = nullptr;
    while(!s.empty() || p)
    {

                // 一直向左
        while(p)
        {
            s.push(p);
            p = p->left;
        }
        p = s.top();
                // 如果当前结点有右子树并且不是刚访问过，则访问右子树
        if(p->right && p->right!=r) p = p->right;
        else{
                      // 否则 访问当前结点
                       // 并利用标志变量记录下来
                        // 访问指针p置空，很关键
            s.pop();
            ans.push_back(p->val);
            r = p;
            p = nullptr;
        }
    }
}
int main()
{
    int N,root_val;
    cin>>N>>root_val;
    TreeNode* root = new TreeNode(root_val);
    createTree(root,N);
    vector<int>ans;
    preOrder(root,ans);
    for(int i : ans)
        cout<<i<<" ";
    cout<<endl;
    ans.clear();
    inOrder(root,ans);
    for(int i:ans)
        cout<<i<<" ";
    cout<<endl;
    ans.clear();
    postOrder(root,ans);
    for(int i:ans)
        cout<<i<<" ";
    cout<<endl;
    return 0;
}

/****************************************************************************
**
** Copyright 2019 yanglingwell@sina.com
**
** Permission is hereby granted, free of charge, to any person obtaining
** a copy of this software and associated documentation files (the "Software"),
** to deal in the Software without restriction, including without limitation the
** rights to use, copy, modify, merge, publish, distribute, sublicens-e, and/or
** sell copies of the Software, and to permit persons to whom the Software is
** furnished to do so, subject to the following conditions:
**
** The above copyright notice and this permission notice shall be included in
** all copies or substantial portions of the Software.
**
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
** THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
** LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
** OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
****************************************************************************/

/*
 *【题目】
 * 遍历二叉树
 *【要求】
 * 分别以递归和非递归实现前序、中序、后序遍历二叉树
 *【解题思路】 
 * 见代码
 */

#include <list>
#include <map>
#include <stack>
#include <iostream>

using namespace std;

// 双向链表/树的节点
struct Node
{
    Node* left;
    Node* right;
    int val;

    Node(int v) : val(v), left(nullptr), right(nullptr){}
};

// 递归前序遍历二叉树
void preorder_traversal_recursion(Node* node)
{
    if (node == nullptr) return;

    cout << node->val << " ";
    preorder_traversal_recursion(node->left);
    preorder_traversal_recursion(node->right);
}

// 递归中序遍历二叉树
void inorder_traversal_recursion(Node* node)
{
    if (node == nullptr) return;

    inorder_traversal_recursion(node->left);
    cout << node->val << " ";
    inorder_traversal_recursion(node->right);
}

// 递归后序遍历二叉树
void postorder_traversal_recursion(Node* node)
{
    if (node == nullptr) return;

    postorder_traversal_recursion(node->left);
    postorder_traversal_recursion(node->right);
    cout << node->val << " ";
}

// 非递归前序遍历二叉树
void preorder_traversal(Node* node)
{
    if (node == nullptr) return;

    stack<Node*> stk;
    stk.push(node);

    while (!stk.empty())
    {
        Node* cur_node = stk.top();
        stk.pop();

        if (!stk.empty() && stk.top() == nullptr)
        {
            stk.pop();
            cout << cur_node->val << " ";
            continue;
        }

        if (cur_node->right != nullptr)
        {
            stk.push(cur_node->right);
        }

        if (cur_node->left != nullptr)
        {
            stk.push(cur_node->left);
        }

        //前序 nullptr 标记当前节点的左右子树已经遍历
        stk.push(nullptr);
        stk.push(cur_node);
    }
}

// 非递归中序遍历二叉树
void inorder_traversal(Node* node)
{
    if (node == nullptr) return;

    stack<Node*> stk;
    stk.push(node);

    while (!stk.empty())
    {
        Node* cur_node = stk.top();
        stk.pop();

        if (!stk.empty() && stk.top() == nullptr)
        {
            stk.pop();
            cout << cur_node->val << " ";
            continue;
        }

        if (cur_node->right != nullptr)
        {
            stk.push(cur_node->right);
        }

        // 中序
        stk.push(nullptr);
        stk.push(cur_node);

        if (cur_node->left != nullptr)
        {
            stk.push(cur_node->left);
        }
    }
}

// 非递归后序遍历二叉树
void postorder_traversal(Node* node)
{
    if (node == nullptr) return;

    stack<Node*> stk;
    stk.push(node);

    while (!stk.empty())
    {
        Node* cur_node = stk.top();
        stk.pop();

        if (!stk.empty() && stk.top() == nullptr)
        {
            stk.pop();
            cout << cur_node->val << " ";
            continue;
        }

        // 后序
        stk.push(nullptr);
        stk.push(cur_node);

        if (cur_node->right != nullptr)
        {
            stk.push(cur_node->right);
        }

        if (cur_node->left != nullptr)
        {
            stk.push(cur_node->left);
        }
    }
}

Node* get_node(map<int, Node*>& m, int t)
{
    if(t == 0) return nullptr;
    if (m.find(t) == m.end())
    {
        m[t] = new Node(t);
    }
    return m[t];
}

int main()
{ 
    Node* tree = nullptr;
    int n, t;
    map<int, Node*> tm;

    while (cin >> n >> t)
    {
        tree = tm[t] = new Node(t);
        int fa, lc, rc;
        for(int i = 0; i < n; ++i)
        {
            cin >> fa >> lc >> rc;

            get_node(tm, fa)->left = get_node(tm, lc);
            get_node(tm, fa)->right = get_node(tm, rc);
        }

        preorder_traversal(tree);
        cout << endl;
        inorder_traversal(tree);
        cout << endl;
        postorder_traversal_recursion(tree);
        cout << endl;
    }
   /* 
    cout << "非递归前序遍历二叉树: ";
    preorder_traversal(tree);
    cout << endl << "递归前序遍历二叉树: ";
    preorder_traversal_recursion(tree);
    cout << endl << endl;

    cout << "非递归中序遍历二叉树: ";
    inorder_traversal(tree);
    cout << endl << "递归中序遍历二叉树: ";
    inorder_traversal_recursion(tree);
    cout << endl << endl;

    cout << "非递归后序遍历二叉树: ";
    postorder_traversal(tree);
    cout << endl << "递归后序遍历二叉树: ";
    postorder_traversal_recursion(tree);
    cout << endl << endl;
    */

    return 0;
}

#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

void createTree(TreeNode* root, int& n) {
    if(root == nullptr)
        return ;
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;
    if(leftVal != 0){
        TreeNode* leftNode = new TreeNode(leftVal);
        leftNode->left = leftNode->right = nullptr;
        root->left = leftNode;
        createTree(leftNode, --n);
    }
    if(rightVal != 0){
        TreeNode* rightNode = new TreeNode(rightVal);
        rightNode->left = rightNode->right = nullptr;
        root->right = rightNode;
        createTree(rightNode, --n);
    }
    return ;
} 
void preOrder(TreeNode* root) {
    if(root == nullptr)
        return ;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
    return ;
}

void inOrder(TreeNode* root) {
    if(root == nullptr)
        return ;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
    return ;
}

void postOrder(TreeNode* root) {
    if(root == nullptr)
        return ;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
    return ;
}

int main() {
    int N, rootVal;
    cin >> N >> rootVal;
    TreeNode* root = new TreeNode(rootVal);
    root->left = root->right = nullptr;
    createTree(root, N);
    preOrder(root);
    cout << endl;
    inOrder(root);
    cout << endl;
    postOrder(root);
    return 0;
}

def inorder(root):
    if tree_dict[root][0]:
        inorder(tree_dict[root][0])
    print(root, end=' ')
    if tree_dict[root][1]:
        inorder(tree_dict[root][1])
def preorder(root):
    print(root, end=' ')
    if tree_dict[root][0]:
        preorder(tree_dict[root][0])
    if tree_dict[root][1]:
        preorder(tree_dict[root][1])
def postorder(root):
    if tree_dict[root][0]:
        postorder(tree_dict[root][0])
    if tree_dict[root][1]:
        postorder(tree_dict[root][1])
    print(root, end=' ')
tree_dict = dict()
n, root = tuple(map(int, input().strip().split()))
for i in range(n):
    fa, lch, rch = list(map(int, input().strip().split()))
    tree_dict[fa] = (lch, rch)
preorder(root)
print()
inorder(root)
print()
postorder(root)

import java.util.*;
import java.io.*;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = br.readLine().split(" ");
        int len = Integer.parseInt(params1[0]);
        Map<Integer,TreeNode> map = new HashMap<>();
        TreeNode head = new TreeNode(Integer.parseInt(params1[1]));
        map.put(Integer.parseInt(params1[1]),head);
        for(int i = 0;i < len; i++){
            String[] params2 = br.readLine().split(" ");
            int curVal = Integer.parseInt(params2[0]);
            int leftVal = Integer.parseInt(params2[1]);
            int rightVal = Integer.parseInt(params2[2]);
            TreeNode cur = map.getOrDefault(curVal,null);
            if(cur == null){
                cur = new TreeNode(curVal);
                map.put(curVal,cur);
            }
            if(leftVal != 0){
                cur.left = new TreeNode(leftVal);
                map.put(leftVal,cur.left);
            }
            if(rightVal != 0){
                cur.right = new TreeNode(rightVal);
                map.put(rightVal,cur.right);
            }
        }
        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        afterOrder(head);
    }
    
    /*
    先序遍历 用一个栈即可，因为栈是先入后厨，所以先压入左节点，在压入右节点，弹出的节点输出
    */
    public static void preOrder(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty()){
                TreeNode cur = stack.pop();
                System.out.print(cur.val + " ");
                if (cur.right != null){
                    stack.push(cur.right);
                }
                if (cur.left != null){
                    stack.push(cur.left);
                }
            }
            
        }
    }
    
    //中序遍历 213
    //先把左边界全部进栈，弹出一个节点，其有右节点，则在压入他的所有左边界
    public static void inOrder(TreeNode head){
        if (head != null){
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head !=null){
                if (head!=null){
                    stack.push(head);
                    head = head.left;
                }else {
                    //左树已经到头来，则可以pop了,然后pop时也可以观察有无右树
                    head = stack.pop();
                    System.out.print(head.val + " ");
                    head = head.right;
                }

            }
        }
    }
    
    //后序遍历231  --- 两个栈 第一个栈头左右 --》头右左 再用一个栈左右头
    public static void afterOrder(TreeNode head){
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while(!stack1.isEmpty()){
            TreeNode cur = stack1.pop();
            if(cur.left != null){
                stack1.push(cur.left);
            }
            if(cur.right != null){
                stack1.push(cur.right);
            }
            stack2.push(cur);
        }
        while(!stack2.isEmpty()){
            System.out.print(stack2.pop().val + " ");
        }
    }
}

import java.io.*;
import java.util.Scanner;
import java.util.Stack;
 class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val){
            this.val = val;
        }
    }
public class Main{
    public static TreeNode createTree(BufferedReader br) throws Exception{
        String[] str = br.readLine().split(" ");
        int[] node = new int[str.length];
        for(int i = 0; i < str.length; i++){
            node[i] = Integer.parseInt(str[i]);
        }
           //构造该行输入对应节点
        TreeNode root = new TreeNode(node[0]);
        if( node[1] != 0 )  root.left = createTree(br);
        if( node[2] != 0 )  root.right = createTree(br);
        return root;
    }
    
    public static void main(String[] args) throws Exception{
//         Scanner sc = new Scanner(System.in);
//         String str = sc.nextLine();
//         TreeNode root = createTree(sc);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        TreeNode root = createTree(br);
        
        preOrder2(root);
        System.out.println();    
        infixOrder2(root);
        System.out.println(); 
        postOrder2(root);
        System.out.println(); 
    }
    // 递归实现
    public static void preOrder(TreeNode root){       
        if(root == null){
          return; 
        } 
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
        public static void infixOrder(TreeNode root){
        if(root == null){
          return; 
        }
        infixOrder(root.left);
        System.out.print(root.val+" ");  
        infixOrder(root.right);
    }
        public static void postOrder(TreeNode root){
         if(root == null){
          return; 
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");  
    }
    // 非递归实现
    //先压入头节点，再弹出它，压入他的右节点和左借点。重复
    public static void preOrder2(TreeNode root){
        Stack<TreeNode> st = new Stack();
        if(root == null){
            return;
        }
        st.push(root);
        while(!st.isEmpty()){
            root = st.pop();
            System.out.print(root.val+" ");
            if(root.right != null){
                st.push(root.right);
            }
            if(root.left != null){
                st.push(root.left);
            }
        }
    }
    public static void infixOrder2(TreeNode root){
        Stack<TreeNode> st = new Stack();
        if(root == null){
            return;
        }
        st.push(root);
        while(root.left != null){
            root = root.left;
            st.push(root);
        }
        while(!st.isEmpty()){
            root = st.pop();
            System.out.print(root.val+" ");
            if(root.right != null){
                root = root.right;
                st.push(root);
                while(root.left != null){
                    root = root.left;
                    st.push(root);
                }
            }
        }
    }
    public static void postOrder2(TreeNode root){
        Stack<TreeNode> st1 = new Stack();
        Stack<TreeNode> st2 = new Stack();
        // 先把shuju数据全压入s2
        if(root == null){
            return;
        }
        st1.push(root);
        while(!st1.isEmpty()){
            root = st1.pop();
            st2.push(root);
            if(root.left != null){
                st1.push(root.left);
            }
            if(root.right != null){
                st1.push(root.right);
            }
        }
        //依次弹出s2
        while(!st2.isEmpty()){
             root = st2.pop();
             System.out.print(root.val+" ");
        }
        
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef int Id;

typedef struct {
  Id id;
  Id l_child, r_child;
} TreeNodeInfo, *INFO;

void preorder(INFO infos, Id root_id) {
  if (!root_id) return;
  fprintf(stdout, "%d ", root_id);
  preorder(infos, infos[root_id].l_child);
  preorder(infos, infos[root_id].r_child);
}

void inorder(INFO infos, Id root_id) {
  if (!root_id) return;
  inorder(infos, infos[root_id].l_child);
  fprintf(stdout, "%d ", root_id);
  inorder(infos, infos[root_id].r_child);
}

void postorder(INFO infos, Id root_id) {
  if (!root_id) return;
  postorder(infos, infos[root_id].l_child);
  postorder(infos, infos[root_id].r_child);
  fprintf(stdout, "%d ", root_id);
}

int main(const int argc, const char* const argv[]) {
  int n, root_id;
  fscanf(stdin, "%d %d", &n, &root_id);
  
  INFO infos = (INFO) malloc ((n + 1) * sizeof(TreeNodeInfo)) ;
  Id fa, l_ch, r_ch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
    infos[fa].id = fa;
    infos[fa].l_child = l_ch;
    infos[fa].r_child = r_ch;
  }
  
  preorder(infos, root_id);
  fputc(10, stdout);
  
  inorder(infos, root_id);
  fputc(10, stdout);
  
  postorder(infos, root_id);
  return 0;
}

今天遍历大总结：递归 栈 mirros的前中后

let [n,root]=readline().split(' ').map(item=>parseInt(item))
const myMap=new Map()
const listNode=function(val){
    this.val=val
    this.left=null
    this.right=null
}
while(n){
     const [fa,lch,rch]=readline().split(' ').map(item=>parseInt(item))
     myMap.set(fa,[lch,rch])
     n--
}

const createTree=function(rootval){
    if(rootval){
         const node=new listNode(rootval)
         const [left,right]=myMap.get(rootval)
         node.left=createTree(left)
         node.right=createTree(right)
        return node
    }else{
        return;
    }
}
   
let treeRoot=createTree(root)

//递归的先序、中序和后序
// let res=[]
// const preTraverse=function(root){
//     if(root){
//        res.push(root.val)
//        preTraverse(root.left)
//        preTraverse(root.right) 
//     }
// }
// preTraverse(treeRoot)
// console.log(res.join(' '))

// res=[]
// const inTraverse=function(root){
//     if(root){
//       inTraverse(root.left) 
//         res.push(root.val)   
//        inTraverse(root.right) 
//     }
// }
// inTraverse(treeRoot)
// console.log(res.join(' '))

// res=[]
// const befTraverse=function(root){
//     if(root){
//        befTraverse(root.left)
//        befTraverse(root.right)  
//        res.push(root.val)
//     }
// }
// befTraverse(treeRoot)
// console.log(res.join(' '))
    

//非递归的先序后序中序--栈版本
// let res=[]
// const preTraverse=function(){
//     let stack=[]
//     stack.push(treeRoot)
//     while(stack.length){
//         const node=stack.pop()
//         res.push(node.val)
// //         先右再左
//          if(node.right)stack.push(node.right)
//         if(node.left)stack.push(node.left)     
//     }
//     console.log(res.join(' '))
// }
// preTraverse()

// res=[]
// const inTraverse=function(){
//     let stack=[]
//     let head=treeRoot

//     while(stack.length||head){
//         if(head){
//             stack.push(head)
//             head=head.left
//         }else{
//             let node=stack.pop()
//             res.push(node.val)
//             head=node.right
//         }
//     }
//      console.log(res.join(' '))
// }
// inTraverse()

// res=[]
// const befTraverse=function(){
//     let stack1=[],stack2=[]
//     stack2.push(treeRoot)
//     while(stack2.length){
//         let node =stack2.pop()
//         stack1.push(node)
//         if(node.left) stack2.push(node.left) 
//         if(node.right) stack2.push(node.right) 
//     }
//     while(stack1.length){
//         res.push(stack1.pop().val)
//     }
//     console.log(res.join(' '))
// }
// befTraverse()

//非递归的先序后序中序--mirros排序版本  非递归非栈 空间O(1)

import java.util.Scanner;
import java.util.HashSet;

class Node{
    public int value;
    public Node left;
    public Node right;
    public Node(int val){
        this.value = val;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        if(sc.hasNextLine()){
            String[] input = sc.nextLine().split(" ");
            int n = Integer.parseInt(input[0]);
            Node root = new Node(Integer.parseInt(input[1]));
            HashSet<Node> set = new HashSet<Node>();
            set.add(root);
            
            for(int j= 0;j<n;j++){
                // build the binary tree
                String[] nodes = sc.nextLine().split(" ");
                int fatherValue = Integer.parseInt(nodes[0]);
                int leftValue = Integer.parseInt(nodes[1]);
                int rightValue = Integer.parseInt(nodes[2]);
                for(Node e:set){
                    if(e.value == fatherValue){
                        e.left = leftValue==0?null:new Node(leftValue);
                        e.right = rightValue==0?null:new Node(rightValue);
                        if(leftValue!=0){
                            set.add(e.left);
                        }
                        if(rightValue!=0){
                            set.add(e.right);
                        }
                        set.remove(e);
                        break;
                    }
                }
            }
            preOrder(root);
            System.out.print("\n");
            inOrder(root);
            System.out.print("\n");
            posOrder(root);
        }
    }
    
    public static void preOrder(Node d){
        if(d==null){
            return;
        }
        System.out.print(d.value);
        System.out.print(" ");
        if(d.left!=null){
            preOrder(d.left);
        }
        if(d.right!=null){
            preOrder(d.right);
        }
    }
    public static void inOrder(Node d){
        if(d==null){
            return;
        }
        if(d.left!=null){
            inOrder(d.left);
        }
        System.out.print(d.value);
        System.out.print(" ");
        
        if(d.right!=null){
            inOrder(d.right);
        }
    }
    public static void posOrder(Node d){
        if(d==null){
            return;
        }
        if(d.left!=null){
            posOrder(d.left);
        }
        if(d.right!=null){
            posOrder(d.right);
        }
        System.out.print(d.value);
        System.out.print(" ");
    }
    
}

//我醉了，一直过不去是因为在中序和后序里调用了前序的递归方法........



import java.util.*;
public class Main {
    public static void main(String[] args) {
        int n,root;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        root = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n+1];
        for(int i=1; i<=n; i++){
            nodes[i] = new TreeNode(i);
        }
        for(int i=1; i<=n; i++){
            int fa = sc.nextInt();
            int left = sc.nextInt();
            int right = sc.nextInt();
            nodes[fa].left = left == 0?null:nodes[left];
            nodes[fa].right = right == 0?null:nodes[right];
        }
        dfs_one(nodes[root]);
        System.out.println();
        dfs_two(nodes[root]);
        System.out.println();
        dfs_thr(nodes[root]);
    }
        public static void dfs_one(TreeNode root ){
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");
        if(root.left!=null)
            dfs_one(root.left);
        if(root.right!=null)
            dfs_one(root.right);
    }
    public static void dfs_two(TreeNode root){
        if(root==null) {
            return;
        }
        if(root.left!=null)
            dfs_two(root.left);
        System.out.print(root.val+" ");
        if(root.right!=null)
            dfs_two(root.right);
    }
    public static void dfs_thr(TreeNode root){
        if(root==null) {
            return;
        }
        if(root.left!=null)
            dfs_thr(root.left);
        if(root.right!=null)
            dfs_thr(root.right);
        System.out.print(root.val+" ");
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;

public class Main {

    public static class TreeNode {

        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
    
    public static TreeNode treeGenerator(int count, String[][] numbers) {
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(0, null);
        String[] number;
        int value;
        for (int i = 0; i < count; i++) {
            number = numbers[i];
            value = Integer.parseInt(number[0]);
            if (value != 0) {
                map.put(value, new TreeNode(value));
            }
        }
        TreeNode cur;
        for (int i = 0; i < count; i++) {
            number = numbers[i];
            value = Integer.parseInt(number[0]);
            cur = map.get(value);
            cur.left = map.get(Integer.parseInt(number[1]));
            cur.right = map.get(Integer.parseInt(number[2]));
        }
        return map.get(Integer.parseInt(numbers[0][0]));
    }
    
    public static void preOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + " ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    public static void inOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left);
        System.out.print(root.value + " ");
        inOrderRecur(root.right);
    }

    public static void posOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        posOrderRecur(root.left);
        posOrderRecur(root.right);
        System.out.print(root.value + " ");
    }

    public static void preOrderUnRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.print(node.value + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public static void inOrderUnRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node = root.left;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.print(node.value + " ");
                node = node.right;
            }
        }
    }

    public static void posOrderUnRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        TreeNode node;
        while (!stack1.isEmpty()) {
            node = stack1.pop();
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            node = stack2.pop();
            System.out.print(node.value + " ");
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine().split(" ")[0]);
        String[][] numbers = new String[n][3];
        for (int i = 0; i < n; i++) {
            numbers[i] = bufferedReader.readLine().split(" ");
        }
        TreeNode root = treeGenerator(n, numbers);
        preOrderUnRecur(root);
        System.out.println();
        inOrderUnRecur(root);
        System.out.println();
        posOrderUnRecur(root);
    }
}

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    long val;
    TreeNode*left;
    TreeNode*right;
    TreeNode(long v): val(v), left(nullptr), right(nullptr) {}
};

void makeTree(TreeNode* root, long cnt) {
    if (cnt == 0) return;
    long p, l, r;
    cin >> p >> l >> r;
    if (l != 0) {
        TreeNode* left = new TreeNode(l);
        root -> left = left;
        makeTree(left, cnt - 1);
    }
    if (r != 0) {
        TreeNode* right = new TreeNode(r);
        root -> right = right;
        makeTree(right, cnt - 1);
    }
}

void preOrder(TreeNode* root, vector<long> &res) {
    if (root == nullptr) return;
    res.push_back(root -> val);
    preOrder(root->left, res);
    preOrder(root->right, res);
}

void midOrder(TreeNode* root, vector<long> &res) {
    if (root == nullptr) return;
    midOrder(root -> left, res);
    res.push_back(root -> val);
    midOrder(root->right, res);
}

void postOrder(TreeNode* root, vector<long> &res) {
    if (root == nullptr) return;
    postOrder(root -> left, res);
    postOrder(root -> right, res);
    res.push_back(root -> val);
}

int main() {
    long N, first;
    cin >> N >> first;
    TreeNode* root = new TreeNode(first);
    makeTree(root, N);
    vector<long> res;
    preOrder(root, res);
    
    int len = res.size();
    for (int i = 0; i < len; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    res.clear();
    midOrder(root, res);
    len = res.size();
    for (int i = 0; i < len; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    res.clear();
    postOrder(root, res);
    len = res.size();
    for (int i = 0; i < len; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}