第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
输出三行,分别表示二叉树的先序,中序和后序。
3 1 1 2 3 2 0 0 3 0 0
1 2 3 2 1 3 2 3 1
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; class TreeNode { public int val; public TreeNode left; public 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[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); TreeNode root = new TreeNode(Integer.parseInt(params[1])); HashMap<Integer, TreeNode> map = new HashMap<>(); map.put(root.val, root); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int val = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(val); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } // 三种遍历 preOrder(root); System.out.println(); inOrder(root); System.out.println(); postOrder(root); } private static void preOrder(TreeNode node) { if(node == null) return; System.out.print(node.val + " "); preOrder(node.left); preOrder(node.right); } private static void inOrder(TreeNode node) { if(node == null) return; inOrder(node.left); System.out.print(node.val + " "); inOrder(node.right); } private static void postOrder(TreeNode node) { if(node == null) return; postOrder(node.left); postOrder(node.right); System.out.print(node.val + " "); } }迭代版遍历
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; import java.util.Stack; class TreeNode { public int val; public TreeNode left; public 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[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); TreeNode root = new TreeNode(Integer.parseInt(params[1])); HashMap<Integer, TreeNode> map = new HashMap<>(); map.put(root.val, root); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int val = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(val); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } // 三种遍历 preOrder(root); inOrder(root); postOrder(root); } private static void preOrder(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); System.out.print(node.val + " "); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } System.out.println(); } private static void inOrder(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); while(!stack.isEmpty() || root != null){ // 先从左边走到头 while(root != null) { stack.push(root); root = root.left; } // 然后右子树进行相同的操作 if(!stack.isEmpty()){ root = stack.pop(); System.out.print(root.val + " "); root = root.right; } } System.out.println(); } private static void postOrder(TreeNode root) { Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(root); while(!stack1.isEmpty()){ TreeNode 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()) System.out.print(stack2.pop().val + " "); System.out.println(); } }
#include <bits/stdc++.h> using namespace std; // 树节点结构 struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(): val(0), left(nullptr), right(nullptr) {} TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; // 建树 void bulidTree(TreeNode* root, int cnt){ if(!cnt) return; if(root == nullptr) return; int cur, l, r; cin >> cur >> l >> r; if(l){ TreeNode* left = new TreeNode(l); root->left = left; bulidTree(root->left, cnt - 1); } if(r){ TreeNode* right = new TreeNode(r); root->right = right; bulidTree(root->right, cnt - 1); } } // 前序递归 void perOrder(TreeNode* root, vector<int>& result){ if(root == nullptr) return ; result.push_back(root->val); perOrder(root->left, result); perOrder(root->right, result); } // 中序递归 void midOrder(TreeNode* root, vector<int>& result){ if(root == nullptr) return ; midOrder(root->left, result); result.push_back(root->val); midOrder(root->right, result); } // 后序递归 void lastOrder(TreeNode* root, vector<int>& result){ if(root == nullptr) return; lastOrder(root->left, result); lastOrder(root->right, result); result.push_back(root->val); } // 前序非递归 void perOrder2(TreeNode* root, vector<int>& result){ stack<TreeNode*> st; if(root) st.push(root); while(!st.empty()){ auto cur = st.top(); if(cur != nullptr){ st.pop(); if(cur->right) st.push(cur->right); if(cur->left) st.push(cur->left); st.push(cur); st.push(nullptr); } else { st.pop(); auto cur = st.top(); st.pop(); result.push_back(cur->val); } } } // 中序非递归 void midOrder2(TreeNode* root, vector<int>& result){ stack<TreeNode*> st; if(root) st.push(root); while(!st.empty()){ auto cur = st.top(); if(cur != nullptr){ st.pop(); if(cur->right) st.push(cur->right); st.push(cur); st.push(nullptr); if(cur->left) st.push(cur->left); } else { st.pop(); auto cur = st.top(); st.pop(); result.push_back(cur->val); } } } // 后序非递归 void lastOrder2(TreeNode* root, vector<int>& result){ stack<TreeNode*> st; if(root) st.push(root); while(!st.empty()){ auto cur = st.top(); if(cur != nullptr){ st.pop(); st.push(cur); st.push(nullptr); if(cur->right) st.push(cur->right); if(cur->left) st.push(cur->left); } else { st.pop(); auto cur =st.top(); st.pop(); result.push_back(cur->val); } } } int main() { int n, val; cin >> n >> val; TreeNode* root = new TreeNode(val); bulidTree(root, n); vector<int> result; perOrder2(root, result); for(auto &c : result) cout << c << " "; cout << endl; result.clear(); midOrder2(root, result); for(auto &c : result) cout << c << " "; cout << endl; result.clear(); lastOrder2(root, result); for(auto &c : result) cout << c << " "; cout << endl; return 0; }
#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 + " "); } } }
#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; }
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; }