关于二叉树的基本性质和结构特征，在此不做详细说明，因为网上的文章非常多，可以查阅
-
本文主要以泛型实现链式二叉树的基本方法，包括：
1. 添加结点
2. 查找结点
3. 计算深度
4. 清空子树
5. 前序遍历
6. 中序遍历
7. 后序遍历
结构示意图
二叉树.png
结果.PNG
结点类 --- Node.java
package tree;
/**
* Created by noonbiteun
* Date: 2017/8/10
*/
public class Node<T> {
private T data; //数据
private Node<T> left; //左子树
private Node<T> right; //右子树
private Node<T> parent; //父结点
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public Node<T> getParent() {
return parent;
}
public void setParent(Node<T> parent) {
this.parent = parent;
}
//清空结点
public void clear() {
left = null;
right = null;
parent = null;
}
}
初始化二叉树
public Node<T> initTree(T data) {
System.out.println("初始化树结构...数据类型为：" + data.getClass());
rootNode = new Node<>();
rootNode.setData(data);
rootNode.setParent(null);
rootNode.setLeft(null);
rootNode.setRight(null);
return rootNode;
}
添加结点
//明确父结点的情况
public void addTreeNode(Node<T> parent, T data, boolean lr) {
Node<T> node = new Node<>();
node.setParent(parent);
node.setData(data);
node.setLeft(null);
node.setRight(null);
if (lr) {
parent.setLeft(node);
} else {
parent.setRight(node);
}
}
//不明确父结点的情况，只知道父结点的数据
public void addTreeNode(T parentData, T data, boolean lr) {
Node<T> parent = findTreeNode(rootNode, parentData);
if (parent == null) {
System.out.println("添加结点错误，无数据为 " + parentData + " 的父结点");
return;
}
addTreeNode(parent, data, lr);
}
查找结点
//从treeNode结点开始查找数据为data的结点
public Node<T> findTreeNode(Node<T> treeNode, T data) {
if (treeNode == null || data == null) {
return null;
}
Node<T> ptr;
if (treeNode.getData().equals(data)) {
return treeNode;
} else {
ptr = findTreeNode(treeNode.getLeft(), data);
if (ptr != null) {
return ptr;
}
ptr = findTreeNode(treeNode.getRight(), data);
if (ptr != null) {
return ptr;
}
return null;
}
}
计算深度
//计算深度
public int getTreeDepth(Node<T> treeNode) {
int depLeft, depRight;
if (treeNode == null) {
return 0;
} else {
depLeft = getTreeDepth(treeNode.getLeft());
depRight = getTreeDepth(treeNode.getRight());
return depLeft > depRight ? depLeft+1 : depRight+1;
}
}
清空子树
//清空treeNode的子树
public void clearTree(Node<T> treeNode) {
if (treeNode != null) {
clearTree(treeNode.getLeft());
clearTree(treeNode.getRight());
treeNode.clear();
}
}
先序遍历、中序遍历、后序遍历
//先序遍历
public void DLRTree(Node<T> treeNode) {
if (treeNode != null) {
System.out.println(treeNode.getData());
DLRTree(treeNode.getLeft());
DLRTree(treeNode.getRight());
}
}
//中序遍历
public void LDRTree(Node<T> treeNode) {
if (treeNode != null) {
LDRTree(treeNode.getLeft());
System.out.println(treeNode.getData());
LDRTree(treeNode.getRight());
}
}
//后序遍历
public void LRDTree(Node<T> treeNode) {
if (treeNode != null) {
LRDTree(treeNode.getLeft());
LRDTree(treeNode.getRight());
System.out.println(treeNode.getData());
}
}
整合：LinkTree.java 链式二叉树类
package tree;
import java.util.Scanner;
/**
* Created by noonbiteun
* Date: 2017/8/10
*/
public class LinkTree<T> {
private Node<T> rootNode;
public Node<T> getRootNode() {
return rootNode;
}
public Node<T> initTree(T data) {
System.out.println("初始化树结构...数据类型为：" + data.getClass());
rootNode = new Node<>();
rootNode.setData(data);
rootNode.setParent(null);
rootNode.setLeft(null);
rootNode.setRight(null);
return rootNode;
}
//明确父结点的情况
public void addTreeNode(Node<T> parent, T data, boolean lr) {
Node<T> node = new Node<>();
node.setParent(parent);
node.setData(data);
node.setLeft(null);
node.setRight(null);
if (lr) {
parent.setLeft(node);
} else {
parent.setRight(node);
}
}
//不明确父结点的情况，只知道父结点的数据
public void addTreeNode(T parentData, T data, boolean lr) {
Node<T> parent = findTreeNode(rootNode, parentData);
if (parent == null) {
System.out.println("添加结点错误，无数据为 " + parentData + " 的父结点");
return;
}
addTreeNode(parent, data, lr);
}
//从treeNode结点开始查找数据为data的结点
public Node<T> findTreeNode(Node<T> treeNode, T data) {
if (treeNode == null || data == null) {
return null;
}
Node<T> ptr;
if (treeNode.getData().equals(data)) {
return treeNode;
} else {
ptr = findTreeNode(treeNode.getLeft(), data);
if (ptr != null) {
return ptr;
}
ptr = findTreeNode(treeNode.getRight(), data);
if (ptr != null) {
return ptr;
}
return null;
}
}
public Node<T> getLeftNode(Node<T> treeNode) {
if (treeNode != null) {
return treeNode.getLeft();
} else {
return null;
}
}
public Node<T> getRightNode(Node<T> treeNode) {
if (treeNode != null) {
return treeNode.getRight();
} else {
return null;
}
}
//计算深度
public int getTreeDepth(Node<T> treeNode) {
int depLeft, depRight;
if (treeNode == null) {
return 0;
} else {
depLeft = getTreeDepth(treeNode.getLeft());
depRight = getTreeDepth(treeNode.getRight());
return depLeft > depRight ? depLeft+1 : depRight+1;
}
}
public boolean isEmptyTree() {
return rootNode == null;
}
public void clearTree(Node<T> treeNode) {
if (treeNode != null) {
clearTree(treeNode.getLeft());
clearTree(treeNode.getRight());
treeNode.clear();
}
}
//先序遍历
public void DLRTree(Node<T> treeNode) {
if (treeNode != null) {
System.out.println(treeNode.getData());
DLRTree(treeNode.getLeft());
DLRTree(treeNode.getRight());
}
}
//中序遍历
public void LDRTree(Node<T> treeNode) {
if (treeNode != null) {
LDRTree(treeNode.getLeft());
System.out.println(treeNode.getData());
LDRTree(treeNode.getRight());
}
}
//后序遍历
public void LRDTree(Node<T> treeNode) {
if (treeNode != null) {
LRDTree(treeNode.getLeft());
LRDTree(treeNode.getRight());
System.out.println(treeNode.getData());
}
}
}
测试类： LinkTreeTest.java
package tree;
/**
* Created by noonbiteun
* Date: 2017/8/10
*/
public class LinkTreeTest {
private static final boolean left = true;//添加到左子树
private static final boolean right = false;//添加到右子树
public static void main(String[] args) {
LinkTree<String> linkTree = new LinkTree<>();
linkTree.initTree("a");
/*
* 隐式添加结点，不用自己new Node出来，直接往已知结点后加
* */
linkTree.addTreeNode("a", "b", left);
linkTree.addTreeNode("a", "c", right);
linkTree.addTreeNode("b", "d", left);
linkTree.addTreeNode("b", "e", right);
linkTree.addTreeNode("e", "g", left);
linkTree.addTreeNode("e", "h", right);
linkTree.addTreeNode("c", "f", right);
/*
* 显式添加结点，自己链接各个node
* */
/*Node<String> b = new Node<>();
b.setData("b");
Node<String> c = new Node<>();
c.setData("c");
Node<String> d = new Node<>();
d.setData("d");
Node<String> e = new Node<>();
e.setData("e");
Node<String> f = new Node<>();
f.setData("f");
Node<String> g = new Node<>();
g.setData("g");
Node<String> h = new Node<>();
h.setData("h");*/
System.out.println();
System.out.println("先序遍历：");
linkTree.DLRTree(linkTree.getRootNode());
System.out.println();
System.out.println("中序遍历：");
linkTree.LDRTree(linkTree.getRootNode());
System.out.println();
System.out.println("后序遍历：");
linkTree.LRDTree(linkTree.getRootNode());
System.out.println();
System.out.println("二叉树深度："+ linkTree.getTreeDepth(linkTree.getRootNode()));
}
}
运行结果：
运行结果
