Posted on 2008-10-24 00:06
eyejava 阅读(282)
评论(0) 编辑 收藏
package tree;
/**
* 结点数据
* @author jiaqiang
*
*/
public class Node {
private int key;
private int data;
private Node leftChild;
private Node rightChild;
public Node() {}
public Node(int key, int data) {
this.key = key;
this.data = data;
}
public int getKey() {
return key;
}
public int getData() {
return data;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
public void display() {
System.out.print(data + " ");
}
}
-------------------
package tree;
/**
* 二叉树
* @author jiaqiang
*
*/
public class Tree {
private Node root;
private int size;
/**
* 查找某个值
* @param key 要查找的值
* @return Node 查找到的结点
*/
public Node find(int key) {
Node current = root;
while ((current!=null) && (current.getKey()!=key)) {
if (key < current.getKey()) { //go left
current = current.getLeftChild();
} else {
current = current.getRightChild(); //go right
}
if (current == null) {
return null;
}
}
return current;
}
/**
* 插入某个值
* @param key
* @param data
*/
public void insert(int key, int data) {
Node newNode = new Node(key, data);
if (root == null) { //空树
root = newNode;
size++;
} else { //not empty tree
Node current = root;
Node parent; //作为插入结点的父结点
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
size++;
return;
}
} //end if go left
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
size++;
return;
}
} //end if go right
} // end while (true)
}
} //end insert
/**
* 中序遍历,该方法为辅助方法
* @param Node localRoot
*/
private void inOrder(Node localRoot) {
if (localRoot != null) {
inOrder(localRoot.getLeftChild());
localRoot.display();
inOrder(localRoot.getRightChild());
} else
return;
}
/**
* 中序遍历
*/
public void inOrder() {
inOrder(root);
}
public int getSize() {
return size;
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(23, 23);
tree.insert(20, 20);
tree.insert(24, 24);
System.out.println(tree.getSize());
tree.inOrder();
}
}