二叉树的遍历（递归与队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Node {
	Object Value;	//结点值
	Node leftChild; //左子树的引用
	Node rightChild;//右子树的引用
	public Node(Object value, Node leftChild, Node rightChild) {
		super();
		Value = value;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}
	public Node(Object value) {
		super();
		Value = value;
	}
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
public class BinaryTree {

	private Node node;

	public BinaryTree(Node node) {
		super();
		this.node = node;
	}

	public BinaryTree() {
		super();
	}
	//判断是否为空
	public boolean isEmpty(){
		if (node !=null) {
			return true;
		}
		return false;
	}
	//先序遍历递归
	public void preOrder(){
		if (node !=null) {
			//打印根结点
			System.out.print(node.Value+"   ");
			//对左子树进行先序遍历
			//构建一个二叉树，根是左子树的根
			BinaryTree leftTree = new BinaryTree(node.leftChild);
			leftTree.preOrder();
			//对右子树进行先序遍历
			//构建一个二叉树，根是左子树的根
			BinaryTree rightTree = new BinaryTree(node.rightChild);
			rightTree.preOrder();
		
		}

	}
	//中序遍历
	public void inOrderTraverse(){
		System.out.println("中序遍历");
		this.inOrderTraverse(node);
		System.out.println("");
		
		
	}
	//中序遍历
	private void inOrderTraverse(Node node){
		if (node !=null) {
		//构建一个二叉树，根是左子树的根
		this.inOrderTraverse(node.leftChild);
		//打印根结点的值 
		System.out.print(node.Value+"   ");
		//构建一个二叉树，根是左子树的根
		this.inOrderTraverse(node.rightChild);
		}
	}
	//后序遍历
	public void postOrderTraverse(){
		System.out.println("后序遍历");
		this.postOrderTraverse(node);
		System.out.println("");
	}
	//后序遍历
	private void postOrderTraverse(Node node){
		if(node !=null){
			//遍历左子树
			this.postOrderTraverse(node.leftChild);
			//遍历右子树
			this.postOrderTraverse(node.rightChild);
			System.out.print(node.Value+"   ");
			
		}
	}
	//高度
	public int getHeight() {
		System.out.println("二叉树的高度是：");
		return this.getHeight(node);
	}
	private int getHeight(Node node) {
		if(node == null){
			return 0;
		}else {
			//获取左子树的高度
			int nl = this.getHeight(node.leftChild);
			//获取右子树的高度
			int nr = this.getHeight(node.rightChild);
			//返回左子树、右子树较大的高度并加1
			return nl > nr ? nl+1:nr+1;	
		}
	}
	
	
	
	//结点数
	public int size() {
		System.out.println("二叉数结点的个数：");
		return this.size(node);
	}
	private int size(Node node) {
		if (node == null) {
			return 0;
		}else {
			//获取左子树的结点数
			int nl = this.size(node.leftChild);
			//获取右子树的结点数
			int nr = this.size(node.rightChild);
			//返回左右子树的和加1；
			return nl+nr+1;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Test {
	
	public static void main(String[] args) {
		//创建树
		Node node5 = new Node(5, null, null);
		Node node4 = new Node(4, null, node5);
		
		Node node3 = new Node(3, null, null);
		Node node7 = new Node(7, null, null);
		Node node6 = new Node(6, null, node7);
		Node node2 = new Node(2,node3, node6);
		
		Node node1 = new Node(1,node4, node2);
		
		BinaryTree btree = new BinaryTree(node1);
		
		//判断二叉树是否为空
		System.out.println(btree.isEmpty());
		
		//先序遍历递归
		System.out.println("先序遍历");
		btree.preOrder();
		System.out.println("");
		
		//中序遍历递归
		btree.inOrderTraverse();
		
		//后序遍历递归
		btree.postOrderTraverse();
		
		//二叉树的高度
		int h  = btree.getHeight();
		System.out.println(h);
		
		//二叉树的结点数量
		int n = btree.size();
		System.out.println(n);
		
		
	}
}