Java树形结构的解释和用法

Java树形结构是一种可以存储元素的有层级关系的数据结构,每个元素以节点的形式存在,并且一个根节点会关联多个子节点,子节点再关联更多的子节点,以此类推。

一、树的基本概念

1、树形结构是一种递归式数据结构,它包括一个值,同时还可能包括指向其他树的引用(树是由节点(储存元素)和边(连接节点)组成的集合)

2、树形结构的特性如下: 每个节点有零个或多个子节点; 没有父节点的节点称为根节点; 每一个非根节点有且只有一个父节点; 除了根节点外,每个子节点又可以分为多个不重叠的子树.

classNode{
intdata;
Nodeleft,right;

publicNode(intitem){
data=item;
left=right=null;
}
}

二、二叉树和二叉搜索树

1、二叉树是每个节点最多只能有两个子节点的树形结构结构,一般子节点称为“左子节点”和“右子节点”。

二叉树形结构的遍历有三种方式:前序遍历、中序遍历和后序遍历。

voidprintPreorder(Nodenode){
if(node==null)
return;

//先输出当前节点的数据
System.out.print(node.data+"");

//递归打印左子节点
printPreorder(node.left);

//现在递归打印右子节点
printPreorder(node.right);
}

二叉搜索树(BST)是一种特性的二叉树:每个节点的值,都大于其左子树的所有节点的值,并且小于右子树形结构的所有节点的值。

classNode{
intkey;
Nodeleft,right;

publicNode(intitem){
key=item;
left=right=null;
}
}

classBinaryTree{
Noderoot;
voidinsert(intkey){root=insertRec(root,key);}

NodeinsertRec(Noderoot,intkey){
if(root==null){
root=newNode(key);
returnroot;
}
if(key<root.key)
root.left=insertRec(root.left,key);
elseif(key>root.key)
root.right=insertRec(root.right,key);
returnroot;
}

voidinorder(){inorderRec(root);}
voidinorderRec(Noderoot){
if(root!=null){
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
}

三、平衡二叉树形结构与红黑树形结构

1、平衡二叉搜索树是其每一个节点的两个子树的高度差最多为1的二叉搜索树,它通过旋转操作,保障树的平衡,从而优化了树的查询速度。

2、红黑树则是一种自平衡的二叉查找树,它在执行插入和删除操作的时候,通过特定的操作保持树的平衡。

以下是其特性:

(1)每个节点或是红色,或是黑色。

(2)根节点是黑色。

(3)每个叶节点(叶节点默认是空节点(NIL)或null)都是黑色的。

(4)如果一个节点是红的,则它的子节点都是黑的。

(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

classNode{
intdata;
Nodeparent;
Nodeleft;
Noderight;
intcolor;
}
publicclassRedBlackTree{

privateNoderoot;
privateNodeTNULL;

//Preorder
privatevoidpreOrderHelper(Nodenode){
if(node!=TNULL){
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}

//In-order
privatevoidinOrderHelper(Nodenode){
if(node!=TNULL){
inOrderHelper(node.left);
inOrderHelper(node.right);
}
}

//Postorder
privatevoidpostOrderHelper(Nodenode){
if(node!=TNULL){
postOrderHelper(node.left);
postOrderHelper(node.right);
}
}

//Balancethetreeafterdeletionofanode
privatevoidfixDelete(Nodex){
Nodes;
while(x!=root&&x.color==0){
if(x==x.parent.left){
s=x.parent.right;
if(s.color==1){
//case3.1
s.color=0;
x.parent.color=1;
leftRotate(x.parent);
s=x.parent.right;
}

if(s.left.color==0&&s.right.color==0){
//case3.2
s.color=1;
x=x.parent;
}else{
if(s.right.color==0){
//case3.3
s.left.color=0;
s.color=1;
rightRotate(s);
s=x.parent.right;
}

//case3.4
s.color=x.parent.color;
x.parent.color=0;
s.right.color=0;
leftRotate(x.parent);
x=root;
}
}else{
//sameas"if(x==x.parent.left)"theotherwayaround
}
}
x.color=0;
}

//Balancethetreeafterinsertionofanode
privatevoidfixInsert(Nodek){
Nodeu;
while(k.parent.color==1){
if(k.parent==k.parent.parent.right){
u=k.parent.parent.left;

//uncleisRED
if(u.color==1){
u.color=0;
k.parent.color=0;
k.parent.parent.color=1;
k=k.parent.parent;
}else{
if(k==k.parent.left){
k=k.parent;
rightRotate(k);
}
//uncleisBLACK
k.parent.color=0;
k.parent.parent.color=1;
leftRotate(k.parent.parent);
}
}else{
//mirrorimageofabovecode
//theotherwayaround
}
if(k==root){
break;
}
}
root.color=0;
}

//...
}

原创文章,作者:小蓝,如若转载,请注明出处:https://www.beidandianzhu.com/g/1047.html

(0)
小蓝的头像小蓝
上一篇 2024-12-17 14:06:46
下一篇 2024-12-17

相关推荐

  • Python爬虫返回太慢的原因及解决方法

    Python爬虫在实际应用中,有时会遇到返回速度较慢的情况。本文将从多个方面探讨Python爬虫返回太慢的原因,并给出相应的解决方法。 一、网络延迟 1、问题描述:网络延迟是指数据…

    程序猿 2025-02-09
  • Python整段代码注释快捷键

    Python作为一门流行的编程语言,具有丰富的编辑器和IDE支持。其中,注释是编写代码时的重要组成部分,可以提高代码可读性和可维护性。本文将介绍Python整段代码注释的快捷键,帮…

    程序猿 2024-12-23
  • Python闭包及其写法

    闭包是函数式编程中的一个重要概念,可以让函数封装一些数据,并且在函数返回后仍然可以访问这些数据。Python语言中也支持闭包的使用,本文将从多个方面对Python闭包及其写法进行详…

    程序猿 2025-01-18
  • Python学习笔记:从入门到进阶

    Python是一门简单易学的编程语言,具备广泛的应用领域。本文将从多个方面介绍Python学习的重要笔记,帮助读者在学习过程中更好地掌握Python编程知识。 一、Python基础…

    程序猿 2024-12-31
  • Python新手应如何学习

    对于想要学习Python编程的新手来说,选择合适的学习路径和方法是非常重要的。本文将从多个方面阐述如何高效地学习Python,帮助新手入门并建立坚实的基础。 一、选择合适的学习资源…

    程序猿 2025-01-04
  • 用Python实现优先队列

    优先队列是一种特殊的队列数据结构,其中每个元素都有一个优先级。优先级较高的元素在队列中排在前面,优先级较低的元素在队列中排在后面。在本篇文章中,我们将详细阐述如何使用Python来…

    程序猿 2024-12-17
  • Python处理字节流的重要性及方法

    在现代计算机科学中, 处理字节流是一项重要的任务。Python作为一种强大的编程语言,提供了丰富的工具和函数来处理字节流。本文将从多个角度详细阐述Python处理字节流的方法和技巧…

  • Python之禅的引用和意义

    Python之禅是Python编程语言的一种理念和指导原则,它通过简洁的语言形式传递了Python的设计哲学和价值观。本文将从多个方面详细阐述Python之禅的引用和意义。 一、简…

    程序猿 2025-01-14
  • Python解释性编程语言

    Python是一种高级、通用、解释性的编程语言。通过本文,将从多个方面详细阐述Python的解释性特点。 一、交互式编程 Python提供了交互式编程的环境,用户可以直接在Pyth…

    程序猿 2025-01-02
  • Python多进程异步并发处理

    Python多进程异步并发处理是指在Python中使用多个进程同时进行异步操作,以提高程序的运行效率和并发能力。 一、创建多个进程 在Python中,可以使用multiproces…

    程序猿 2024-12-20

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

分享本页
返回顶部