原创
用Java实现一颗简单的二叉树
温馨提示:
本文最后更新于 2018年06月14日,已超过 2,366 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我。
什么是二叉树?
实现一颗简单的二叉树
TreeNode
二叉树的结点。
package com.lzhpo.twotree;
/**
* 二叉树
*
* <p>
* Create By IntelliJ IDEA
* Author:lzhpo
* </p>
*/
public class TreeNode {
//节点的权
int value;
//左儿子
TreeNode leftNode;
//右儿子
TreeNode rightNode;
/**
* 二叉树的创建
*/
//构造方法,传入一个值
public TreeNode(int value) {
this.value = value;
}
//设置左儿子
public void setlNode(TreeNode lNode) {
this.leftNode = lNode;
}
//设置右儿子
public void setrNode(TreeNode rNode) {
this.rightNode = rNode;
}
/**
* 二叉树的遍历
*/
//前序遍历(根,左,右)
public void frontShow() {
//先遍历当前节点(根节点);
System.out.print(value);
//左节点
if(leftNode!=null)
{
leftNode.frontShow();
}
//右节点
if(rightNode!=null)
{
rightNode.frontShow();
}
}
//中序遍历(左,根,右)
public void midShow() {
//先遍历左节点
if(leftNode!=null)
{
leftNode.midShow();
}
//在遍历当前节点(根节点);
System.out.print(value);
//最后右节点
if(rightNode!=null)
{
rightNode.midShow();
}
}
//后序遍历(左,右,根)
public void afterShow() {
//先左节点
if(leftNode!=null)
{
leftNode.afterShow();
}
//在右节点
if(rightNode!=null)
{
rightNode.afterShow();
}
//最后遍历当前节点(根节点);
System.out.print(value);
}
//设置左孩子
public void setleftNode(TreeNode lNode) {
this.leftNode = lNode;
}
//设置右孩子
public void setrightNode(TreeNode rNode) {
this.rightNode = rNode;
}
/**
* 二叉树的查找
*/
//前序查找
public TreeNode frontSearch(int i) {
TreeNode target=null;
//对比当前节点的值
if(this.value==i)
{
return this;
//当前节点中的值不是要查找的
}else {
//查找左节点
if(leftNode!=null)
{
//有可能可以查到,有可能查找不到,查不到的话,target还是null
target=leftNode.frontSearch(i);
}
//如果不为空,则查找成功
if(target!=null) {
return target;
}
//查找右节点
if(rightNode!=null)
{
target=rightNode.frontSearch(i);
}
}
return target;
}
/**
* 二叉树的删除
*/
//删除二叉树的子树
public void delete(int i) {
TreeNode parent=this;
//判断左孩子
if(parent.leftNode!=null&&parent.leftNode.value==i)
{
parent.leftNode=null;
return;
}
//判断右孩子
if(parent.rightNode!=null&&parent.rightNode.value==i)
{
parent.rightNode=null;
return;
}
//如果都不是,递归检查并删除左孩子
parent=leftNode;
if(parent!=null)
{
parent.delete(i);
}
//递归检查并删除右孩子
parent=rightNode;
if(parent!=null)
{
parent.delete(i);
}
}
}
BinaryTree
实现二叉树的相关简单操作。
package com.lzhpo.twotree;
/**
* <p>
* Create By IntelliJ IDEA
* Author:lzhpo
* </p>
*/
public class BinaryTree {
//根节点
TreeNode root;
/**
* 二叉树的创建
*/
//获取根节点
public TreeNode getRoot() {
return root;
}
//设置根节点
public void setRoot(TreeNode root) {
this.root = root;
}
/**
* 二叉树的遍历
*/
//前序遍历
public void frontShow()
{
if(root!=null) {
root.frontShow();
}else
{
System.out.println("此二叉树为空");
}
}
//中序遍历
public void midShow()
{
if(root!=null) {
root.midShow();
}else
{
System.out.println("此二叉树为空");
}
}
//后序遍历
public void afterShow()
{
if(root!=null) {
root.afterShow();
}else
{
System.out.println("此二叉树为空");
}
}
/**
* 二叉树的查找
* @param i
* @return
*/
//前序查找
public TreeNode frontSearch(int i) {
return root.frontSearch(i);
}
/**
* 二叉树的删除
* @param i
*/
public void delete(int i) {
if(root.value==i)
{
root=null;
}else {
root.delete(i);
}
}
}
TestBinaryTree
main方法。
package com.lzhpo.twotree;
/**
* <p>
* Create By IntelliJ IDEA
* Author:lzhpo
* </p>
*/
public class TestBinaryTree {
public static void main(String[] args) {
/**
* 创建二叉树
*/
//创建一棵树
BinaryTree binaryTree = new BinaryTree();
//创建一个根节点
TreeNode root = new TreeNode(1);
//把根节点赋给树
binaryTree.setRoot(root);
//创建两个节点
TreeNode rootL = new TreeNode(2);
TreeNode rootR = new TreeNode(3);
//把心创建的节点设置为根节点的子节点
root.setlNode(rootL);
root.setrNode(rootR);
//为第二层的节点创建子节点
rootL.setleftNode(new TreeNode(4));
rootL.setrightNode(new TreeNode(5));
rootR.setleftNode(new TreeNode(6));
rootR.setrightNode(new TreeNode(7));
/**
* 遍历二叉树
*/
System.out.println("======================二叉树的遍历======================");
//1.前序遍历(根,左,右)
System.out.println("此二叉树的前序遍历为:");
binaryTree.frontShow();
System.out.println();
System.out.println("此二叉树的中序遍历为:");
binaryTree.midShow();
System.out.println();
System.out.println("此二叉树的后序遍历为:");
binaryTree.afterShow();
/**
* 二叉树的查找
*/
System.out.println("======================二叉树的查找======================");
TreeNode result = binaryTree.frontSearch(9);
System.out.println(result);
/**
* 二叉树删除
*/
System.out.println("======================二叉树的删除======================");
binaryTree.delete(2);
binaryTree.frontShow();
}
}
- 本文标签: Java 数据结构与算法
- 本文链接: http://www.lzhpo.com/article/69
- 版权声明: 本文由lzhpo原创发布,转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权