Java实现二叉树先序,中序,后序遍历

发布时间:2017-3-2 3:58:10 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Java实现二叉树先序,中序,后序遍历 ",主要涉及到Java实现二叉树先序,中序,后序遍历 方面的内容,对于Java实现二叉树先序,中序,后序遍历 感兴趣的同学可以参考一下。

以下是我要解析的一个二叉树的模型形状

接下来废话不多直接上代码

一种是用递归的方法,另一种是用堆栈的方法:

首先创建一棵树:

  

public class Node {      private int data;      private Node leftNode;      private Node rightNode;      public Node(int data, Node leftNode, Node rightNode){          this.data = data;          this.leftNode = leftNode;          this.rightNode = rightNode;      }        public int getData() {          return data;      }      public void setData(int data) {          this.data = data;      }      public Node getLeftNode() {          return leftNode;      }      public void setLeftNode(Node leftNode) {          this.leftNode = leftNode;      }      public Node getRightNode() {          return rightNode;      }      public void setRightNode(Node rightNode) {          this.rightNode = rightNode;      }  }  

递归:

public class BinaryTree {      /**      * @author yaobo     * 二叉树的先序中序后序排序      */      public Node init() {//注意必须逆序建立,先建立子节点,再逆序往上建立,因为非叶子结点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错          Node J = new Node(8, null, null);          Node H = new Node(4, null, null);          Node G = new Node(2, null, null);          Node F = new Node(7, null, J);          Node E = new Node(5, H, null);          Node D = new Node(1, null, G);          Node C = new Node(9, F, null);          Node B = new Node(3, D, E);          Node A = new Node(6, B, C);          return A;   //返回根节点      }        public void printNode(Node node){          System.out.print(node.getData());      }      public void theFirstTraversal(Node root) {  //先序遍历          printNode(root);          if (root.getLeftNode() != null) {  //使用递归进行遍历左孩子              theFirstTraversal(root.getLeftNode());          }          if (root.getRightNode() != null) {  //递归遍历右孩子              theFirstTraversal(root.getRightNode());          }      }      public void theInOrderTraversal(Node root) {  //中序遍历          if (root.getLeftNode() != null) {              theInOrderTraversal(root.getLeftNode());          }          printNode(root);          if (root.getRightNode() != null) {              theInOrderTraversal(root.getRightNode());          }      }            public void thePostOrderTraversal(Node root) {  //后序遍历          if (root.getLeftNode() != null) {              thePostOrderTraversal(root.getLeftNode());          }          if(root.getRightNode() != null) {              thePostOrderTraversal(root.getRightNode());          }          printNode(root);      }            public static void main(String[] args) {          BinaryTree tree = new BinaryTree();          Node root = tree.init();          System.out.println("先序遍历");          tree.theFirstTraversal(root);          System.out.println("");          System.out.println("中序遍历");          tree.theInOrderTraversal(root);          System.out.println("");          System.out.println("后序遍历");          tree.thePostOrderTraversal(root);          System.out.println("");      }  }  

堆栈:

 

public class BinaryTree1 {      public Node init() {//注意必须逆序建立,先建立子节点,再逆序往上建立,因为非叶子结点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错              Node J = new Node(8, null, null);              Node H = new Node(4, null, null);              Node G = new Node(2, null, null);              Node F = new Node(7, null, J);              Node E = new Node(5, H, null);              Node D = new Node(1, null, G);              Node C = new Node(9, F, null);              Node B = new Node(3, D, E);              Node A = new Node(6, B, C);              return A;   //返回根节点          }         public void printNode(Node node){          System.out.print(node.getData());      }            public void theFirstTraversal_Stack(Node root) {  //先序遍历          Stack<Node> stack = new Stack<Node>();          Node node = root;          while (node != null || stack.size() > 0) {  //将所有左孩子压栈              if (node != null) {   //压栈之前先访问                  printNode(node);                  stack.push(node);                  node = node.getLeftNode();              } else {                  node = stack.pop();                  node = node.getRightNode();              }          }      }            public void theInOrderTraversal_Stack(Node root) {  //中序遍历          Stack<Node> stack = new Stack<Node>();          Node node = root;          while (node != null || stack.size() > 0) {              if (node != null) {                  stack.push(node);   //直接压栈                  node = node.getLeftNode();              } else {                  node = stack.pop(); //出栈并访问                  printNode(node);                  node = node.getRightNode();             }          }      }            public void thePostOrderTraversal_Stack(Node root) {   //后序遍历          Stack<Node> stack = new Stack<Node>();          Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后序遍历的结果          Node node = root;          while (node != null || stack.size() > 0) {              if (node != null) {                  output.push(node);                  stack.push(node);                                 node = node.getRightNode();              } else {                  node = stack.pop();                               node = node.getLeftNode();            }          }          System.out.println(output.size());        while (output.size() > 0) {                        printNode(output.pop());          }      }        public static void main(String[] args) {          BinaryTree1 tree = new BinaryTree1();          Node root = tree.init();          System.out.println("先序遍历");          tree.theFirstTraversal_Stack(root);          System.out.println("");          System.out.println("中序遍历");          tree.theInOrderTraversal_Stack(root);          System.out.println("");          System.out.println("后序遍历");          tree.thePostOrderTraversal_Stack(root);          System.out.println("");      }

上一篇:Adding List Item Element At Runtime In Oracle Forms
下一篇:匿名类型

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。