二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。
两种遍历:
递归遍历和层次遍历.
前序:根左右
中序:左根右
后序:左右根
public class Tree
{
public Tree mLeft;
public Tree mRight;
private Data mData;
public List<Tree> treeList = new ArrayList<Tree>();
public static final int MAX = 40;
// 层次遍历时保存各个节点
Tree[] elements = new Tree[MAX];
// 层次遍历时队首
int front;
// 层次遍历时队尾
int rear;
public Tree(Tree left, Tree right, Data data)
{
this.mLeft = left;
this.mRight = right;
this.mData = data;
}
public Tree(Tree left, Tree right, String data)
{
this.mLeft = left;
this.mRight = right;
this.mData = new Data(data);
}
// 前序遍历,根左右
public void preOrder(Tree parent)
{
if (parent == null)
return;
System.out.print(parent.mData.desc + " ");
preOrder(parent.mLeft);
preOrder(parent.mRight);
}
// 中序遍历,左根右
public void inOrder(Tree parent)
{
if (parent == null)
return;
inOrder(parent.mLeft);
System.out.print(parent.mData.desc + " ");
inOrder(parent.mRight);
}
// 后序遍历,左右根
public void postOrder(Tree parent)
{
if (parent == null)
return;
postOrder(parent.mLeft);
postOrder(parent.mRight);
System.out.print(parent.mData.desc + " ");
}
// 遍历treeList并生成下次要遍历的
public void layerOrder()
{
if (treeList.isEmpty())
return;
List<Tree> buff = new ArrayList<Tree>();
for (Tree t : treeList)
{
if (t != null)
{
System.out.print(t.mData.desc + " ");
buff.add(t.mLeft);
buff.add(t.mRight);
}
}
treeList.clear();
if (!buff.isEmpty())
{
treeList.addAll(buff);
layerOrder();
}
}
// 另外一种利用数组 层次遍历的实现
public void layerOrder1(Tree parent)
{
elements[0] = parent;
front = 0;
rear = 1;
while (front < rear)
{
if (elements[front].mData != null)
{
System.out.print(elements[front].mData.desc + " ");
if (elements[front].mLeft != null)
{
elements[rear++] = elements[front].mLeft;
}
if (elements[front].mRight != null)
{
elements[rear++] = elements[front].mRight;
}
front++;
}
}
}
public static class Data
{
public String desc;
public Data(String s)
{
this.desc = s;
}
@Override
public String toString()
{
return desc;
}
}
}
public class TreeMain
{
public static void main(String[] args)
{
Tree d = new Tree(null, null, "D");
Tree e = new Tree(null, null, "E");
Tree f = new Tree(null, null, "F");
Tree g = new Tree(null, null, "G");
Tree b = new Tree(d, e, "B");
Tree c = new Tree(f, g, "C");
Tree a = new Tree(b, c, "A");
a.preOrder(a);
System.out.println("");
a.inOrder(a);
System.out.println("");
a.postOrder(a);
System.out.println("");
a.treeList.add(a);
a.layerOrder();
}
}
分享到:
相关推荐
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
目录1. 集合的概念2. 集合的分类3. 对集合操作的接口3.1 Collection接口3.2 List接口3.3 Set接口4....数据结构1.1 栈1.2 队列1.3 数组1.4 链表1.5 树1.5.1 二叉树1.5.2 红黑树2. 关于泛型2.1 概念2.2 定义和使用2.3 泛
2012-06-11 21:09 1,553,768 数据结构算法Visual.C.6.0程序集_源码.rar 2012-06-11 21:42 87,040 时域卷积定理的证明.ppt 2012-06-11 21:10 4,371 更改网关IP.rar 2012-06-11 20:57 1,419 栈的实现.txt 2012-06-11 ...
oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 第一章 Oracle入门 一、 数据库概述 数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,它产生于距今五十年前。简单来说是本身可视...