数据结构二叉树的java实现,包括二叉树的创建、搜索、删除和遍历

时间:2024-10-12 11:04:19

根据自己的学习体会并参考了一些网上的资料,以java写出了二叉树的创建、搜索、删除和遍历等操作,尚未实现的功能有:根据先序和中序遍历,得到后序遍历以及根据后序和中序遍历,得到先序遍历,以及获取栈的深度和其它的一些方法等完成了再继续更新:

二叉树的java实现:

 package com.peter.java.dsa.common;

 import java.util.ArrayList;

 public class BinaryTree {
private TreeNode root;
private int size = 0; public BinaryTree() {
// TODO Auto-generated constructor stub
} public BinaryTree(int value) {
// TODO Auto-generated constructor stub
this.root = new TreeNode(value);
this.size = 1;
} public TreeNode getRoot() {
return root;
} public int getMax() {
TreeNode node = root;
while (node.rightChildNode != null) {
node = node.rightChildNode;
}
return node.value;
} public int getMin() {
TreeNode node = root;
while (node.leftChildNode != null) {
node = node.leftChildNode;
}
return node.value;
} public void preOrderTreeWalk(TreeNode node, ArrayList<Integer> container) {
if (node != null) {
container.add(node.value);
preOrderTreeWalk(node.leftChildNode, container);
preOrderTreeWalk(node.rightChildNode, container);
}
} public void midOrderTreeWalk(TreeNode node, ArrayList<Integer> container) {
if (node != null) {
midOrderTreeWalk(node.leftChildNode, container);
container.add(node.value);
midOrderTreeWalk(node.rightChildNode, container);
}
} public void postOrderTreeWalk(TreeNode node, ArrayList<Integer> container) {
if (node != null) {
postOrderTreeWalk(node.leftChildNode, container);
postOrderTreeWalk(node.rightChildNode, container);
container.add(node.value);
}
} public TreeNode search(int value) {
TreeNode node = root;
while (node.value != value) {
if (value < node.value) {
node = node.leftChildNode;
} else {
node = node.rightChildNode;
}
if (node == null) {
node = null;
}
}
return node;
} private TreeNode findParentNode(int value) {
TreeNode parent = null;
TreeNode node = root;
while (node.value != value) {
parent = node;
if (value < node.value) {
node = node.leftChildNode;
} else {
node = node.rightChildNode;
}
if (node == null) {
node = null;
parent = null;
}
}
return parent;
} public void createBinaryTree(int[] data) {
if (data != null) {
for (int i : data) {
insert(i);
}
}
} public void insert(int value) {
if (root == null) {
root = new TreeNode(value);
} else {
TreeNode curNode = root;
TreeNode parentNode;
while (true) {
parentNode = curNode;
if (value < curNode.value) {
curNode = curNode.leftChildNode;
if (curNode == null) {
parentNode.leftChildNode = new TreeNode(value);
parentNode.leftChildNode.leftOrRight = -1;
break;
}
} else {
curNode = curNode.rightChildNode;
if (curNode == null) {
parentNode.rightChildNode = new TreeNode(value);
parentNode.rightChildNode.leftOrRight = 1;
break;
}
}
}
}
++size;
} public boolean delete(int value) {
boolean flag = false;
TreeNode node = search(value);
TreeNode parent = findParentNode(value);
if (node != null) {
if (node.equals(root)) {
root = null;
}
if (node.leftChildNode == null && node.rightChildNode == null) {
if (node.leftOrRight == 1) {
node = null;
parent.rightChildNode = null;
}
if (node.leftOrRight == -1) {
node = null;
parent.leftChildNode = null;
}
} else if (node.leftChildNode != null
&& node.rightChildNode != null) {
TreeNode successor = findSuccessor(node);
if (node.leftOrRight == -1) {
parent.leftChildNode = successor;
parent.leftChildNode.leftOrRight = -1;
}
if (node.leftOrRight == 1) {
parent.rightChildNode = successor;
parent.rightChildNode.leftOrRight = 1;
}
successor.leftChildNode = node.leftChildNode;
} else {
if (node.leftChildNode != null) {
if (node.leftOrRight == 1) {
parent.rightChildNode = node.leftChildNode;
}
if (node.leftOrRight == -1) {
parent.leftChildNode = node.leftChildNode;
}
}
if (node.rightChildNode != null) {
if (node.leftOrRight == 1) {
parent.rightChildNode = node.rightChildNode;
}
if (node.leftOrRight == -1) {
parent.leftChildNode = node.rightChildNode;
}
}
node = null;
}
flag = true;
--size;
}
return flag;
} private TreeNode findSuccessor(TreeNode delNode) {
TreeNode parent = delNode;
TreeNode successor = delNode;
TreeNode curNode = delNode.rightChildNode; while (curNode != null) {
parent = successor;
successor = curNode;
curNode = curNode.leftChildNode;
}
if (!successor.equals(delNode.rightChildNode)) {
parent.leftChildNode = successor.rightChildNode;
successor.rightChildNode = delNode.rightChildNode;
}
return successor;
} public int size() {
return this.size;
} public boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
} public class TreeNode {
int leftOrRight = 0;// 0: root;-1:left child node;1, right childe node;
Integer value;
TreeNode leftChildNode;
TreeNode rightChildNode; public TreeNode(Integer value) {
// TODO Auto-generated constructor stub
this.value = value;
} @Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
if (obj instanceof TreeNode) {
TreeNode node = (TreeNode) obj;
return node.value == this.value;
}
return false;
} @Override
public String toString() {
return "TreeNode [leftOrRight="
+ leftOrRight
+ ", value="
+ value
+ (leftChildNode != null ? ", leftChildNode="
+ leftChildNode : "")
+ (rightChildNode != null ? ", rightChildNode="
+ rightChildNode : "") + "]";
}
}
}

测试代码如下:

 package com.peter.java.dsa.test;

 import java.util.ArrayList;
import java.util.Arrays; import com.peter.java.dsa.common.BinaryTree;
import com.peter.java.dsa.common.BinaryTree.TreeNode; public class Test { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] data = { 21, 25, 16, 32, 22, 19, 13, 20 };
System.out.println("input: " + Arrays.toString(data));
BinaryTree bTree = new BinaryTree();
System.out.println(bTree.isEmpty() + "--" + bTree.size());
bTree.createBinaryTree(data);
System.out.println(bTree.isEmpty() + "--" + bTree.size());
ArrayList<Integer> container = new ArrayList<Integer>();
TreeNode root = bTree.getRoot();
container.clear();
bTree.preOrderTreeWalk(root, container);
System.out.println("pre Order Binary Tree Walk: "
+ container.toString());
container.clear();
bTree.midOrderTreeWalk(root, container);
System.out.println("mid Order Binary Tree Walk: "
+ container.toString());
container.clear();
bTree.postOrderTreeWalk(root, container);
System.out.println("post Order Binary Tree Walk: "
+ container.toString());
System.out.println("Max Value: " + bTree.getMax());
System.out.println("Max Value: " + bTree.getMin());
// change the function findParentNode() to be private
// TreeNode parent = bTree.findParentNode(25);
// if (parent != null) {
// System.out.println("Parent Value: " + parent.toString());
// }
// delete a node which has no child nodes, successfully
// bTree.delete(13);
// container.clear();
// bTree.midOrderTreeWalk(root, container);
// System.out.println("mid Order Binary Tree Walk: "
// + container.toString());
// container.clear();
// bTree.postOrderTreeWalk(root, container);
// System.out.println("post Order Binary Tree Walk: "
// + container.toString());
// delete a node which has a right child node, successfully
// bTree.delete(19);
// container.clear();
// bTree.preOrderTreeWalk(root, container);
// System.out.println("pre Order Binary Tree Walk: "
// + container.toString());
// container.clear();
// bTree.midOrderTreeWalk(root, container);
// System.out.println("mid Order Binary Tree Walk: "
// + container.toString()); // delete a node which has a right child node, successfully
bTree.delete(16);
container.clear();
bTree.preOrderTreeWalk(root, container);
System.out.println("pre Order Binary Tree Walk: "
+ container.toString());
container.clear();
bTree.midOrderTreeWalk(root, container);
System.out.println("mid Order Binary Tree Walk: "
+ container.toString());
}
}

相关文章