二叉排序樹又稱二叉查找樹。它或者是一顆空樹，或者是具有以下性質的二叉樹：
①如果左子樹不空，那么左子樹上所有結點的值均小于它的根結點的值；
②如果右子樹不空，那么右子樹上所有結點的值均大于它的根結點的值；
③左右子樹也分別為二叉排序樹。
以下代碼實現了：
- 二叉樹的構建
- 二叉樹的中、前、后、層序遍歷
- 二叉樹中結點的最大距離
|
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
import java.util.LinkedList;import java.util.Queue;class Node{ public int data; public Node left; public Node right; public int leftMaxDistance; public int rightMaxDistance; public Node(int data){ this.data=data; this.left=null; this.right=null; }}/** * @author TY * 實現二叉排序樹，包括插入、中序遍歷、先序遍歷、后序遍歷、計算所有節點的最大距離的功能 */public class BinaryTree { private Node root; public BinaryTree(){ root=null; } public void insert(int data){ Node newNode=new Node(data); if(root==null) root=newNode; else{ Node current=root; Node parent; while (true) {//尋找插入位置 parent=current; if(data<current.data){ current=current.left; if(current==null){ parent.left=newNode; return; } }else{ current=current.right; if (current==null) { parent.right=newNode; return; } } } } } //將數值輸入構建二叉樹 public void buildTree(int[] data){ for (int i = 0; i < data.length; i++) { insert(data[i]); } } //中序遍歷方法遞歸實現 public void inOrder(Node localRoot){ if(localRoot!=null){ inOrder(localRoot.left); System.out.print(localRoot.data+" "); inOrder(localRoot.right); } } public void inOrder(){ this.inOrder(this.root); } //先序遍歷方法遞歸實現 public void preOrder(Node localRoot){ if(localRoot!=null){ System.out.print(localRoot.data+" "); preOrder(localRoot.left); preOrder(localRoot.right); } } public void preOrder(){ this.preOrder(this.root); } //后序遍歷方法遞歸實現 public void postOrder(Node localRoot){ if(localRoot!=null){ postOrder(localRoot.left); postOrder(localRoot.right); System.out.print(localRoot.data+" "); } } public void postOrder(){ this.postOrder(this.root); } /** * 層序遍歷二叉樹：現將根結點放入隊列中，然后每次都從隊列中取一個結點打印該結點的值， * 若這個結點有子結點，則將它的子結點放入隊列尾，直到隊列為空 */ public void layerTranverse(){ if(this.root==null) return; Queue<Node> q=new LinkedList<Node>(); q.add(this.root); while(!q.isEmpty()){ Node n=q.poll(); System.out.print(n.data+" "); if(n.left!=null) q.add(n.left); if(n.right!=null) q.add(n.right); } } private int maxLen=0; private int max(int a,int b){ return a>b?a:b; } public void findMaxDistance(Node root){ if(root==null) return; if(root.left==null) root.leftMaxDistance=0; if(root.right==null) root.rightMaxDistance=0; if(root.left!=null) findMaxDistance(root.left); if(root.right!=null) findMaxDistance(root.right); //計算左字樹中距離根結點的最大距離 if(root.left!=null) root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1; //計算右字樹中距離根結點的最大距離 if(root.right!=null) root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1; //獲取二叉樹所有結點的最大距離 if(root.leftMaxDistance+root.rightMaxDistance>maxLen){maxLen=root.leftMaxDistance+root.rightMaxDistance; } } public static void main(String[] args) { BinaryTree biTree=new BinaryTree(); int[] data={2,8,7,4,9,3,1,6,7,5}; biTree.buildTree(data); System.out.print("二叉樹的中序遍歷："); biTree.inOrder(); System.out.println(); System.out.print("二叉樹的先序遍歷："); biTree.preOrder(); System.out.println(); System.out.print("二叉樹的后序遍歷："); biTree.postOrder(); System.out.println(); System.out.print("二叉樹的層序遍歷："); biTree.layerTranverse(); System.out.println(); biTree.findMaxDistance(biTree.root); System.out.println("二叉樹中結點的最大距離："+biTree.maxLen); }} |
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/winorgohome/p/6044627.html
