java——二叉树的实现代码
/**
* @ClassName Node
* @Description 树的节点
* @Author lzq
* @Date 2018/11/28 12:44
* @Version 1.0
**/
public class Node {
String data; //元素数据
Node left; //左子树节点的引用
Node right; //右子树节点的引用
}
import java.util.Scanner;
/**
* @ClassName BinaryTree
* @Description 二叉树
* @Author lzq
* @Date 2018/11/28 11:52
* @Version 1.0
**/
public class BinaryTree {
Scanner scan = new Scanner(System.in);
/**
* 初始化根节点
* @return
*/
public Node rootnode() {
Node node;
if((node = new Node()) != null) {
System.out.println("请输入一个根节点数据：");
node.data = scan.next();
node.left = null;
node.right = null;
if(node != null) {
return node;
}else {
return null;
}
}
return null;
}
/**
* 添加节点
* @param node
*/
public void add_tree_node(Node node) {
Node p,parent;
String data;
int count;
if((p = new Node()) != null) {
System.out.println("输入二叉树节点数据:");
p.data = scan.next();
p.left = null;
p.right = null;
System.out.println("请输入该节点的父节点的数据：");
data = scan.next();
parent = find_tree_node(node,data);
if(parent == null) {
System.out.println("未找到父节点！");
parent = null;
return;
}
System.out.println("1、添加该结点到左子树\n 2、添加该结点到右子树");
do {
count = scan.nextInt();
if(count == 1 || count == 2) {
if(parent == null) {
System.out.println("不存在父节点，请先设置父节点！");
}else {
switch (count) {
case 1:
if(parent.left != null) {
System.out.println("左子树节点不为空！");
}else {
parent.left = p;
}
break;
case 2:
if(parent.right != null) {
System.out.println("右子树节点不为空！");
}else {
parent.right = p;
}
break;
default:
System.out.println("无效参数！");
}
}
}
}while (count != 1 && count != 2);
}
}
/**
* 查找节点
* @param node
* @param data
* @return
*/
public Node find_tree_node(Node node,String data) {
Node ptr;
if(node == null) {
return null;
}else {
if(node.data.equals(data)) {
return node;
}else {
if((ptr = find_tree_node(node.left,data)) != null) {
return ptr;
}else if((ptr = find_tree_node(node.right,data)) != null) {
return ptr;
}else {
return null;
}
}
}
}
/**
* 获取左子树
* @param node
* @return
*/
public Node left_tree(Node node) {
if(node != null) {
return node.left;
}else {
return null;
}
}
/**
* 获取右子树
* @param node
* @return
*/
public Node right_tree(Node node) {
if(node != null) {
return node.right;
}else {
return null;
}
}
/**
* 判断二叉树是否为空
* @param node
* @return
*/
public boolean isEmpty(Node node) {
if(node != null) {
return false;
}else {
return true;
}
}
/**
* 得到树的深度
* @param node
* @return
*/
public int tree_length(Node node) {
int depleft,depright;
if(isEmpty(node)) {
return 0;
}else {
depleft = tree_length(node.left);
depright = tree_length(node.right);
if(depleft > depright) {
return depleft+1;
}else {
return depright+1;
}
}
}
/**
* 清空二叉树
* @param node
*/
public void clear_tree(Node node) {
if(node != null) {
clear_tree(node.left);
clear_tree(node.right);
node = null;
}
}
/**
* 得到节点数据
* @param node
*/
public String node_data(Node node) {
System.out.print(node.data+"\t");
return node.data;
}
/**
* 遍历二叉树，先序遍历
* @param node
*/
public void DLR(Node node) {
if(node != null) {
node_data(node);
DLR(node.left);
DLR(node.right);
}
}
}
测试代码：
public class TestDemo6 {
public static void main(String[] args) {
Node root = null;
BinaryTree t = new BinaryTree();
root = t.rootnode(); //设置根节点
/**
* 添加节点
*/
int i = 1;
do {
t.add_tree_node(root);
i++;
}while (i <= 5);
System.out.print("先序遍历：");
t.DLR(root);
System.out.println("\n二叉树的深度："+t.tree_length(root));
t.clear_tree(root); //清空
root = null;
}
}
请输入一个根节点数据：
A
输入二叉树节点数据:
B
请输入该节点的父节点的数据：
A
1、添加该结点到左子树
2、添加该结点到右子树
1
输入二叉树节点数据:
C
请输入该节点的父节点的数据：
A
1、添加该结点到左子树
2、添加该结点到右子树
2
输入二叉树节点数据:
D
请输入该节点的父节点的数据：
B
1、添加该结点到左子树
2、添加该结点到右子树
1
输入二叉树节点数据:
G
请输入该节点的父节点的数据：
D
1、添加该结点到左子树
2、添加该结点到右子树
1
输入二叉树节点数据:
H
请输入该节点的父节点的数据：
D
1、添加该结点到左子树
2、添加该结点到右子树
2
输入二叉树节点数据:
F
请输入该节点的父节点的数据：
C
1、添加该结点到左子树
2、添加该结点到右子树
2
输入二叉树节点数据:
E
请输入该节点的父节点的数据：
C
1、添加该结点到左子树
2、添加该结点到右子树
1
输入二叉树节点数据:
I
请输入该节点的父节点的数据：
E
1、添加该结点到左子树
2、添加该结点到右子树
2
输入二叉树节点数据:
K
请输入该节点的父节点的数据：
F
1、添加该结点到左子树
2、添加该结点到右子树
1
先序遍历：A B D G H C E I F K
二叉树的深度：4