二叉树
1、定义:树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构。
二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”和“右子树”。
链表是一种特殊的树。
2、构建规则:左子树<右子树
3、组成元素:根节点 、边、左(右)子树
二叉树的遍历方式
1、前序 、先序 :根节点 -->左-->右 访问根结点的操作发生在遍历其左右子树之前。
2、中序 :左 -->根节点-->右 访问根结点的操作发生在遍历其左右子树之中(间)。
3、后序 :左 -->右-->根节点 访问根结点的操作发生在遍历其左右子树之后。
4、层次
5、
6、广度
1.中序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
⑴遍历左子树;
⑵访问根结点;
⑶遍历右子树。
2.先序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
⑴ 访问根结点;
⑵ 遍历左子树;
⑶ 遍历右子树。
3.后序遍历得递归算法定义:
若二叉树非空,则依次执行如下操作:
⑴遍历左子树;
⑵遍历右子树;
⑶访问根结点。
练习:
1、构建树结构
2、分别实现 前、中、后序的遍历
结点类:
public class Node {
// 节点存储的数据
private Object date;
// 左节点的地址
private Node left;
// 右节点的地址
private Node right;
// 返回节点处的数据
public Object getDate() {
return date;
}
// 设置节点处的数据
public void setDate(Object date) {
this.date = date;
}
// 返回左节点
public Node getLeft() {
return left;
}
// 设置左节点
public void setLeft(Node left) {
this.left = left;
}
// 返回右节点
public Node getRight() {
return right;
}
// 设置右节点
public void setRight(Node right) {
this.right = right;
}
// 构造函数
public Node() {
super();
}
// 构造函数
public Node(Object date) {
super();
this.date = date;
}
// 构造函数
public Node(Object date, Node left, Node right) {
this.date = date;
this.left = left;
this.right = right;
}
}
树类:
public class NodeTree {
// 定义一个根节点
private Node root;
/**
* 添加节点 的方法
* @param node 要添加的代码
*/
public void add(Node node){
if(root==null){
root = node;
}
else{
querynode1(root,node);
}
}
/**
* 查找节点添加位置并添加的方法
* @param node1 根节点
* @param node2 要添加的节点
*/
public void querynode1(Node node1,Node node2){
if((int)node2.getDate()<(int)node1.getDate()){
if(node1.getLeft()==null){
node1.setLeft(node2);
}
else{
querynode1(node1.getLeft(),node2);
}
}
else{
if(node1.getLeft()==null){
node1.setLeft(node2);
}
else if(node1.getRight()==null){
node1.setRight(node2);
}
else{
querynode1(node1.getRight(),node2);
}
}
}
/**
* 前序遍历
* @param node 根节点
*/
public void NLR(Node node){
// 访问根节点
System.out.print(node.getDate()+"\t");
// 访问左子树
if(node.getLeft()!=null){//左子树不为空
NLR(node.getLeft());
}
// 访问右子树
if(node.getRight()!=null){//右子树不为空
NLR(node.getRight());
}
}
/**
* 中序遍历
* @param node 根节点
*/
public void LNR(Node node){
// 遍历左子树
if(node.getLeft()==null){
System.out.print(node.getDate()+"\t");
}
else{
LNR(node.getLeft());
}
// 遍历根节点
if(node.getLeft()!=null){
System.out.print(node.getDate()+"\t");
}
// 遍历右子树
if(node.getRight()!=null){
LNR(node.getRight());
}
}
/**
* 后序遍历
* @param node 根节点
*/
public void LRN(Node node){
// 遍历左树
if(node.getLeft()==null){
System.out.print(node.getDate()+"\t");
}
else{
LRN(node.getLeft());
}
// 遍历右树
if(node.getRight()!=null){
LRN(node.getRight());
}
// 遍历根节点
if(node.getLeft()!=null){
System.out.print(node.getDate()+"\t");
}
}
public void delete(Node node){
// 遍历查找
// 访问根节点
System.out.print(node.getDate()+"\t");
// 访问左子树
if(node.getLeft()!=null){//左子树不为空
NLR(node.getLeft());
}
// 访问右子树
if(node.getRight()!=null){//右子树不为空
NLR(node.getRight());
}
}
}
主函数:
public class Manager {
/**
* @param args
*/
public static void main(String[] args) {
NodeTree nt = new NodeTree();
Node[] node = new Node[8];
node[0] = new Node(100);
node[1] = new Node(90);
node[2] = new Node(120);
node[3] = new Node(80);
node[4] = new Node(95);
node[5] = new Node(110);
node[6] = new Node(125);
node[7] = new Node(85);
for(int i =0; i<node.length;i++){
nt.add(node[i]);
}
// 前序遍历
System.out.println("前序遍历输出~~~~~~~~~~~");
nt.NLR(node[0]);
System.out.println();
// 中序遍历
// System.out.println("中序遍历输出~~~~~~~~~~~");
// nt.LNR(node[0]);
// System.out.println();
// 后序遍历
// System.out.println("后序遍历输出~~~~~~~~~~~");
// nt.LRN(node[0]);
// System.out.println();
// nt.delete(node[3]);
}
}
分享到:
相关推荐
二叉树、平衡二叉树(如AVL树和红黑树)、B树和B+树等是常见的树型数据结构,广泛应用于文件系统、数据库索引等场景。 8. **图(Graph)**:图由节点(顶点)和连接节点的边构成,可以表示各种复杂的关系。图的遍历...
《实战应用Java算法分析与设计》视频教程深入浅出地讲解了链表、二叉树、哈夫曼树、图以及动态规划等核心数据结构与算法,并通过Java语言实现这些理论知识的应用。本文将对这一系列视频中的知识点进行总结,旨在帮助...
这本书深入浅出地解析了如何有效地思考、设计和实现代码,是许多程序员在求职过程中不可或缺的参考资料。 在编码面试中,数据结构和算法是核心部分。数据结构包括数组、链表、栈、队列、树(如二叉树、平衡树)、图...
对于深度为\( h \)的完全二叉树,它至少拥有\( 2^{h-1} \)个结点,这是因为最浅的一层至少有一个结点;而最深的一层可以只有1个结点。完全二叉树的最大结点数则取决于是否除了最后一层外的所有层都是满的。因此,当...
### 树形DP浅略总结 #### 一、树形DP概述 树形DP,即在树状结构上的动态规划,是一种重要的算法技术。与线性DP不同的是,树形DP考虑的问题通常涉及树结构中的节点及其之间的关系。在解决这类问题时,有两种基本的...
《算法与数据结构考研第二版》是一本专为准备计算机科学考研的学生编写的教材,它深入浅出地探讨了算法和数据结构的核心概念,并结合近年来的考研真题进行了详尽的解析。这本书不仅覆盖了数据结构的基础知识,还涵盖...
标题“浅谈一些树形问题_高胜寒.ppt”主要涵盖了树形数据结构在解决计算机科学问题中的重要性及应用。这篇文档可能是一个讲座或课程的幻灯片,作者高胜寒通过江苏省常州高级中学的平台分享了关于树形问题的深入见解...
这份"数据结构 PPT讲义"源自著名计算机科学家严蔚敏教授,他在清华大学的教学资源,以其清晰的讲解和深入浅出的实例而广受欢迎。严蔚敏教授的数据结构教程以C语言为编程工具,使得学生能够更好地理解抽象数据类型的...
哈弗曼编码的基本原理是构建一棵特殊的二叉树,称为哈弗曼树或最优二叉树。 哈弗曼树的构建过程分为以下几个步骤: 1. **建立初始节点**:将每个需要编码的字符视为一个带权(权重即字符出现的频率)的叶子节点。 ...
《LeetCode算法详解》这份资料是为编程爱好者和求职者准备的一份宝贵资源,它深入浅出地解析了LeetCode平台上的各类算法问题。LeetCode是一个广受欢迎的在线平台,它提供了大量的编程挑战,旨在帮助用户提升算法技能...
严蔚敏教授的《数据结构》一书,是该领域的经典教材,以其深入浅出的讲解和丰富的实例深受读者喜爱。配套实现程序则为理论知识提供了实践平台,帮助学习者更直观地理解各种数据结构的运作机制和算法的实现细节。 1....
"c语言常用程序代码(由浅到深)"这个主题涵盖了从C语言的基础概念到高级特性的全面实践,是学习C语言的一个理想资源。下面我们将详细探讨其中可能包含的知识点。 1. **基础语法**:C语言的学习始于基本语法,包括...
4. **树结构**:层次关系的数据表示,如二叉树、平衡二叉树(AVL树、红黑树)、B树和B+树等,广泛应用于搜索算法、文件系统和数据库索引。 5. **图**:由顶点和边构成的抽象结构,可以用来模拟各种复杂关系,如网络...
这本书深入浅出地讲解了算法和数据结构的基础知识,旨在提升读者的编程能力和解决实际问题的能力。 首先,书中详细介绍了基础算法,包括排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序以及堆排序,...
书中不仅深入浅出地介绍了各种数据结构的概念和算法,还提供了丰富的配套程序,帮助读者通过实践来理解和掌握这些理论知识。 压缩包中的"数据结构(C语言版)".严蔚敏_吴伟民版本配套程序,包含了书中各个章节的示例...
邓俊辉教授的《数据结构(C++语言版)第三版》是一本深入浅出的数据结构教材,特别适合C++编程者学习。该书以其详尽的讲解和丰富的实例,深受广大读者喜爱。 本书首先介绍了数据结构的基本概念,包括数组、链表、栈...
字符出现频率越高,其对应的叶子节点在树中的深度越浅,编码长度越短。 2. 构建哈夫曼树: 构建哈夫曼树的过程分为两步:首先,将所有字符及其频率作为带权节点放入优先队列(通常使用最小堆实现);然后,每次从...
严蔚敏版的数据结构讲义是中国计算机专业学生广泛使用的一本教材,以其深入浅出的讲解和丰富的实例而备受赞誉。这份讲义主要涵盖了线性结构、树形结构、图状结构、查找与排序等基本概念和算法。 1. 线性结构:线性...
二叉树是最常见的一种,包括完全二叉树、满二叉树、平衡二叉树(如AVL树、红黑树)。讲义将介绍树的各种操作,如查找、插入、删除。 5. **图**:用于表示对象之间的关系,如网络路由、社交网络等。图的遍历(深度...