一、前序遍历
????????前序遍历是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右
????????前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。
????????若二叉树为空则结束返回，否则：
????????（1）访问根结点。
????????（2）前序遍历左子树。
????????（3）前序遍历右子树 。
? ? ? ? 如图所示，前序遍历的结果为：ABDECFG
?
递归实现：
public class TreeNode {//定义二叉树节点
TreeNode leftnode;
TreeNode rightnode;
String v;
public TreeNode(String v){
this.v=v;
}
//递归前序
public void preOrder(TreeNode root){
if(root != null){
System.out.print(root.v);//打印根节点
preOrder(root.leftnode);//访问左节点
preOrder(root.rightnode);//访问右节点
}
}
}
测试代码，下同
public class Test {
public static void main(String[] args) {
TreeNode n1=new TreeNode("A");
TreeNode n2=new TreeNode("B");
TreeNode n3=new TreeNode("C");
TreeNode n4=new TreeNode("D");
TreeNode n5=new TreeNode("E");
TreeNode n6=new TreeNode("F");
TreeNode n7=new TreeNode("G");
n1.leftnode=n2;
n1.rightnode=n3;
n2.leftnode=n4;
n2.rightnode=n5;
n3.leftnode=n6;
n3.rightnode=n7;
n1.preOrder(n1);
}
}
测试结果：
非递归实现：
????????根节点存入栈中打印根节点，然后访问这个根节点的左子树，左子树也是将左子树的根存入栈中打印根节点，依次往下直到左子树为空，再取出栈顶元素，栈顶元素(访问完左子树的根节点)作为新的根节点去访问右子树。
?
public class TreeNode {//定义二叉树节点
TreeNode leftnode;
TreeNode rightnode;
String v;
public TreeNode(String v){
this.v=v;
}
//非递归前序
public void preOrder(TreeNode root){
Stack<TreeNode> stack =new Stack<>();//定义一个栈用于存放节点
while (root!=null || !stack.isEmpty()){//判断二叉树是否遍历完
while (root!=null){//往左走
stack.push(root);//根节点入栈
System.out.print(root.v);//打印根节点
root=root.leftnode;//访问根节点的左节点
}
root=stack.pop();//取出根节点
root=root.rightnode;//访问根节点的右节点
}
}
}测试结果：
二、中序遍历?
? ? ? ? 中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。可记作左跟右
????????中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
????????若二叉树为空则结束返回，否则：
????????（1）中序遍历左子树
????????（2）访问根结点
????????（3）中序遍历右子树
如图所示，中序遍历的结果为：DBEAFCG
递归实现：
public class TreeNode {//定义二叉树节点
TreeNode leftnode;
TreeNode rightnode;
String v;
public TreeNode(String v){
this.v=v;
}
//递归中序
public void preOrder(TreeNode root){
if(root != null){
preOrder(root.leftnode);//访问左节点
System.out.print(root.v);//打印根节点
preOrder(root.rightnode);//访问右节点
}
}
}?测试结果：
?非递归方式
? ? ? ? 与前序方式基本相同，不同的是不先打印根节点，而是先访问左子树，在打印根节点，在访问右子树。
public class TreeNode {//定义二叉树节点
TreeNode leftnode;
TreeNode rightnode;
String v;
public TreeNode(String v){
this.v=v;
}
//非递归中序
public void preOrder(TreeNode root){
Stack<TreeNode> stack =new Stack<>();//定义一个栈用于存放节点
while (root!=null || !stack.isEmpty()){//判断二叉树是否遍历完
while (root!=null){//往左走
stack.push(root);//根节点入栈
root=root.leftnode;//访问根节点的左节点
}
root=stack.pop();//取出根节点
System.out.print(root.v);//打印根节点
root=root.rightnode;//访问根节点的右节点
}
}
}测试结果：
?
后序遍历
????????后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。??
????????后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，否则：
????????（1）后序遍历左子树
????????（2）后序遍历右子树
????????（3）访问根结点
?如图所示，中序遍历的结果为：DEBFGCA\
?递归方法
public class TreeNode {//定义二叉树节点
TreeNode leftnode;
TreeNode rightnode;
String v;
public TreeNode(String v){
this.v=v;
}
//递归后序
public void preOrder(TreeNode root){
if(root != null){
preOrder(root.leftnode);//访问左节点
preOrder(root.rightnode);//访问右节点
System.out.print(root.v);//打印根节点
}
}
}?测试结果：
非递归方法?
public class TreeNode {//定义二叉树节点
TreeNode leftnode;
TreeNode rightnode;
String v;
public TreeNode(String v){
this.v=v;
}
//非递归后序
public void preOrder(TreeNode root){
Stack<TreeNode> stack =new Stack<>();//定义一个栈用于存放节点
TreeNode node =root;
TreeNode p=null;
while (node!=null || !stack.isEmpty()){//判断二叉树是否遍历完
while (node!=null){//往左走
stack.push(node);//根节点入栈
node=node.leftnode;//访问根节点的左节点
}
node=stack.peek();//判断栈顶元素
if (node.rightnode==null || node.rightnode==p){
node=stack.pop();//打印根节点，并出栈，将打印过的节点从栈中删除
System.out.print(node.v);
p=node;//记录prev，表示以当前prev为根的子树已经访问过了
node=null;//node置null就不会再次访问以node为根节点的左右子树，这里的node既然已经打印，说明它的左右子树早已访问完毕
}else {
node=node.rightnode;//访问右子树
}
}
}
}测试结果：
?