一个二叉树的实现

编程

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

回到顶部