首先定义一个二叉树结构如下
class BNode{
private String name;
private BNode left,right;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public BNode getLeft() {
return left;
}
public void setLeft(BNode left) {
this.left = left;
}
public BNode getRight() {
return right;
}
public void setRight(BNode right) {
this.right = right;
}
public BNode(String name)
{
this(name,null,null);
}
public BNode(String name,BNode left,BNode right){
this.name = name;
this.left = left;
this.right = right;
}
}
插入一堆节点
BNode root;
root = new BNode("贾母");
root.setLeft(new BNode("贾政"));
root.setRight(new BNode("贾赦"));
root.getLeft().setLeft(new BNode("贾元春"));
root.getLeft().setRight(new BNode("贾宝玉"));
root.getRight().setLeft(new BNode("贾琏"));
root.getRight().setRight(new BNode("王熙凤"));
下面是简单的前序遍历,中序遍历,后序遍历
protected static void preOrder(BNode n)
{
if(n!=null){
System.out.println(n.getName());
preOrder(n.getLeft());
preOrder(n.getRight());
}
}
protected static void inOrder(BNode n)
{
if(n!=null){
inOrder(n.getLeft());
System.out.println(n.getName());
inOrder(n.getRight());
}
}
protected static void postOrder(BNode n)
{
if(n!=null){
postOrder(n.getLeft());
postOrder(n.getRight());
System.out.println(n.getName());
}
}
下面是广度优先遍历
protected static void wideOrder(BNode n)
{
LinkedList l = new LinkedList();
if(n!= null){
l.push(n);
}
while(!l.isEmpty()){
BNode t = (BNode)l.removeLast();
System.out.println(t.getName());
if(t.getLeft()!=null){
l.push(t.getLeft());
}
if(t.getRight()!=null){
l.push(t.getRight());
}
}
}
1,首先将根节点放到队列中;
2,不断循环取队列尾,如果能取到节点,进行步骤3,否则退出循环;
3,依次将该节点的左右子节点插入队列头
下面是非递归先序遍历二叉树的一种实现,用到Stack这种数据结构,注意压栈时先右子节点后左子节点
protected static void preOrder(BNode n)
{
Stack s = new Stack();
if(n!=null){
s.push(n);
}
while(!s.isEmpty())
{
n = (BNode)s.pop();
System.out.println(n.getName());
if(n.getRight() != null){
s.push(n.getRight());
}
if(n.getLeft()!=null){
s.push(n.getLeft());
}
}
}
分享到:
相关推荐
完成二叉树的建立然后分别先序中序后序遍历二叉树并算出二叉树的高度和叶节点的个数
1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...
算法与数据结构——二叉树的建立与遍历.pdf算法与数据结构——二叉树的建立与遍历.pdf
数据结构,实现二叉树的生成与遍历的算法。包含利用先序、中序、后序遍历二叉树算法,二叉树基本操作。(注意没有左子树或右子树时用@或#作为结束符号)
以二叉链表作存储结构,试编写前序、中序、后序遍历二叉树的算法。
实验要求: (1)采用链式存储结构建立二叉树,并按先序输入二叉树的结点序列。建立时按先序输入的结点序列为:a b c # # # d e ... (3)在主函数中分别调用以上四个算法函数(建立二叉树,先序、中序、后序遍历二叉树)。
算法与数据结构——二叉树的建立与遍历.docx算法与数据结构——二叉树的建立与遍历.docx
该文件包括二叉树的头文件(BitTree开头)和堆栈的头文件(Seq开头),另外还实现了编写按层次顺序(同一层自左至右)遍历二叉树的算法、后序递归遍历计算二叉树的深度的算法、判断给定二叉树是否为完全二叉树(通过...
通过“图片压缩编码”的编程实践,学习树、遍历二叉树、哈夫曼树、哈夫曼编码和他们的编程应用。 (1)掌握树的存储结构 (2)掌握二叉树的三种遍历方法 (3)掌握并理解Huffman树、Huffman编码等知识和应用 (4)掌握文件的...
(1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现先序遍历、中序遍历、后序...
本人本科期间数据结构二叉树的实验 1、建立二叉树的存储结构 2、先序、中序、后序遍历二叉树(要求任选某一种用非递归算法完成) 3、查询二叉树中某个结点 4、统计二叉树中叶子结点的个数 5、求二叉树的深度 6、要求...
本文介绍了使用Java语言实现二叉树前序、中序和后序遍历的基本算法。首先,定义了一个简单的TreeNode类来表示二叉树的节点,包括节点...这些遍历算法是二叉树操作的基础,对于理解树形数据结构和算法设计具有重要意义。
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
以二叉链表为存储结构,实现二叉树的创建、遍历(先序,中序,后序遍历)算法
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有最高效率的...
数据结构的二叉树的应用——MFC 【问题描述】设计出二叉链表结构的相关函数库。 【实现要求】 (1) 包括二叉树的各种基本函数以及常用函数 (2) 最好借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形...