算法:二叉树的先(根)序遍历、中(根)序遍历、后(根)序遍历(递归及压栈出栈实现的非递归方式)的java代码实现

2021年9月30日 7点热度 0条评论 来源: 兜兜里o全是糖

 首先来看一棵二叉树:

1、前(根)序遍历,也叫先序遍历:

前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问
根结点,然后遍历左子树,最后遍历右子树。 若
二叉树为空则结束返回,否则: (1)访问根结点; (2)前序遍历左子树; (3)前序遍历右子树 ; 需要注意的是:遍历左右子树时仍然采用前序遍历方法。可以看出前序遍历后,遍历结果为:631254978
2、中(根)序遍历: 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。即: 若
二叉树为空则结束返回,
否则: (1)中序遍历左子树; (2)访问根结点;

(3)中序遍历右子树; 注意的是:遍历左右子树时仍然采用中序遍历方法。最上图的二叉树用中序遍历的结果是:123456789
3、后(根)遍历: 后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。即: 若
二叉树为空则结束返回,
否则: (1)后序遍历左子树; (2)后序遍历右子树; (3)访问根结点; 如图所示的二叉树,用后序遍历的结果是:214538796

三种遍历的递归实现:
[java] 
view plain
 copy

  1. public class Node { //二叉树节点  
  2.       
  3.     private int data;  
  4.     private Node leftNode;  
  5.     private Node rightNode;  
  6.       
  7.     public Node(int data, Node leftNode, Node rightNode){  
  8.         this.data = data;  
  9.         this.leftNode = leftNode;  
  10.         this.rightNode = rightNode;  
  11.     }  
  12.       
  13.     public int getData(){  
  14.         return data;  
  15.     }  
  16.       
  17.     public void setData(int data){  
  18.         this.data = data;  
  19.     }  
  20.       
  21.     public Node getLeftNode(){  
  22.         return leftNode;  
  23.     }  
  24.       
  25.     public void setLeftNode(Node leftNode){  
  26.         this.leftNode = leftNode;  
  27.     }  
  28.       
  29.     public Node getRightNode(){  
  30.         return rightNode;  
  31.     }  
  32.       
  33.     public void setRightNode(Node rightNode){  
  34.         this.rightNode = rightNode;  
  35.     }  
  36.       
  37. }  

三种遍历的递归实现:
[java] 
view plain
 copy

  1. public class BinaryTree_DiGui {  
  2.       
  3.     /* 
  4.      * 二叉树先序中序后序排序 
  5.      * 方式:递归。 
  6.      */  
  7.       
  8.     //注意必须逆序简历,先建立子节点,再逆序往上建立,  
  9.     //因为非叶子节点会使用到下面的节点,而初始化是按顺序初始化得,不逆序建立会报错  
  10.     public static Node init(){  
  11.         Node J = new Node(8nullnull);  
  12.         Node H = new Node(4nullnull);  
  13.         Node G = new Node(2nullnull);  
  14.         Node F = new Node(7null, J);  
  15.         Node E = new Node(5, H, null);  
  16.         Node D = new Node(1null, G);  
  17.         Node C = new Node(9, F, null);  
  18.         Node B = new Node(3, D, E);  
  19.         Node A = new Node(6, B, C);  
  20.         return A;  //返回根节点  
  21.     }  
  22.       
  23.     //打印节点数值  
  24.     public static void printNode(Node node){  
  25.         System.out.print(node.getData());  
  26.     }  
  27.       
  28.       
  29.     //先序遍历  
  30.     public static void preOrder(Node root){  
  31.           
  32.         printNode(root);//打印根节点  
  33.           
  34.         if(root.getLeftNode() != null){ //使用递归遍历左孩子  
  35.             preOrder(root.getLeftNode());  
  36.         }  
  37.         if(root.getRightNode() != null){ //使用递归遍历右孩子  
  38.             preOrder(root.getRightNode());  
  39.         }  
  40.     }  
  41.       
  42.       
  43.     //中序遍历  
  44.     public static void inOrder(Node root){  
  45.           
  46.         if(root.getLeftNode() != null){ //使用递归遍历左孩子  
  47.             inOrder(root.getLeftNode());  
  48.         }  
  49.           
  50.         printNode(root);//打印根节点  
  51.           
  52.         if(root.getRightNode() != null){ //使用递归遍历右孩子  
  53.             inOrder(root.getRightNode());  
  54.         }  
  55.     }  
  56.       
  57.       
  58.     //后续遍历  
  59.     public static void postOrder(Node root){  
  60.           
  61.         if(root.getLeftNode() != null){ //使用递归遍历左孩子  
  62.             postOrder(root.getLeftNode());  
  63.         }  
  64.           
  65.         if(root.getRightNode() != null){ //使用递归遍历右孩子  
  66.             postOrder(root.getRightNode());  
  67.         }  
  68.           
  69.         printNode(root);//打印根节点  
  70.     }  
  71.       
  72.       
  73.     public static void main(String[] args){  
  74. //      BinaryTree tree = new BinaryTree();//注释掉本行后类中方法需变为static  
  75.         Node root = init();  
  76.           
  77.         System.out.println("先序遍历");  
  78.         preOrder(root);  
  79.         System.out.println("");  
  80.           
  81.         System.out.println("中序遍历");  
  82.         inOrder(root);  
  83.         System.out.println("");  
  84.           
  85.         System.out.println("后序遍历");  
  86.         postOrder(root);  
  87.         System.out.println("");  
  88.           
  89.     }  
  90.       
  91. }  

通过栈实现三种遍历(非递归):
[java] 
view plain
 copy

  1. public class BinaryTree_Zhan {  
  2.       
  3.     /* 
  4.      *  
  5.      * 二叉树先序中序后序排序 
  6.      * 方式:采用非递归方式。 
  7.      */  
  8.       
  9.     //注意必须逆序简历,先建立子节点,再逆序往上建立,  
  10.     //因为非叶子节点会使用到下面的节点,而初始化是按顺序初始化得,不逆序建立会报错  
  11.     public static Node init(){  
  12.         Node J = new Node(8nullnull);  
  13.         Node H = new Node(4nullnull);  
  14.         Node G = new Node(2nullnull);  
  15.         Node F = new Node(7null, J);  
  16.         Node E = new Node(5, H, null);  
  17.         Node D = new Node(1null, G);  
  18.         Node C = new Node(9, F, null);  
  19.         Node B = new Node(3, D, E);  
  20.         Node A = new Node(6, B, C);  
  21.         return A;  //返回根节点  
  22.     }  
  23.       
  24.     //打印节点数值  
  25.     public static void printNode(Node node){  
  26.         System.out.print(node.getData());  
  27.     }  
  28.       
  29.       
  30.     public static void preOrder_stack(Node root){ //先序遍历  
  31.           
  32.         Stack<Node> stack = new Stack<Node>();  
  33.         Node node = root;  
  34.           
  35.         while(node != null || stack.size()>0){ //将所有左孩子压栈  
  36.             if(node != null){ //压栈之前先访问  
  37.                 printNode(node);  
  38.                 stack.push(node);  
  39.                 node = node.getLeftNode();  
  40.                   
  41.             }else{  
  42.                 node = stack.pop();  
  43.                 node = node.getRightNode();  
  44.             }  
  45.         }  
  46.     }  
  47.       
  48.       
  49.     public static void inOrder_Stack(Node root){ //中序遍历  
  50.           
  51.         Stack<Node> stack = new Stack<Node>();  
  52.         Node node = root;  
  53.           
  54.         while(node != null || stack.size()>0){  
  55.             if(node != null){  
  56.                 stack.push(node);//直接压栈  
  57.                 node = node.getLeftNode();  
  58.             }else{  
  59.                 node = stack.pop();//出栈并访问  
  60.                 printNode(node);  
  61.                 node = node.getRightNode();  
  62.             }  
  63.         }  
  64.     }  
  65.       
  66.       
  67.     public static void postOrder_Stack(Node root){ //后续遍历  
  68.           
  69.         Stack<Node> stack = new Stack<Node>();  
  70.         Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后续遍历的结果  
  71.         Node node = root;  
  72.         while(node != null || stack.size()>0){  
  73.             if(node != null){  
  74.                 output.push(node);  
  75.                 stack.push(node);  
  76.                 node = node.getRightNode();  
  77.             }else{  
  78.                 node = stack.pop();  
  79.                 node = node.getLeftNode();  
  80.             }  
  81.         }  
  82.           
  83.         while(output.size()>0){  
  84.             printNode(output.pop());  
  85.         }  
  86.           
  87.     }  
  88.       
  89.       
  90.     public static void main(String[] args){  
  91.           
  92.         Node root = init();  
  93.           
  94.         System.out.println("先序遍历");  
  95.         preOrder_stack(root);  
  96.         System.out.println("");  
  97.           
  98.         System.out.println("中序遍历");  
  99.         inOrder_Stack(root);   
  100.         System.out.println("");  
  101.           
  102.         System.out.println("后序遍历");  
  103.         postOrder_Stack(root);  
  104.         System.out.println("");  
  105.     }  
  106.   
  107. }  
    原文作者:兜兜里o全是糖
    原文地址: https://blog.csdn.net/zilaike/article/details/79096548
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。