首页 > 代码库 > 二叉树的遍历(递归、非递归)
二叉树的遍历(递归、非递归)
理论：
1．先（根）序遍历的递归定义：
若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
2．中（根）序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵访问根结点；
⑶遍历右子树。
3．后（根）序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点
java实现
package 二叉树;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Stack;public class BSTree { private List<Node>nodeList=new ArrayList<Node>(); public Node CreateTree(int[] a){ for(int data:a) nodeList.add(new Node(data)); int lastLeftRoot=a.length/2-1; for(int i=lastLeftRoot; i>=0; i--) { Node root=nodeList.get(i); int leftIndex=i*2+1; int rightIndex=leftIndex+1; if(leftIndex<a.length); { Node left=nodeList.get(leftIndex); root.setLeft(left); } if(rightIndex<a.length) { Node right=nodeList.get(rightIndex); root.setRgiht(right); } } Node root=nodeList.get(0); return root; } public static void printNode(Node node){ System.out.print(node.getData()+" "); } public static void preOrderStack(Node node){ Stack<Node> stack=new Stack<Node>(); Node p=node; if(node!=null) { stack.push(p); while(!stack.isEmpty()) { Node top=stack.pop(); printNode(top); if(top.getRight()!=null) stack.push(top.getRight()); if(top.getLeft()!=null) stack.push(top.getLeft()); } } } public static void minOrderStack(Node node){ Stack<Node> stack=new Stack<Node>(); Node p=node; while(p!=null ||!stack.isEmpty()) { while(p!=null) { stack.push(p); p=p.getLeft(); } if(!stack.isEmpty()) { p=stack.pop(); printNode(p); p=p.getRight(); } } } public static void postOrderStack(Node node){ Stack<Node> stack=new Stack<Node>(); Node p=node; Node q=p; while(p!=null) { while(p.getLeft()!=null) { stack.push(p); p=p.getLeft(); } while(p!=null&&(p.getRight()==null||p.getRight()==q)) { printNode(p); q=p; if(stack.isEmpty())return; p=stack.pop(); } stack.push(p); p=p.getRight(); } } public static void preTrav(Node node){ if(node==null) return; System.out.print(node.getData()+" "); preTrav(node.getLeft()); preTrav(node.getRight()); } public static void midTrav(Node node){ if(node==null) return; midTrav(node.getLeft()); System.out.print(node.getData()+" "); midTrav(node.getRight()); } public static void postTrav(Node node){ if(node==null) return; postTrav(node.getLeft()); postTrav(node.getRight()); System.out.print(node.getData()+" "); }public static void main(String[] args) { // TODO Auto-generated method stub int[] a={10,6,14,4,8,12,16};//这些数据是按二叉查找树的层次遍历存放 BSTree bt=new BSTree(); Node root=bt.CreateTree(a); preTrav(root); System.out.println(); preOrderStack(root); System.out.println(); midTrav(root); System.out.println(); minOrderStack(root); System.out.println(); postTrav(root); System.out.println(); postOrderStack(root); System.out.println(); }}
二叉树的遍历(递归、非递归)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。