データ構造ツリーのjava実装(ツリーの作成、検索、削除、遍歴を含む)
41991 ワード
自分の学習体験に基づいて、いくつかのネット上の資料を参考にして、javaで二叉木の作成、検索、削除、遍歴などの操作を書きました.まだ実現されていない機能は、先序と中序に基づいて遍歴し、後序と中序に基づいて遍歴し、先序に遍歴し、スタックの深さとその他の方法を取得するなどしてから更新を続けます.
ツリーのjava実装:
テストコードは次のとおりです.
ツリーのjava実装:
1 package com.peter.java.dsa.common;
2
3 import java.util.ArrayList;
4
5 public class BinaryTree {
6 private TreeNode root;
7 private int size = 0;
8
9 public BinaryTree() {
10 // TODO Auto-generated constructor stub
11 }
12
13 public BinaryTree(int value) {
14 // TODO Auto-generated constructor stub
15 this.root = new TreeNode(value);
16 this.size = 1;
17 }
18
19 public TreeNode getRoot() {
20 return root;
21 }
22
23 public int getMax() {
24 TreeNode node = root;
25 while (node.rightChildNode != null) {
26 node = node.rightChildNode;
27 }
28 return node.value;
29 }
30
31 public int getMin() {
32 TreeNode node = root;
33 while (node.leftChildNode != null) {
34 node = node.leftChildNode;
35 }
36 return node.value;
37 }
38
39 public void preOrderTreeWalk(TreeNode node, ArrayList<Integer> container) {
40 if (node != null) {
41 container.add(node.value);
42 preOrderTreeWalk(node.leftChildNode, container);
43 preOrderTreeWalk(node.rightChildNode, container);
44 }
45 }
46
47 public void midOrderTreeWalk(TreeNode node, ArrayList<Integer> container) {
48 if (node != null) {
49 midOrderTreeWalk(node.leftChildNode, container);
50 container.add(node.value);
51 midOrderTreeWalk(node.rightChildNode, container);
52 }
53 }
54
55 public void postOrderTreeWalk(TreeNode node, ArrayList<Integer> container) {
56 if (node != null) {
57 postOrderTreeWalk(node.leftChildNode, container);
58 postOrderTreeWalk(node.rightChildNode, container);
59 container.add(node.value);
60 }
61 }
62
63 public TreeNode search(int value) {
64 TreeNode node = root;
65 while (node.value != value) {
66 if (value < node.value) {
67 node = node.leftChildNode;
68 } else {
69 node = node.rightChildNode;
70 }
71 if (node == null) {
72 node = null;
73 }
74 }
75 return node;
76 }
77
78 private TreeNode findParentNode(int value) {
79 TreeNode parent = null;
80 TreeNode node = root;
81 while (node.value != value) {
82 parent = node;
83 if (value < node.value) {
84 node = node.leftChildNode;
85 } else {
86 node = node.rightChildNode;
87 }
88 if (node == null) {
89 node = null;
90 parent = null;
91 }
92 }
93 return parent;
94 }
95
96 public void createBinaryTree(int[] data) {
97 if (data != null) {
98 for (int i : data) {
99 insert(i);
100 }
101 }
102 }
103
104 public void insert(int value) {
105 if (root == null) {
106 root = new TreeNode(value);
107 } else {
108 TreeNode curNode = root;
109 TreeNode parentNode;
110 while (true) {
111 parentNode = curNode;
112 if (value < curNode.value) {
113 curNode = curNode.leftChildNode;
114 if (curNode == null) {
115 parentNode.leftChildNode = new TreeNode(value);
116 parentNode.leftChildNode.leftOrRight = -1;
117 break;
118 }
119 } else {
120 curNode = curNode.rightChildNode;
121 if (curNode == null) {
122 parentNode.rightChildNode = new TreeNode(value);
123 parentNode.rightChildNode.leftOrRight = 1;
124 break;
125 }
126 }
127 }
128 }
129 ++size;
130 }
131
132 public boolean delete(int value) {
133 boolean flag = false;
134 TreeNode node = search(value);
135 TreeNode parent = findParentNode(value);
136 if (node != null) {
137 if (node.equals(root)) {
138 root = null;
139 }
140 if (node.leftChildNode == null && node.rightChildNode == null) {
141 if (node.leftOrRight == 1) {
142 node = null;
143 parent.rightChildNode = null;
144 }
145 if (node.leftOrRight == -1) {
146 node = null;
147 parent.leftChildNode = null;
148 }
149 } else if (node.leftChildNode != null
150 && node.rightChildNode != null) {
151 TreeNode successor = findSuccessor(node);
152 if (node.leftOrRight == -1) {
153 parent.leftChildNode = successor;
154 parent.leftChildNode.leftOrRight = -1;
155 }
156 if (node.leftOrRight == 1) {
157 parent.rightChildNode = successor;
158 parent.rightChildNode.leftOrRight = 1;
159 }
160 successor.leftChildNode = node.leftChildNode;
161 } else {
162 if (node.leftChildNode != null) {
163 if (node.leftOrRight == 1) {
164 parent.rightChildNode = node.leftChildNode;
165 }
166 if (node.leftOrRight == -1) {
167 parent.leftChildNode = node.leftChildNode;
168 }
169 }
170 if (node.rightChildNode != null) {
171 if (node.leftOrRight == 1) {
172 parent.rightChildNode = node.rightChildNode;
173 }
174 if (node.leftOrRight == -1) {
175 parent.leftChildNode = node.rightChildNode;
176 }
177 }
178 node = null;
179 }
180 flag = true;
181 --size;
182 }
183 return flag;
184 }
185
186 private TreeNode findSuccessor(TreeNode delNode) {
187 TreeNode parent = delNode;
188 TreeNode successor = delNode;
189 TreeNode curNode = delNode.rightChildNode;
190
191 while (curNode != null) {
192 parent = successor;
193 successor = curNode;
194 curNode = curNode.leftChildNode;
195 }
196 if (!successor.equals(delNode.rightChildNode)) {
197 parent.leftChildNode = successor.rightChildNode;
198 successor.rightChildNode = delNode.rightChildNode;
199 }
200 return successor;
201 }
202
203 public int size() {
204 return this.size;
205 }
206
207 public boolean isEmpty() {
208 // TODO Auto-generated method stub
209 return size == 0;
210 }
211
212 public class TreeNode {
213 int leftOrRight = 0;// 0: root;-1:left child node;1, right childe node;
214 Integer value;
215 TreeNode leftChildNode;
216 TreeNode rightChildNode;
217
218 public TreeNode(Integer value) {
219 // TODO Auto-generated constructor stub
220 this.value = value;
221 }
222
223 @Override
224 public boolean equals(Object obj) {
225 // TODO Auto-generated method stub
226 if (obj instanceof TreeNode) {
227 TreeNode node = (TreeNode) obj;
228 return node.value == this.value;
229 }
230 return false;
231 }
232
233 @Override
234 public String toString() {
235 return "TreeNode [leftOrRight="
236 + leftOrRight
237 + ", value="
238 + value
239 + (leftChildNode != null ? ", leftChildNode="
240 + leftChildNode : "")
241 + (rightChildNode != null ? ", rightChildNode="
242 + rightChildNode : "") + "]";
243 }
244 }
245 }テストコードは次のとおりです.
1 package com.peter.java.dsa.test;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 import com.peter.java.dsa.common.BinaryTree;
7 import com.peter.java.dsa.common.BinaryTree.TreeNode;
8
9 public class Test {
10
11 /**
12 * @param args
13 */
14 public static void main(String[] args) {
15 // TODO Auto-generated method stub
16 int[] data = { 21, 25, 16, 32, 22, 19, 13, 20 };
17 System.out.println("input: " + Arrays.toString(data));
18 BinaryTree bTree = new BinaryTree();
19 System.out.println(bTree.isEmpty() + "--" + bTree.size());
20 bTree.createBinaryTree(data);
21 System.out.println(bTree.isEmpty() + "--" + bTree.size());
22 ArrayList<Integer> container = new ArrayList<Integer>();
23 TreeNode root = bTree.getRoot();
24 container.clear();
25 bTree.preOrderTreeWalk(root, container);
26 System.out.println("pre Order Binary Tree Walk: "
27 + container.toString());
28 container.clear();
29 bTree.midOrderTreeWalk(root, container);
30 System.out.println("mid Order Binary Tree Walk: "
31 + container.toString());
32 container.clear();
33 bTree.postOrderTreeWalk(root, container);
34 System.out.println("post Order Binary Tree Walk: "
35 + container.toString());
36 System.out.println("Max Value: " + bTree.getMax());
37 System.out.println("Max Value: " + bTree.getMin());
38 // change the function findParentNode() to be private
39 // TreeNode parent = bTree.findParentNode(25);
40 // if (parent != null) {
41 // System.out.println("Parent Value: " + parent.toString());
42 // }
43 // delete a node which has no child nodes, successfully
44 // bTree.delete(13);
45 // container.clear();
46 // bTree.midOrderTreeWalk(root, container);
47 // System.out.println("mid Order Binary Tree Walk: "
48 // + container.toString());
49 // container.clear();
50 // bTree.postOrderTreeWalk(root, container);
51 // System.out.println("post Order Binary Tree Walk: "
52 // + container.toString());
53 // delete a node which has a right child node, successfully
54 // bTree.delete(19);
55 // container.clear();
56 // bTree.preOrderTreeWalk(root, container);
57 // System.out.println("pre Order Binary Tree Walk: "
58 // + container.toString());
59 // container.clear();
60 // bTree.midOrderTreeWalk(root, container);
61 // System.out.println("mid Order Binary Tree Walk: "
62 // + container.toString());
63
64 // delete a node which has a right child node, successfully
65 bTree.delete(16);
66 container.clear();
67 bTree.preOrderTreeWalk(root, container);
68 System.out.println("pre Order Binary Tree Walk: "
69 + container.toString());
70 container.clear();
71 bTree.midOrderTreeWalk(root, container);
72 System.out.println("mid Order Binary Tree Walk: "
73 + container.toString());
74 }
75 }