二叉排序樹又稱二叉查找樹。它或者是一顆空樹，或者是具有以下性質(zhì)的二叉樹：
①如果左子樹不空，那么左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
②如果右子樹不空，那么右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
③左右子樹也分別為二叉排序樹。
以下代碼實(shí)現(xiàn)了：
- 二叉樹的構(gòu)建
- 二叉樹的中、前、后、層序遍歷
- 二叉樹中結(jié)點(diǎn)的最大距離
|
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 * 實(shí)現(xiàn)二叉排序樹，包括插入、中序遍歷、先序遍歷、后序遍歷、計(jì)算所有節(jié)點(diǎn)的最大距離的功能 */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; } } } } } //將數(shù)值輸入構(gòu)建二叉樹 public void buildTree(int[] data){ for (int i = 0; i < data.length; i++) { insert(data[i]); } } //中序遍歷方法遞歸實(shí)現(xiàn) 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); } //先序遍歷方法遞歸實(shí)現(xiàn) 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); } //后序遍歷方法遞歸實(shí)現(xiàn) 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); } /** * 層序遍歷二叉樹：現(xiàn)將根結(jié)點(diǎn)放入隊(duì)列中，然后每次都從隊(duì)列中取一個(gè)結(jié)點(diǎn)打印該結(jié)點(diǎn)的值， * 若這個(gè)結(jié)點(diǎn)有子結(jié)點(diǎn)，則將它的子結(jié)點(diǎn)放入隊(duì)列尾，直到隊(duì)列為空 */ 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); //計(jì)算左字樹中距離根結(jié)點(diǎn)的最大距離 if(root.left!=null) root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1; //計(jì)算右字樹中距離根結(jié)點(diǎn)的最大距離 if(root.right!=null) root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1; //獲取二叉樹所有結(jié)點(diǎn)的最大距離 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("二叉樹中結(jié)點(diǎn)的最大距離："+biTree.maxLen); }} |
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持服務(wù)器之家！
原文鏈接：http://www.cnblogs.com/winorgohome/p/6044627.html
