package other;
import java.util.Stack;
class TreeNode {
private String key;
private TreeNode lchild; //左孩子
private TreeNode rchild; //右孩子
private TreeNode parent; //双亲节点
public TreeNode(String key) {
this.key = key;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public TreeNode getLchild() {
return lchild;
}
public void setLchild(TreeNode lchild) {
this.lchild = lchild;
}
public TreeNode getRchild() {
return rchild;
}
public void setRchild(TreeNode rchild) {
this.rchild = rchild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public String toString() { // 打印出树种某个节点的信息
StringBuffer sb = new StringBuffer();
sb.append("key:" + this.key + " ");
if (this.getLchild() != null) {
sb.append(" left child:" + this.getLchild().getKey());
}
if (this.getRchild() != null) {
sb.append(" right child:" + this.getRchild().getKey());
}
return sb.toString();
}
}
public class TreeTest {
private static Stack<TreeNode> s;
private static TreeNode root;
public static TreeNode createTree(){
root = new TreeNode("6");
TreeNode l = new TreeNode("3");
TreeNode r = new TreeNode("8");
l.setParent(root);
r.setParent(root);
TreeNode ll = new TreeNode("2");
TreeNode rl = new TreeNode("7");
l.setLchild(ll);
r.setLchild(rl);
ll.setParent(l);
rl.setParent(r);
root.setLchild(l);
root.setRchild(r);
root.setParent(null);
return root;
}
public static void main(String[] args) {
// 简单的构造一个树,当然是先构造树上的每一个节点
root = createTree();
System.out.println(treeDepth(root));
// preOrderTraverse(root); // 递归先序遍历树
//
//
// //
// TreeNode finded = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
// System.out.println(finded);
//
// TreeNode finded2 = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在
// System.out.println(finded2);
// inOrderNonTraverse(root);
}
// 递归先序遍历二叉树,后序和中序相似,只是调换输出子树根节点的次序
public static void preOrderTraverse(TreeNode t) {
System.out.println("递归先序遍历");
if (t != null) {
System.out.println(t.getKey());
preOrderTraverse(t.getLchild());
preOrderTraverse(t.getRchild());
}
}
public static void inOrderNonTraverse(TreeNode t) { // 中序遍历二叉树的非递归
s = new Stack<TreeNode>();
s.clear();
s.push(t);// 根节点入栈
while (!s.isEmpty()) {
while (!s.isEmpty()&&s.peek()!= null)
s.push(s.peek().getLchild());// 向左走到尽头
s.pop();//空指针退栈,别忘了
if (!s.isEmpty()) {
TreeNode current = s.pop();
System.out.println(current.getKey());
s.push(current.getRchild());
}
}
}
// 二叉查找树,必须满足左子树的关键字小于等于根,右子树的节点大于等于根,这样中序遍历该树,可得到一个有序序列
/*
* 在二叉查找树上找关键字为key的节点,递归方法
*/
public static TreeNode treeSearchTranverse(TreeNode root, String key) {
if (root == null || root.getKey().equals(key))
return root;
if (root.getKey().compareTo(key) > 0) { // 小于根节点的关键字,肯定在左子树上
return treeSearchTranverse(root.getLchild(), key);
} else {
return treeSearchTranverse(root.getRchild(), key);
}
}
/*
* 在二叉查找树上找关键字为key的节点,非递归方法
*/
public static TreeNode treeSearchNonTranverse(TreeNode root, String key) {
while (root != null && !root.getKey().equals(key)) {
if (key.compareTo(root.getKey()) < 0) {
root = root.getLchild(); // 指向左孩子
} else {
root = root.getRchild();
}
}
return root;
}
/*
* 返回查找树中的最小关键字,只需一直沿着节点的left指针即可
*/
public static TreeNode TreeMin(TreeNode x) {
while (x.getLchild() != null) {
x = x.getLchild();
}
return x;
}
/*
* 返回查找树中的最大关键字,只需一直沿着节点的right指针即可
*/
public static TreeNode TreeMax(TreeNode x) {
while (x.getRchild() != null) {
x = x.getRchild();
}
return x;
}
/*
* 返回中序遍历查找树时节点x的后继,无需对关键字进行比较,因为二叉查找树的结构,x的后继就是具有大于x.getKey()的关键字中最小者的那个节点
*/
public static TreeNode TreeSuccessor(TreeNode x) {
if (x.getRchild() != null) //根据中序遍历
return TreeMin(x.getRchild());
TreeNode y = x.getParent();
while(y!=null&&x==y.getRchild()){ //x是y的右孩子或x是根节点???
x=y;
y=y.getParent();
}
return y; //x是y的左孩子
}
/*
* 在二叉查找树中插入一个节点z,使之仍然保持查找树的特性???????????不懂,指针x跟踪路径,从根节点开始,下降,而y始终指向x的父节点。
*/
public static void insertNode(TreeNode z){
TreeNode y =null;
TreeNode x = getRoot(); //根的父节点为空
while(x!=null){
y=x;
if(z.getKey().compareTo(x.getKey())<0) x=x.getLchild();
else x=x.getRchild();
}
z.setParent(y); //插入的z节点的双亲节点
if(y==null){
setRoot(z);//当前树为空树,设置根节点
}
else if(z.getKey().compareTo(y.getKey())<0){
y.setLchild(z);
}
else y.setRchild(z);
}
public static TreeNode getRoot() {
return root;
}
public static void setRoot(TreeNode root) {
TreeTest.root = root;
}
/*
* 在二叉查找树中删除一个节点z,使之仍然保持查找树的特性
*/
public static TreeNode deleteNode(TreeNode z){
TreeNode x,y;
if(z.getLchild()==null||z.getRchild()==null){
y=z;
}
else y = TreeSuccessor(z);
if(y.getLchild()!=null){
x=y.getLchild();
}
else x = y.getRchild();
if(x!=null){
x.setParent(y.getParent());
}
if(y.getParent()==null){
setRoot(x);
}
else if(y==y.getParent().getLchild()){
y.getParent().setLchild(x);
}
else{
y.getParent().setRchild(x);
}
if(y!=z){
z.setKey(y.getKey());
}
return y;
}
public static int treeDepth(TreeNode t){ //计算树的深度
TreeNode lchild,rchild;
int lchildDepth,rchildDepth;
if(t==null) return 0;
else {
System.out.println("树节点不为空时:");
lchild = t.getLchild();
rchild = t.getRchild();
lchildDepth = treeDepth(lchild);
rchildDepth = treeDepth(rchild);
return lchildDepth>rchildDepth?(lchildDepth+1):(rchildDepth+1);
}
}
}
分享到:
相关推荐
数据结构-二叉树Java实现及其遍历算法,代码示例中实现了中序遍历,简单易学。
在Java中实现二叉树,我们可以自定义一个类来表示树节点,并通过节点之间的连接来构建整个树形结构。这篇博客主要讨论了如何在Java中实现二叉树的基本操作,包括递归和非递归方式的三种遍历顺序:前序遍历、中序遍历...
平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,平衡二叉树Java实现,
总结来说,理解和掌握二叉树以及如何用JAVA实现它们是成为优秀程序员的关键一步。通过实践,你可以更深入地了解数据结构的精髓,提升算法设计能力,并为解决复杂问题打下坚实基础。对于初学者,可以从简单的二叉树...
本文将深入探讨“数据结构 二叉树 java图形界面实现”这一主题,主要围绕二叉树的基本概念、常见操作以及如何在Java环境中结合图形界面进行实现。 首先,二叉树是一种非线性的数据结构,每个节点最多有两个子节点,...
代码实现: 二叉树的查找、插入、删除和输出根节点到当前节点的路径 二叉树的前序遍历,中序遍历和后续遍历 TreeNode.java --定义树节点 Mytree.java----创建树结构和上述功能函数 TestTree.java --测试上述的功能
java二叉树实现 (简单实现,入门用) /**创建二叉树*/ public BinaryTree createTree(String treeStr); /**寻找结点*/ public BinaryTree findNode(BinaryTree tree ,char sign); /**找所给结点的左子树*/ ...
后序遍历的Java实现通常使用栈来辅助操作: ```java public void postOrderTraversal(TreeNode node) { if (node == null) return; Stack<TreeNode> stack = new Stack(); TreeNode prev = null; while (node...
java实现二叉树非递归前序中序后序遍历
在本项目中,“基于JAVA开发的二叉树课程设计与实现”主要涵盖了计算机科学中的数据结构和算法领域,特别是关于二叉树的理论知识、Java编程语言的应用以及软件工程的基本实践。二叉树是一种重要的非线性数据结构,...
在Java中动态实现二叉树,即在运行时根据需要创建、更新和操作树结构,这涉及到对数据结构和Swing组件的深入理解。 首先,二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,分别称为左孩子和右孩子。...
下面是一些常见的二叉树操作的Java实现示例: 1. **创建二叉树**: 创建二叉树通常从空节点开始,通过插入节点来构造。例如,插入新节点的函数可能如下: ```java public void insert(int val) { root = insert...
编程实现如下功能: 1、假设二叉树的结点值是字符,根据输入的一颗二叉树的标明了空子树的完整先根遍历序列,建立一棵以二叉链表表示的二叉树。 2、对二叉树进行先根、中根和后根遍历操作,并输出遍历序列,同时观察...
总之,Java实现二叉树的最佳方法依赖于对二叉树性质的深入理解以及对Java语言特性的熟练应用。递归构建和遍历是实现二叉树的两个核心方面,它们共同构建了复杂二叉树算法的基石。在实际应用中,还需要考虑树结构的...
数据结构二叉树(Binary Tree)的Java实现; 包括最基本的清空方法/判断为空方法/求树的深度的方法/获得父结点的方法/获得左/右兄弟结点的方法/递归先序/中序/后序遍历二叉树的方法;
文档中是我自己实现的用java语言实现(1)判断给定的二叉树是否平衡;(2)二叉树插入新数据后,如果失衡自我旋转调整的方法。
1:构造一个二叉树 2:二叉树前序遍历(递归) 3:二叉树中序遍历(递归) 4:二叉树后续遍历(递归) 5:二叉树前序遍历(非递归) 6:二叉树中序遍历(非递归) 7:二叉树后序遍历(非递归)
在"二叉树java源码完整"这个项目中,我们可以期待找到用Java实现的二叉树类及其相关方法。源码通常会包括以下部分: 1. **基础定义**:首先,会有一个类(例如`BinaryTree`或者`Node`)来表示二叉树的节点,每个...
在这个Java实现中,我们可以看到一个完整的二叉树可视化系统,包括四个关键的Java源文件:BinaryNode、Show1_12、Display_Tree和TreeControl。 1. **BinaryNode.java**: 这个文件代表二叉树的基本节点。在Java中,...