一、概念
二叉树遍历分为三种：前序、中序、后序，其中序遍历最为重要。
二、特点
a：根节点、b：左节点、c：右节点;
- 前序顺序是abc（根节点排最先，然后同级先左后右）；
- 中序顺序是bac (先左后根最后右）；
- 后序顺序是bca（先左后右最后根）。
三、图
四、代码实现
递归方式
第一步: 节点实体类
package node.tree;
public class node {
private string value;
private node left;
private node right;
public string getvalue() {
return value;
}
public void setvalue(string value) {
this.value = value;
}
public node getleft() {
return left;
}
public void setleft(node left) {
this.left = left;
}
public node getright() {
return right;
}
public void setright(node right) {
this.right = right;
}
public node(string value, node left, node right) {
this.value = value;
this.left = left;
this.right = right;
}
@override
public string tostring() {
return "node{"
"value='" value '\''
", left=" left
", right=" right
'}';
}
}
二：节点数和核心处理类
package node.tree;
import java.util.arraylist;
import java.util.list;
public class tree {
private node root;
private list result=new arraylist();
public node getroot() {
return root;
}
public void setroot(node root) {
this.root = root;
}
public list getresult() {
return result;
}
public void setresult(list result) {
this.result = result;
}
public tree(){
init();
}
private void init() {
node g=new node("g",null,null);
node x=new node("x",null,null);
node y=new node("y",null,null);
node d=new node("d",x,y);
node b=new node("b",d,null);
node e=new node("e",g,null);
node f=new node("f",null,null);
node c=new node("c",e,f);
node a=new node("a",b,c);
root=a;
}
/**
* 计算深度
* @param node
* @return
*/
public int caldepth(node node){
if (node.getleft()==null&&node.getright()==null){
return 1;
}
int leftdepth=0;
int rightdepth=0;
if(node.getleft()!=null){
leftdepth=caldepth(node.getleft());
}
if(node.getright()!=null){
rightdepth=caldepth(node.getright());
}
system.out.println("左" leftdepth "右" rightdepth);
int temp=leftdepth>rightdepth?leftdepth 1:rightdepth 1;
system.out.println("中间计算结果" temp);
return temp;
}
//前序遍历 根左右
public void perorder(node root){
if(root==null){
return;
}
result.add(root);
if(root.getleft()!=null){
perorder(root.getleft());
}
if(root.getright()!=null){
perorder(root.getright());
}
}
//中序遍历 左根右
public void inmiddleorder(node root){
if(root==null){
return;
}
if(root.getleft()!=null){
inmiddleorder(root.getleft());
}
result.add(root);
if(root.getright()!=null){
inmiddleorder(root.getright());
}
}
//后序遍历 左右根
public void lastorder(node root){
if(root==null){
return;
}
if(root.getleft()!=null){
lastorder(root.getleft());
}
if(root.getright()!=null){
lastorder(root.getright());
}
result.add(root);
}
}
三：测试类
package node.tree;
public class test {
public static void main(string[] args) {
tree tree=new tree();
system.out.println("根节点" tree.getroot().getvalue());
//先序遍历
tree.perorder(tree.getroot());
system.out.println("树的深度是" tree.caldepth(tree.getroot()));
system.out.println("先序遍历结果是：");
for (node node :tree.getresult() ) {
system.out.print(node.getvalue() " ");
}
system.out.println("");
tree.getresult().clear();
tree.inmiddleorder(tree.getroot());
system.out.println("中序遍历结果是：");
for (node node :tree.getresult() ) {
system.out.print(node.getvalue() " ");
}
system.out.println("");
tree.getresult().clear();
tree.lastorder(tree.getroot());
system.out.println("后序遍历结果是：");
for (node node :tree.getresult() ) {
system.out.print(node.getvalue() " ");
}
}
}
非递归方式实现
前序遍历：
public static class node {
public int value;
public node left;
public node right;
public node(int v) {
value = v;
}
}
// object peek( )
// 查看堆栈顶部的对象，但不从堆栈中移除它。
// object pop( )
// 移除堆栈顶部的对象，并作为此函数的值返回该对象。
// object push(object element)
// 把项压入堆栈顶部。
// 先头节点，先压右，后压左
public static void pre(node head) {
// 压栈
system.out.print("pre-order: ");
if (head != null) {
stack stack = new stack();
stack.add(head);
while (!stack.isempty()) {
// 弹出来
head = stack.pop();
system.out.print(head.value " ");
if (head.right != null) {
// 压右
stack.push(head.right);
}
if (head.left != null) {
// 压右
stack.push(head.left);
}
}
}
system.out.println();
}
后序遍历方式：
public static void pos1(node head) {
system.out.print("pos-order: ");
if (head != null) {
stack s1 = new stack();
stack s2 = new stack();
s1.push(head);
while (!s1.isempty()) {
head = s1.pop(); // 头 右 左
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
// 左 右 头
while (!s2.isempty()) {
system.out.print(s2.pop().value " ");
}
}
system.out.println();
}
这里后序遍历其实跟前序遍历是一样的，前序遍历是根，左，右。后序是根，右，左。
其实只需要再加一个栈来区别他是左边的还是右边的就好。
中序遍历方式：
public static void in(node cur) {
system.out.print("in-order: ");
if (cur != null) {
stack stack = new stack();
while (!stack.isempty() || cur != null) {
if (cur != null) {
// head整条左边树进栈，除去空的情况
stack.push(cur);
cur = cur.left;
} else {
// 右节点为空的时候弹出打印
// 从栈中弹出节点打印，这个节点的右孩子为cur
cur = stack.pop();
system.out.print(cur.value " ");
cur = cur.right;
}
}
}
system.out.println();
}
中序先将左树全部进栈，右节点为空的时候就弹出，在把当前节点给到他的左父节点。
后序遍历的话其实也可以用一个栈来实现：
// 一个栈实现
public static void pos2(node h) {
system.out.print("pos-order: ");
if (h != null) {
stack stack = new stack();
stack.push(h);
node c = null;
while (!stack.isempty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
system.out.print(stack.pop().value " ");
h = c;
}
}
}
system.out.println();
}
public static void main(string[] args) {
node head = new node(1);
head.left = new node(2);
head.right = new node(3);
head.left.left = new node(4);
head.left.right = new node(5);
head.right.left = new node(6);
head.right.right = new node(7);
pre(head);
system.out.println("========");
in(head);
system.out.println("========");
pos1(head);
system.out.println("========");
pos2(head);
system.out.println("========");
}