查找二叉樹的定義
一棵二叉搜索樹（Binary Sort Tree）是以一棵二叉樹來組織的，可以用鏈表資料結構來表示，其中，每一個結點就是一個物件，一般地，包含資料值和指向孩子（也可能是父母）的指標，如果某個孩子結點不存在，其指標為空（NULL），
- 查找樹的左右子樹各是一棵查找樹
- 若查找樹的左子樹非空，則其左子樹上的各節點值均小于根節點的值，
- 若查找樹的右子樹非空，則其右子樹上的各節點值均大于根節點的值，
二叉樹的后繼節點
對于下面的二叉樹，8的后繼節點為9(題目說的中序遍歷)，6的后繼節點為7，5的后繼節點為6
①如果節點有右子樹，則該節點的后繼節點就是往右子樹出發，然后轉到右子樹的左子樹，一直到左子樹的左子樹為空（即輸入節點的右子樹的最左子樹，例如節點8，后繼節點就是9）其實就是找，結點的右結點里值最小結點，
②如果節點沒有右子樹，則向上尋找父節點，直到父節點的左子樹等于當前節點，則該父節點就是后繼節點（如節點7，沒有右子樹，則向上找，這時到6這個節點，因為6的左子樹不等于7，所以繼續向上找，這時到節點8，8的左子樹等于當前節點6，所以回傳8）
查找二叉樹代碼實作
1 package cn.itcast.test;
2
3 import sun.reflect.generics.tree.Tree;
4
5 public class SearchBinaryTree {
6 public static void main(String[] args) {
7 SearchBinaryTree binaryTree = new SearchBinaryTree();
8 int[] intArray = new int[]{50, 30, 20, 44, 88, 33, 87, 16, 7, 77};
9 for (int i : intArray) {
10 TreeNode put = binaryTree.put(i);
11 }
12 binaryTree.midOrder(binaryTree.root);
13 System.out.println("-----");
14 try {
15 binaryTree.deleteNode(44);
16 binaryTree.midOrder(binaryTree.root);
17 } catch (Exception e) {
18 e.printStackTrace();
19 }
20 }
21
22 //定義根結點
23 private TreeNode root;
24
25 public SearchBinaryTree() {
26
27 }
28
29 /**
30 * 中序遍歷
31 * @param node
32 */
33 public void midOrder(TreeNode node) {
34 if (node == null) {
35 return;
36 } else {
37 midOrder(node.leftChild);
38 System.out.println(node.data);
39 midOrder(node.rightChild);
40 }
41 }
42
43 /**
44 * 創建查找二叉樹，添加結點
45 */
46 public TreeNode put(int data) {
47 TreeNode node = null;//定義一個結點
48 TreeNode parent = null;//定義一個父節點
49 node = new TreeNode(0, data);//創建一個結點
50 if (root == null) {
51 root = node;//創建根節點
52 return node;
53 }
54 node = root;
55 while (node != null) {//找左右結點，直到note=null，跳出回圈
56 parent = node;//先暫時把當前結點當做父節點
57 if (data > node.data) {//data：根節點
58 node = node.rightChild;
59 } else if (data < node.data) {
60 node = node.leftChild;
61 } else {
62 return node;
63 }
64 }
65
66 //表示將此結點添加到相應位置
67 node = new TreeNode(0, data);
68 if (data < parent.data) {//傳data值
69 parent.leftChild = node;
70 node.parent = parent;
71 } else {
72 parent.rightChild = node;
73 node.parent = parent;
74 }
75 return node;
76 }
77
78
79 public void deleteNode(int key) throws Exception {
80 //查找node結點
81 TreeNode node = searchNode(key);
82 if (node == null) {
83 throw new Exception("該節點無法找到");
84 } else {
85 //洗掉該結點
86 delete(node);
87 }
88 }
89
90 private void delete(TreeNode node) throws Exception {
91 //嚴謹，再判斷一次，可以單獨寫一個方法判斷
92 if (node == null) {
93 throw new Exception("該節點無法找到");
94 } else {
95 TreeNode parent = node.parent;
96 //1.被洗掉的結點無左右孩子
97 if (node.leftChild == null && node.rightChild == null) {
98 if (parent.leftChild == node) {
99 parent.leftChild = null;//斷開父結點與其的連接，等于洗掉了
100 } else {
101 parent.rightChild = null;
102 }
103 return;
104 }
105 //2.被洗掉的結點有左無右
106 if (node.leftChild != null && node.rightChild == null) {
107 if (parent.leftChild == node) {
108 //在父結點的左邊，并且有左無右
109 parent.leftChild = node.leftChild;
110 } else {
111 //在父結點的右邊，并且有左無右
112 parent.rightChild = node.leftChild;
113 }
114 return;
115 }
116 //3.被洗掉的結點有右無左
117 if (node.leftChild == null && node.rightChild != null) {
118 if (parent.leftChild == node) {
119 //在父結點的左邊，并且有右無左
120 parent.leftChild = node.rightChild;
121 } else {
122 //在父結點的右邊，并且有右無左
123 parent.rightChild = node.rightChild;
124 }
125 return;
126 }
127 //4.被洗掉的結點有左有右
128 TreeNode next = getNextNode(node);//找到該結點node的后繼結點
129 delete(next);//遞回
130 node.data = https://www.cnblogs.com/xiaozhongfeixiang/p/next.data;//完成賦值
131 }
132 }
133
134 /**
135 * 獲取一個結點的后繼結點
136 * @param node
137 * @return
138 */
139 private TreeNode getNextNode(TreeNode node) {
140 if (node == null) {
141 return null;
142 } else {
143 if (node.rightChild != null) {
144 //找某結點的最小關鍵字結點
145 return getMinTreeNode(node.rightChild);
146 } else {
147 TreeNode parent = node.parent;
148 //直到node是父結點的左結點，而不是父結點的右結點
149 while (parent != null && node == parent.rightChild) {
150 node = parent;
151 parent = parent.parent;
152 }
153 return parent;
154 }
155 }
156 }
157
158 private TreeNode getMinTreeNode(TreeNode node) {
159 if (node == null) {
160 return null;
161 } else {
162 //一直往左子樹找，直到找到為止
163 while (node.leftChild != null) {
164 node = node.leftChild;
165 }
166 }
167 return node;
168 }
169
170 /**
171 * 找node結點，要么為空，要么找到
172 *
173 * @param key
174 * @return
175 */
176 private TreeNode searchNode(int key) {
177 TreeNode node = root;//為了從根節點開始查找
178 if (node == null) {
179 return null;
180 } else {
181 while (node != null && key != node.data) {
182 if (key < node.data) {
183 node = node.leftChild;//左子樹永遠比右子樹小
184 } else {
185 node = node.rightChild;
186 }
187 }
188 }
189 return node;
190 }
191
192
193 class TreeNode {
194 private int key;
195 private TreeNode leftChild;
196 private TreeNode rightChild;
197 private TreeNode parent;
198 private int data;
199
200 public TreeNode(int key, int data) {
201 //呼叫父類的構造方法，即Object類的無參構造方法
202 super();
203 this.key = key;
204 this.data =https://www.cnblogs.com/xiaozhongfeixiang/p/ data;
205 this.leftChild = null;
206 this.rightChild = null;
207 this.parent = null;
208 }
209
210 public int getKey() {
211 return key;
212 }
213
214 public void setKey(int key) {
215 this.key = key;
216 }
217
218 public TreeNode getLeftChild() {
219 return leftChild;
220 }
221
222 public void setLeftChild(TreeNode leftChild) {
223 this.leftChild = leftChild;
224 }
225
226 public TreeNode getRightChild() {
227 return rightChild;
228 }
229
230 public void setRightChild(TreeNode rightChild) {
231 this.rightChild = rightChild;
232 }
233
234 public TreeNode getParent() {
235 return parent;
236 }
237
238 public void setParent(TreeNode parent) {
239 this.parent = parent;
240 }
241
242 public int getData() {
243 return data;
244 }
245
246 public void setData(int data) {
247 this.data =https://www.cnblogs.com/xiaozhongfeixiang/p/ data;
248 }
249 }
250 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137719.html
標籤：其他
上一篇：五大常用演算法簡介