一个二叉树的实现
package mynode;public class Node {
public int iData;
public double dData;
public Node leftChild;
public Node rightChild;
@Override
public String toString() {
return "Node{" +
"iData=" + iData +
", dData=" + dData +
"}";
}
public void display() {
System.out.println(this.toString());
}
}
package mynode;public class Tree {
private Node root;
public Tree() {
root = null;
}
public Node find(int key) {
Node current = root;
while (current.iData != key) {
if(key < current.iData) {
current = current.leftChild;
} else {
current = current.rightChild;
}
if (current == null){
return null;
}
}
return current;
}
public void insert(int id, double dd) {
Node newNode = new Node();
newNode.iData =id;
newNode.dData = dd;
if(root == null) {
root = newNode;
} else {
Node current = root;
Node parent;
while (true) {
parent = current;
if(id < current.iData) {
current = current.leftChild;
if(current == null) {
parent.leftChild = newNode;
return;
}
} else {
current = current.rightChild;
if(null == current) {
parent.rightChild = newNode;
return;
}
}
}
}
}
public void inOrder(Node localRoot) {
if(localRoot != null) {
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public Node min() {
Node current, last = null;
current = root;
while (current != null) {
last = current;
current = current.leftChild;
}
return last;
}
public Node max() {
Node current, last = null;
current = root;
while (current != null) {
last = current;
current = current.rightChild;
}
return last;
}
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while (current.iData != key) {
parent = current;
if(key < current.iData) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if(current == null) {
System.out.println("没有找到!");
return false;
}
}
//删除的是叶子节点
if(current.leftChild == null && current.rightChild == null) {
//如果是根节点， 清空树
if(current == root) {
root = null;
} else if(isLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
} else if(current.rightChild == null) { //删除的是左子节点
if(current == root) {
root = current.leftChild;
}
if(isLeftChild) {
parent.leftChild = current.leftChild;
} else {
parent.rightChild = current.leftChild;
}
} else if(current.leftChild == null) { //删除的是右子节点
if(current == root) {
root = current.rightChild;
}
if(isLeftChild) {
parent.leftChild = current.rightChild;
} else {
parent.rightChild = current.rightChild;
}
} else {
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root) {
root = successor;
} else if(isLeftChild) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
// connect successor to current"s left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true;
}
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
}
package mynode;public class Client {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(3,2.0);
tree.insert(6,2.0);
tree.insert(4,2.0);
tree.insert(2,2.0);
// tree.insert(50,2.0);
// tree.insert(32,2.0);
tree.insert(7,2.0);
tree.insert(1,2.0);
tree.inOrder(tree.getRoot());
System.out.println("-----------------------------------------------");
Node x = tree.find(4);
x.display();
System.out.println("-----------------------------------------------");
Node min = tree.min();
min.display();
System.out.println("-----------------------------------------------");
Node max = tree.max();
max.display();
//删除根节点
// boolean flag = tree.delete(1);
// System.out.println(flag);
// tree.inOrder(tree.getRoot());
//
//
// System.out.println("-----------------------------------------------");
boolean flag = tree.delete(2);
System.out.println(flag);
tree.inOrder(tree.getRoot());
System.out.println("-----------------------------------------------");
}
}
以上是 一个二叉树的实现 的全部内容， 来源链接： utcz.com/z/516999.html
