第一行输入两个整数 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); inOrder(root); postOrder(root); } private static void preOrder(TreeNode root) { if(root == null) return; TreeNode cur = root; TreeNode mostRight = null; while(cur != null){ mostRight = cur.left; if(mostRight != null){ // 到左子树的最右节点 while(mostRight.right != null && mostRight.right != cur) mostRight = mostRight.right; if(mostRight.right == null){ System.out.print(cur.val + " "); // 第一次到左子树的最右节点,需要将其右孩子的指向指向cur mostRight.right = cur; cur = cur.left; continue; }else{ // 第二次到这要回复右孩子的指针 mostRight.right = null; } }else{ // 只会到一次的节点,直接打印 System.out.print(cur.val + " "); } // 没有左子树节点直接右移 cur = cur.right; } System.out.println(); } private static void inOrder(TreeNode root) { if(root == null) return; TreeNode cur = root; TreeNode mostRight = null; while(cur != null){ mostRight = cur.left; if(mostRight != null){ // 到左子树的最右节点 while(mostRight.right != null && mostRight.right != cur) mostRight = mostRight.right; if(mostRight.right == null){ // 第一次到左子树的最右节点,需要将其右孩子的指向指向cur mostRight.right = cur; cur = cur.left; continue; }else{ System.out.print(cur.val + " "); // 第二次到这要回复右孩子的指针 mostRight.right = null; } }else{ // 只会到一次的节点,直接打印 System.out.print(cur.val + " "); } // 没有左子树节点直接右移 cur = cur.right; } System.out.println(); } private static void postOrder(TreeNode root) { if(root == null) return; TreeNode cur = root; TreeNode mostRight = null; while(cur != null){ mostRight = cur.left; if(mostRight != null){ // 到左子树的最右节点 while(mostRight.right != null && mostRight.right != cur) mostRight = mostRight.right; if(mostRight.right == null){ // 第一次到左子树的最右节点,需要将其右孩子的指向指向cur mostRight.right = cur; cur = cur.left; continue; }else{ // 第二次到这要回复右孩子的指针 mostRight.right = null; printEdge(cur.left); // 逆序打印左树右边界 } } // 没有左子树节点直接右移 cur = cur.right; } // 遍历完成后还需要打印整棵树的右边界 printEdge(root); System.out.println(); } private static void printEdge(TreeNode node) { TreeNode tail = reverseEdge(node); TreeNode cur = tail; while(cur != null){ System.out.print(cur.val + " "); cur = cur.right; } // 逆序打印后还要把指针指向还原回去 reverseEdge(tail); } // 翻转链表操作 private static TreeNode reverseEdge(TreeNode cur) { TreeNode prev = null; TreeNode next = null; while(cur != null){ next = cur.right; cur.right = prev; prev = cur; cur = next; } return prev; } }
import java.util.*; public class Main { private static List<Integer> preOrder = new LinkedList<>(); private static List<Integer> inOrder = new LinkedList<>(); private static List<Integer> postOrder = new LinkedList<>(); public static void order(TreeNode node){ if (node == null) return; preOrder.add(node.value); order(node.left); inOrder.add(node.value); order(node.right); postOrder.add(node.value); } public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt(); int rootVal = in.nextInt(); Map<Integer,TreeNode> map = new HashMap<>(); TreeNode root = new TreeNode(rootVal); map.put(rootVal,root); for (int i=0;i<num;i++){ int n = in.nextInt(); int l = in.nextInt(); int r = in.nextInt(); TreeNode node = map.get(n); if (l > 0){ TreeNode left = new TreeNode(l); node.left = left; map.put(l,left); } if (r > 0){ TreeNode right = new TreeNode(r); node.right = right; map.put(r,right); } } order(root); for (int i: preOrder){ System.out.print(i+" "); } System.out.println(); for (int i: inOrder){ System.out.print(i+" "); } System.out.println(); for (int i: postOrder){ System.out.print(i+" "); } } static class TreeNode{ int value; TreeNode left; TreeNode right; public TreeNode(int value){ this.value = value; } } }
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct TreeNode { ElemType data; struct TreeNode* left; struct TreeNode* right; } TreeNode, *PTreeNode; PTreeNode buildTree(int (*data)[2], int index) { // recursion exit conditon if (!index) return NULL; PTreeNode root = (PTreeNode) malloc(sizeof(TreeNode)); if (!root) return NULL; root->data = index; root->left = buildTree(data, **(data + index)); root->right = buildTree(data, *(*(data + index) + 1)); return root; } void output(PTreeNode node) { fprintf(stdout, "%d ", (*node).data); } // recursively void preorder(PTreeNode root, void (*visit) (PTreeNode)) { if (!root) return; visit(root); preorder(root->left, visit); preorder(root->right, visit); } // iteratively void inorder(PTreeNode root, void (*visit) (PTreeNode)) { PTreeNode stk[(int) 1E6]; int top = 0; PTreeNode p = root, curr; while (top || p) { while (p) { *(stk + top++) = p; p = p->left; } curr = *(stk + --top); visit(curr); p = curr->right; } } // recursively void postorder(PTreeNode root, void (*visit) (PTreeNode)) { if (!root) return; postorder(root->left, visit); postorder(root->right, visit); visit(root); } int main(const int argc, const char* const argv[]) { int n, root; fscanf(stdin, "%d %d", &n, &root); int data[n + 1][2]; int fa, lch, rch; while (n--) { fscanf(stdin, "%d %d %d", &fa, &lch, &rch); **(data + fa) = lch; *(*(data + fa) + 1) = rch; } PTreeNode pRoot = buildTree(data, root); preorder(pRoot, output); fputc(10, stdout); inorder(pRoot, output); fputc(10, stdout); postorder(pRoot, output); return 0; }
let [n,root]=readline().split(' ').map(item=>parseInt(item)) let myMap=new Map() while(n--){ let [fa,lch,rch]=readline().split(' ').map(item=>parseInt(item)) myMap.set(fa,[lch,rch]) } const listNode=function(val){ this.val=val this.left=null this.right=null } const createTree=function(root){ if(root){ let [lch,rch]=myMap.get(root) let node=new listNode(root) node.left=createTree(lch) node.right=createTree(rch) return node } } const treeHead=createTree(root) let res=[] //morris顺序 const morris=function(root){ if(root==null)return ; let cur=root; let mostRight=null; while(cur!=null){ mostRight=cur.left if(mostRight!=null){ //有左子树 while(mostRight.right!=null&& mostRight.right!=cur){ //找左子树的最右节点 mostRight=mostRight.right } //左子树的最右节点第一次被找到 指向根节点 if(mostRight.right==null){ mostRight.right=cur res.push(cur.val) cur=cur.left continue }else{ //左子树的最右节点第二次被找到 res.push(cur.val) mostRight.right=null } }else{ res.push(cur.val) } cur=cur.right } } morris(treeHead) // console.log(res.join(' ')) res=[] //morris顺序 先序 const premorris=function(root){ if(root==null)return ; let cur=root; let mostRight=null; while(cur!=null){ mostRight=cur.left if(mostRight!=null){ //有左子树 while(mostRight.right!=null&& mostRight.right!=cur){ //找左子树的最右节点 mostRight=mostRight.right } //左子树的最右节点第一次被找到 指向根节点 if(mostRight.right==null){ mostRight.right=cur res.push(cur.val) cur=cur.left continue }else{ //左子树的最右节点第二次被找到 mostRight.right=null } } //没有左子树 else{ res.push(cur.val) } cur=cur.right } } premorris(treeHead) console.log(res.join(' ')) res=[] //morris顺序 中序 const inmorris=function(root){ if(root==null)return ; let cur=root; let mostRight=null; while(cur!=null){ mostRight=cur.left if(mostRight!=null){ //有左子树 while(mostRight.right!=null&& mostRight.right!=cur){ //找左子树的最右节点 mostRight=mostRight.right } //左子树的最右节点第一次被找到 指向根节点 if(mostRight.right==null){ mostRight.right=cur cur=cur.left continue }else{ //左子树的最右节点第二次被找到 // res.push(cur.val) mostRight.right=null } }//没有左子树 res.push(cur.val) cur=cur.right } } inmorris(treeHead) console.log(res.join(' ')) res=[] const reverseedg=function(from){ let pre=null let next = null while(from!=null){ next=from.right from.right=pre pre=from from=next } return pre } const printegd=function(root){ let tail=reverseedg(root) let cur=tail while(cur!=null){ res.push(cur.val) cur=cur.right } //把树的链表复原 reverseedg(tail) } const bemorris=function(root){ if(root==null)return ; let cur=root; let mostRight=null; while(cur!=null){ mostRight=cur.left if(mostRight!=null){ //有左子树 while(mostRight.right!=null&& mostRight.right!=cur){ //找左子树的最右节点 mostRight=mostRight.right } //左子树的最右节点第一次被找到 指向根节点 if(mostRight.right==null){ mostRight.right=cur cur=cur.left continue }else{ //左子树的最右节点第二次被找到 mostRight.right=null //打印左子树的右边界 printegd(cur.left) } }//没有左子树 cur=cur.right } printegd(root) } bemorris(treeHead) console.log(res.join(' '))
#include <iostream> using namespace std; struct TreeNode{ int val; TreeNode* lptr; TreeNode* rptr; TreeNode(int fa) :val(fa), lptr(nullptr), rptr(nullptr) {} }; TreeNode* createTree(){ int fa, lch, rch; cin >> fa >> lch >> rch; TreeNode *head = new TreeNode(fa); if(lch != 0) head->lptr = createTree(); if(rch != 0) head->rptr = createTree(); return head; } void deleteTree(TreeNode* root){ if(root == nullptr) return; if(root->lptr != nullptr) deleteTree(root->lptr); if(root->rptr != nullptr) deleteTree(root->rptr); delete root; } //morris前序遍历 void morrisPre(TreeNode* root){ if(root == nullptr) return; TreeNode* cur = root; TreeNode* mostRight = nullptr; while(cur != nullptr){ mostRight = cur->lptr; if(mostRight != nullptr){ while(mostRight->rptr != nullptr && mostRight->rptr != cur) mostRight = mostRight->rptr; if(mostRight->rptr == nullptr){ mostRight->rptr = cur; cout << cur->val << " "; cur = cur->lptr; continue; } else{ mostRight->rptr = nullptr; } }else{ cout << cur->val << " "; } cur = cur->rptr; } cout << endl; } //morris中序遍历 void morrisIn(TreeNode* root){ TreeNode* cur = root; TreeNode* mostRight = nullptr; while(cur != nullptr){ mostRight = cur->lptr; if(mostRight != nullptr){ while(mostRight->rptr != nullptr && mostRight->rptr != cur) mostRight = mostRight->rptr; if(mostRight->rptr == nullptr){ mostRight->rptr = cur; cur = cur->lptr; continue; } else{ mostRight->rptr = nullptr; } } cout << cur->val << " "; cur = cur->rptr; } cout << endl; } TreeNode* reverse(TreeNode* head){ if(head == nullptr) return nullptr; TreeNode* pre = nullptr; TreeNode* cur = head; TreeNode* next = nullptr; while(cur != nullptr){ next = cur->rptr; cur->rptr = pre; pre = cur; cur = next; } return pre; } void print(TreeNode* head){ TreeNode* reverseHead = reverse(head); TreeNode* cur = reverseHead; while(cur != nullptr){ cout << cur->val << " "; cur = cur->rptr; } reverse(reverseHead); } void morrisPost(TreeNode *root){ TreeNode *cur = root; TreeNode *mostRight = nullptr; while(cur != nullptr){ mostRight = cur->lptr; if(mostRight != nullptr){ while(mostRight->rptr != nullptr && mostRight->rptr != cur) mostRight = mostRight->rptr; if(mostRight->rptr == nullptr){ mostRight->rptr = cur; cur = cur->lptr; continue; }else{ mostRight->rptr = nullptr; print(cur->lptr); } } cur = cur->rptr; } print(root); cout << endl; } int main(void){ int n, rootVal; cin >> n >> rootVal; TreeNode* root = createTree(); morrisPre(root); morrisIn(root); morrisPost(root); deleteTree(root); return 0; }使用morris遍历方法解决了所有问题
看到递归和Morris版都有了,再加一种使用stack的非递归版
#include <iostream> #include <vector> #include <stack> const std::vector<int> preorder(const std::vector<int> &lefts, std::vector<int> &rights, const int root){ using namespace std; vector<int> res; stack<int> s; s.push(root); while(s.size()){ int current = s.top(); s.pop(); res.push_back(current); int left, right; if(right = rights[current]){ s.push(right); } if(left = lefts[current]){ s.push(left); } } return std::move(res); } const std::vector<int> inorder(const std::vector<int> &lefts, std::vector<int> &rights, const int root){ using namespace std; vector<int> res; stack<int> s; int current = root; while(current || s.size()){ if(current){ s.push(current); current = lefts[current]; }else{ current = s.top(); s.pop(); res.push_back(current); current = rights[current]; } } return std::move(res); } const std::vector<int> postorder_r(const std::vector<int> &lefts, std::vector<int> &rights, const int root){ using namespace std; vector<int> res; stack<int> s; s.push(root); while(s.size()){ int current = s.top(), left, right; s.pop(); res.push_back(current); if(left = lefts[current]){ s.push(left); } if(right = rights[current]){ s.push(right); } } return std::move(res); } int main(){ using namespace std; int n, root; cin >> n >> root; vector<int> lefts(n + 1), rights(n + 1); for(int i = 0; i<n; ++i){ int fa, lch, rch; cin >> fa >> lch >> rch; lefts[fa] = lch; rights[fa] = rch; } //先序 for(int v : preorder(lefts, rights, root)){ cout << v << ' '; } cout << endl; //中序 for(int v : inorder(lefts, rights, root)){ cout << v << ' '; } cout << endl; //后序 auto postorder_res(std::move(postorder_r(lefts, rights, root))); for(auto iter = postorder_res.rbegin(); iter != postorder_res.rend(); ++iter){ cout << (*iter) << ' '; } cout << endl; return 0; }
#include<bits/stdc++.h> using namespace std; void morrisPre(int root,int* lc,int* rc,vector<int>& ans) { if(!root) return; int cur = root; int mostRight = 0; while(cur) { mostRight = lc[cur]; // 有左子树 if(mostRight) { // 找左子树的右边界结点 while(rc[mostRight] && rc[mostRight] != cur) mostRight = rc[mostRight]; // 如果最右结点的右指针为null if(!rc[mostRight]) { // 将它指向当前结点 rc[mostRight] = cur; // 有左子树的结点可以两次到达,在第一次到达时访问 ans.push_back(cur); cur = lc[cur]; continue; }else{ // 若已经指向当前结点 则置空 rc[mostRight] = 0; } }else{ // 只能到达一次的结点直接访问即可 ans.push_back(cur); } cur = rc[cur]; } } void morrisIn(int root,int* lc,int*rc,vector<int>& ans) { if(!root) return; int cur = root; int mostRight = 0; while(cur) { mostRight = lc[cur]; if(mostRight) { while(rc[mostRight] && rc[mostRight]!=cur) mostRight = rc[mostRight]; if(!rc[mostRight]) { rc[mostRight] = cur; cur = lc[cur]; continue; } else{ rc[mostRight]=0; } } // 能到达两次的,在第二次到达时访问 ans.push_back(cur); cur = rc[cur]; } } int reverse(int root,int* lc,int* rc) { int pre = 0; int next = 0; while(root) { next = rc[root]; rc[root] = pre; pre = root; root = next; } return pre; } void printEdge(int root,int* lc,int* rc,vector<int>& ans) { int tail = reverse(root,lc,rc); int cur = tail; while(cur) { ans.push_back(cur); cur = rc[cur]; } // 复原 reverse(tail,lc,rc); } void morrisPost(int root,int* lc,int* rc,vector<int>& ans) { if(!root) return; int cur = root; int mostRight = 0; while(cur) { mostRight = lc[cur]; if(mostRight) { while(rc[mostRight] && rc[mostRight]!=cur) mostRight = rc[mostRight]; // 第一次到达 if(!rc[mostRight]) { rc[mostRight] = cur; cur = lc[cur]; continue; } // 第二次到达 else{ rc[mostRight]=0; printEdge(lc[cur],lc,rc,ans); } } cur = rc[cur]; } printEdge(root,lc,rc,ans); } void print(vector<int>&ans) { for(int i:ans) cout<<i<<" "; cout<<endl; ans.clear(); } int main() { int n,root; cin>>n>>root; int* lc = new int[n+1]; int* rc = new int[n+1]; int p; for(int i=0;i<n;++i) { cin>>p; cin>>lc[p]>>rc[p]; } vector<int>ans; morrisPre(root,lc,rc,ans); print(ans); morrisIn(root,lc,rc,ans); print(ans); morrisPost(root,lc,rc,ans); print(ans); return 0; }