二叉树部分功能实现（JAVA）
时间：2021-07-01 10:21:17
帮助过：6人阅读
主要实现了二叉树的一般用法，可能会有些错误，还望纠正一下。
- package structure.tree;
- public class Node {
- public int idata;
- public double ddata;
- public Node leftNode;
- public Node rightNode;
-
- public Node() {
-
- }
-
- public void display() {// отй╬╫з╣Ц
- System.out.print('{');
- System.out.print(idata);
- System.out.print(',');
- System.out.print(ddata);
- System.out.print('}');
- }
- }
[code]package structure.tree;
import java.util.Stack;
public class Tree {
/* 节点属性, 树是由节点构成的 */
private Node root;
public Tree() {
root = null;
}
/**
* 查找指定key值的树节点
*
* @param key
* @return
*/
public Node find(int key) {
Node current = root;
while(current.idata != key) {
if(key < current.idata)
current = current.leftNode;
else
current = current.rightNode;
if(current == null)
return null;
}
return current;
}
/**
* 往树结构插入指定节点
* 说明： 插入成功返回true,插入失败返回false
*
* @param key
* @param data
* @return
*/
public boolean insert(int key, double data) {
boolean flag = true;
boolean isLeftNode = false;
Node node = new Node();
node.idata = key;
node.ddata = data;
Node parent = new Node();
if(root == null)
root = node;
else {
Node current = root;
while(current != null) {
parent = current;
if(current.idata > key) {
isLeftNode = true;
current = current.leftNode;
}
else if(current.idata < key) {
isLeftNode = false;
current = current.rightNode;
}
else
flag = false;
}// 结束while循环
}// 结束else条件
if((flag == true) && isLeftNode)
parent.leftNode = node;
else if((flag == true) && !isLeftNode)
parent.rightNode = node;
return flag;
}
/**
* 删除树中的指定节点
* 说明：删除成功返回true,删除失败或者没找到则返回false
* 算法：
* |-- 找到要删除的节点
* |-- 删除叶节点
* |-- 删除只有一个子节点的节点
* |-- 删除有两个子节点的节点
*
* @param key
* @return
*/
public boolean delete(int key) {
boolean flag = true;
boolean isLeftNode = false;
Node current = root;
Node parent = root;
while(current.idata != key) {
parent = current;
if(current.idata > key) {
isLeftNode = true;
current = current.leftNode;
} else {
isLeftNode = false;
current = current.rightNode;
}
if(current == null) {// 没有找到相应的指定节点
flag = false;
return flag;
}
}// 结束while循环
// 执行到此，就意味着找到要删除的节点current
// 删除的节点是叶结点
if(current.leftNode == null && current.rightNode == null) {
if(isLeftNode == true)
parent.leftNode = null;
else
parent.rightNode = null;
}
// 删除的节点只有左子节点
else if(current.rightNode == null) {
if(current == root)
root = current.leftNode;
else if(isLeftNode)
parent.leftNode = current.leftNode;
else
parent.rightNode = current.leftNode;
}
// 删除的节点只有右子节点
else if(current.leftNode == null) {
if(current == root)
root = current.rightNode;
else if(isLeftNode)
parent.leftNode = current.rightNode;
else
parent.rightNode = current.rightNode;
}
// 删除的节点有左子节点和右子节点
else {
Node replacedNode = getReplacedNode(current);
if(current == root)
root = replacedNode;
else if(isLeftNode)
parent.leftNode = replacedNode;
else
parent.rightNode = replacedNode;
}
return flag;
}
/**
* 判断选择遍历方式
*
* @param traverseType
*/
public void traverse(int traverseType) {
switch(traverseType) {
case 1:
System.out.print("\n先序遍历:");
preOrder(root);
break;
case 2:
System.out.print("\n中序遍历:");
inOrder(root);
break;
case 3:
System.out.print("\n后序遍历:");
postOrder(root);
break;
}
System.out.println();
}
/**
* 先序排列
*/
private void preOrder(Node node) {
if(node != null) {
System.out.print(node.idata + " ");
preOrder(node.leftNode);
preOrder(node.rightNode);
}
}
/**
* 中序排列
*/
private void inOrder(Node node) {
if(node != null) {
preOrder(node.leftNode);
System.out.print(node.idata + " ");
preOrder(node.rightNode);
}
}
/**
* 后序排列
*/
private void postOrder(Node node) {
if(node != null) {
preOrder(node.leftNode);
preOrder(node.rightNode);
System.out.print(node.idata + " ");
}
}
/**
* 找到替换【被删除节点】的节点并且构建出以【替换点】为根的子树
* 说明：寻找【被删除节点】中右子树中key值最小的点作为【替换节点】,很明显是右子树中左叶子节点(如果有的话)
*
* @param delNode
* @return
*/
private Node getReplacedNode(Node delNode) {
Node current = delNode.rightNode;
Node replacedNode = delNode;
Node replacedParentNode = delNode;
while(current != null) {
replacedParentNode = replacedNode;
replacedNode = current;
current = current.leftNode;
}
if(replacedNode != delNode.rightNode) {
// replacedNode就是要替换掉【被删除节点】的节点
replacedParentNode.leftNode = replacedNode.rightNode;
replacedNode.rightNode = delNode.rightNode;
}
replacedNode.leftNode = delNode.leftNode;
return replacedNode;
}
/**
* 显示树结构
*
* @param node
*/
@SuppressWarnings("unchecked")
public void displayTree() {
System.out.println(" |
