Java二叉树的实现（含各种方法）
程序员文章站
2024-01-15 20:27:28
...
数据结构：二叉树
此文章包含建立二叉树，遍历二叉树，和二叉树的各种方法的实现与调用，适合萌新小白阅读加深对二叉树的理解。
此文章为作者原创 禁止转载 侵权必究
代码如下：
/**
* 二叉树方法的各种实现
*/
import java.util.ArrayList;
import java.util.concurrent.LinkedBlockingDeque;
public class BinaryTreeDemo2 {
//二叉树节点
static class BinaryTreeNode {
private String data; //数据
private BinaryTreeNode leftChild; //左孩子
private BinaryTreeNode rightChild; //右孩子
BinaryTreeNode(String value) {
data = value;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
//二叉树
static class BinaryTree {
private BinaryTreeNode root;
//初始化二叉树
public BinaryTree() {
}
public BinaryTree(BinaryTreeNode root) {
this.root = root;
}
public void setRoot(BinaryTreeNode root) {
this.root = root;
}
public BinaryTreeNode getRoot() {
return root;
}
//清空树
public void clear() {
clear(root);
}
//二叉树的查找算法
public BinaryTreeNode searchNode(String value) {
BinaryTreeNode x = new BinaryTreeNode(value);
if (root != null) {
if (root.getData().equals(x.getData())) //对根节点进行判断
return root;
else {
BinaryTreeNode lresult = searchNode(root.getLeftChild(), x); //查找左子树
//若在左子树中查找到值为x的结点，则返回该结点；否则，在右子树中查找该结点并返回结果
return lresult != null ? lresult : searchNode(root.getRightChild(), x);
}
}
return null;
}
//二叉树的查找算法
private BinaryTreeNode searchNode(BinaryTreeNode root, BinaryTreeNode x) {
if (root != null) {
if (root.getData().equals(x.getData())) //对根节点进行判断
return root;
else {
BinaryTreeNode lresult = searchNode(root.getLeftChild(), x); //查找左子树
//若在左子树中查找到值为x的结点，则返回该结点；否则，在右子树中查找该结点并返回结果（地址）
return lresult != null ? lresult : searchNode(root.getRightChild(), x);
}
}
return null;
}
//判断二叉树是否为空
public boolean isEmpty() {
return root == null;
}
//获取二叉树的高度
public int height() {
return height(root);
}
//获取二叉树的节点数
public int size() {
return size(root);
}
//完整二叉树打印
public void fullPrint() {
ArrayList<String> arrayList = new ArrayList<String>();
if (root == null) {
return;
}
LinkedBlockingDeque<BinaryTreeNode> queue = new LinkedBlockingDeque<BinaryTreeNode>();
queue.addFirst(root);
while (!queue.isEmpty()) {
BinaryTreeNode curNode = queue.pollLast();
arrayList.add(curNode.getData());
if (curNode.getLeftChild() == null && curNode.getRightChild() == null) {
continue;
}
if (curNode.getLeftChild() != null) {
queue.addFirst(curNode.getLeftChild());
} else {
queue.addFirst(new BinaryTreeNode(null));
}
if (curNode.getRightChild() != null) {
queue.addFirst(curNode.getRightChild());
} else {
queue.addFirst(new BinaryTreeNode(null));
}
}
System.out.println("完整二叉树打印" + arrayList);
}
//压缩打印
public void reducePrint() {
ArrayList<String> arrayList = new ArrayList<String>();
if (root == null) {
return;
}
LinkedBlockingDeque<BinaryTreeNode> queue = new LinkedBlockingDeque<BinaryTreeNode>();
queue.addFirst(root);
while (!queue.isEmpty()) {
BinaryTreeNode curNode = queue.pollLast();
arrayList.add(curNode.getData());
if (curNode.getLeftChild() != null) {
queue.addFirst(curNode.getLeftChild());
}
if (curNode.getRightChild() != null) {
queue.addFirst(curNode.getRightChild());
}
}
System.out.println("压缩二叉树打印" + arrayList);
}
//给某个节点插入左节点
public void insertLeft(BinaryTreeNode parent, BinaryTreeNode newNode) {
parent.setLeftChild(newNode);
}
//给某个节点插入右节点
public void insertRight(BinaryTreeNode parent, BinaryTreeNode newNode) {
parent.setRightChild(newNode);
}
//获取某个节点的左子树
public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
return node.getLeftChild();
}
//获取某个节点的右子树
public BinaryTreeNode getRightTree(BinaryTreeNode node) {
return node.getRightChild();
}
//查找node节点在二叉树中的父节点
public BinaryTreeNode getParent(BinaryTreeNode node) {
return (root == null || root == node) ? null : getParent(root, node);
}
//前跟遍历
public void PreOrder(BinaryTreeNode node) {
if (node != null) {
System.out.print(node.getData() + " "); //先访问根节点
PreOrder(node.getLeftChild()); //先根遍历左子树
PreOrder(node.getRightChild()); //先根遍历右子树
}
}
//中根遍历
public void InOrder(BinaryTreeNode node) {
if (node != null) {
InOrder(node.getLeftChild()); //中根遍历左子树
System.out.print(node.data + " "); //访问根节点
InOrder(node.getRightChild()); //中根遍历右子树
}
}
//后根遍历
public void PostOrder(BinaryTreeNode node) {
if (node != null) {
PostOrder(node.getLeftChild()); //后根遍历左子树
PostOrder(node.getRightChild()); //后根遍历右子树
System.out.print(node.getData() + " "); //访问根节点
}
}
/**
* 二叉树的清空：
* 首先提供一个清空以某个节点为根节点的子树的方法，既递归地删除每个节点；
* 接着提供一个删除树的方法，直接通过第一种方法删除到根节点即可
*/
//清除某个子树的所有节点
private void clear(BinaryTreeNode node) {
if (node != null) {
clear(node.getLeftChild());
clear(node.getRightChild());
node = null; //删除节点
}
}
/**
* 求二叉树的高度：
* 首先要一种获取以某个节点为子树的高度的方法，使用递归调用。
* 如果一个节点为空，那么这个节点肯定是一颗空树，高度为0；
* 如果不为空，那么我们要遍历地比较它的左子树高度和右子树高度，
* 高的一个为这个子树的最大高度，然后加上自己本身的高度就是了
* 获取二叉树的高度，只需要调用第一种方法，即传入根节点
*/
//获取以某节点为子树的高度
private int height(BinaryTreeNode node) {
if (node == null) {
return 0; //递归结束，空子树高度为0
} else {
//递归获取左子树高度
int l = height(node.getLeftChild());
//递归获取右子树高度
int r = height(node.getRightChild());
//高度应该算更高的一边，（+1是因为要算上自身这一层）
return l > r ? (l + 1) : (r + 1);
}
}
/**
* 求二叉树的节点数：
* 求节点数时，我们看看获取某个节点为子树的节点数的实现。
* 首先节点为空，则个数肯定为0；
* 如果不为空，那就算上这个节点之后继续递归所有左右子树的子节点数，
* 全部相加就是以所给节点为根的子树的节点数
* 如果求二叉树的节点数，则输入根节点即可
*/
public int size(BinaryTreeNode node) {
if (node == null) {
return 0; //如果节点为空，则返回节点数为0
} else {
//计算本节点 所以要+1
//递归获取左子树节点数和右子树节点数，最终相加
return 1 + size(node.getLeftChild()) + size(node.getRightChild());
}
}
/**
* 判断两树是否相等:
*/
public boolean isEqual(BinaryTree T1) {
if (T1 == null && root == null) {
return true;
}
if (T1 != null && root != null)
if (T1.getRoot().getData().equals(root.getData()))
if (isEqual(T1.getRoot().leftChild, root.leftChild))
if (isEqual(T1.getRoot().rightChild, root.rightChild))
return true;
return true;
}
private boolean isEqual(BinaryTreeNode T1, BinaryTreeNode T2) {
if (T1 == null && T2 == null) {
return true;
}
if (T1 != null && root != null)
if (T1.getData().equals(root.getData()))
if (isEqual(T1.leftChild, T2.leftChild))
if (isEqual(T1.rightChild, T2.rightChild))
return true;
return true;
}
//node节点在subTree子树中的父节点
private BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
if (subTree == null) {
return null; //如果是空子树，则没有父节点
}
if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {
return subTree; //如果子树的根节点的左右孩子之一是待查节点，则返回子树的根节点
}
BinaryTreeNode parent = null;
if (getParent(subTree.getLeftChild(), node) != null) {
parent = getParent(subTree.getLeftChild(), node);
return parent;
} else {
//递归左右子树
return getParent(subTree.getRightChild(), node);
}
}
}
public static void main(String[] args) {
//二叉树
BinaryTree tree = new BinaryTree();
BinaryTree treeplus = new BinaryTree();
//创建节点
BinaryTreeNode a = new BinaryTreeNode("a");
BinaryTreeNode b = new BinaryTreeNode("b");
BinaryTreeNode c = new BinaryTreeNode("c");
BinaryTreeNode d = new BinaryTreeNode("d");
BinaryTreeNode e = new BinaryTreeNode("e");
BinaryTreeNode f = new BinaryTreeNode("f");
BinaryTreeNode g = new BinaryTreeNode("g");
BinaryTreeNode h = new BinaryTreeNode("h");
//构建二叉树
tree.setRoot(a);
a.setLeftChild(b);
a.setRightChild(c);
b.setLeftChild(d);
c.setLeftChild(e);
c.setRightChild(f);
e.setLeftChild(h);
d.setLeftChild(g);
/**
* a
* / \
* b c
* / /\
* d e f
* / /
* g h
*/
//第二个二叉树
treeplus.setRoot(a);
a.setLeftChild(b);
b.setLeftChild(c);
b.setRightChild(d);
c.setLeftChild(e);
c.setRightChild(f);
e.setLeftChild(h);
d.setLeftChild(g);
/**
* a
* /
* b
* / \
* c d
* / \
* e f
* / /
* h g
*/
//前序遍历
tree.PreOrder(tree.getRoot());
System.out.println(" ");
//中根遍历
tree.InOrder(tree.getRoot());
System.out.println(" ");
//后序遍历
tree.PostOrder(tree.getRoot());
System.out.println(" ");
tree.size(a);
//完整二叉树打印
tree.fullPrint();
//二叉树个数
System.out.println("二叉树个数：" + tree.size());
//二叉树高度
System.out.println("二叉树高度：" + tree.height());
//查找二叉树
BinaryTreeNode result = tree.searchNode("g");
System.out.println("查询结果：" + result);//返回节点的地址
result = tree.searchNode("z");
System.out.println("查询结果：" + result);
//判断两棵树是否相等
System.out.println("两棵树是否相等" + tree.isEqual(treeplus));
}
}
运行结果如下：
喜欢我的话请一键三连噢宝贝们~
上一篇： php读取csv文件类
下一篇： php GUID生成函数和类_PHP