正文
Java对二叉搜索树进行插入、查找、遍历、最大值和最小值的操作
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
1、首先，须要一个节点对象的类。这些对象包括数据。数据代表存储的内容，并且还有指向节点的两个子节点的引用
class Node {
public int iData;
public double dData;
public Node leftChild;
public Node rightChild;
public void displayNode() {
System.out.print("{");
System.out.print(iData);
System.out.print(",");
System.out.print(dData);
System.out.print("}");
}
}
2、插入一个节点
从根開始查找一个对应的节点，它将是新节点的父节点。
当父节点找到了，新节点就能够连接到它的左子节点或右子节点处。这取决于新节点的值是比父节点的值大还是小。
以下是insert()方法代码：
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(current == null) {
parent.rightChild = newNode;
return;
}
}
} // end while
} // end else
}
这里用一个新的变量parent(current的父节点)，来存储遇到的最后一个不是null的节点。必须这样做，由于current在查找的过程中会变成null，才干发现它查过的上一个节点没有一个相应的子节点。
假设不存储parent。就会失去插入新节点的位置。
3、查找一个节点
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;
}
找到节点：假设while循环不满足条件，从循环的末端退出来。current的iData字段和key相等，这就找到了该节点。
找不到节点：假设current等于null。在查找序列中找不到下一个子节点，到达序列的末端而没有找到要找的节点。表明了它不存在。返回nulll来指出这个情况。
4、遍历树（前序遍历。中序遍历，后序遍历）
/**
* 前序遍历
* @param localRoot
*/
public void preOrder(Node localRoot) {
if(localRoot != null) {
System.out.print(localRoot.iData+" ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
} /**
* 中序遍历
* @param localRoot
*/
public void inOrder(Node localRoot) {
if(localRoot != null) {
preOrder(localRoot.leftChild);
System.out.print(localRoot.iData+" ");
preOrder(localRoot.rightChild);
}
} /**
* 后序遍历
* @param localRoot
*/
public void postOrder(Node localRoot) {
if(localRoot != null) {
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
System.out.print(localRoot.iData+" ");
}
}
遍历树的最简单方法使用递归的方法。
用递归的方法遍历整棵树要用一个节点作为參数。初始化这个节点是根。比如中序遍历仅仅须要做三件事：
1）、调用自身来遍历节点的左子树
2）、訪问这个节点
3）、调用自身来遍历节点的右子树。
5、查找最大值和最小值
/**
* 求树中的最小值
* @return
*/
public Node minimum() {
Node current;
current = root;
Node last = null;
while(current != null) {
last = current;
current = current.leftChild;
}
return last;
} /**
* 求树中的最大值
* @return
*/
public Node maxmum() {
Node current;
current = root;
Node last = null;
while(current != null) {
last = current;
current = current.rightChild;
}
return last;
}
下面是完整測试代码：
package binTree;
class Node {
public int iData;
public double dData;
public Node leftChild;
public Node rightChild;
public void displayNode() {
System.out.print("{");
System.out.print(iData);
System.out.print(",");
System.out.print(dData);
System.out.print("}");
}
}
class Tree {
private Node root;
public Tree() {
root = null;
}
/**
* 查找节点
* @param key
* @return
*/
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;
}
/**
* 插入节点
* @param id
* @param dd
*/
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(current == null) {
parent.rightChild = newNode;
return;
}
}
} // end while
} // end else
}
/**
* 前序遍历
* @param localRoot
*/
public void preOrder(Node localRoot) {
if(localRoot != null) {
System.out.print(localRoot.iData+" ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
/**
* 中序遍历
* @param localRoot
*/
public void inOrder(Node localRoot) {
if(localRoot != null) {
preOrder(localRoot.leftChild);
System.out.print(localRoot.iData+" ");
preOrder(localRoot.rightChild);
}
}
/**
* 后序遍历
* @param localRoot
*/
public void postOrder(Node localRoot) {
if(localRoot != null) {
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
System.out.print(localRoot.iData+" ");
}
}
/**
* 求树中的最小值
* @return
*/
public Node minimum() {
Node current;
current = root;
Node last = null;
while(current != null) {
last = current;
current = current.leftChild;
}
return last;
}
/**
* 求树中的最大值
* @return
*/
public Node maxmum() {
Node current;
current = root;
Node last = null;
while(current != null) {
last = current;
current = current.rightChild;
}
return last;
}
}
public class TreeApp {
public static void main(String[] args) {
Tree theTree = new Tree();
/**
* 50
* / \
* 25 75
* / \ \
* 12 37 87
* / \ \
* 30 43 93
* \ \
* 33 97
*/
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
System.out.println("插入完成~");
//找到root节点
Node nodeRoot = theTree.find(50);
// 中序遍历
theTree.inOrder(nodeRoot);
System.out.println();
// 求最小值
System.out.println("mini:"+ theTree.minimum().iData);
// 求最大值
System.out.println("max:"+ theTree.maxmum().iData);
}
}
