`
jaychang
  • 浏览: 734759 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

二叉树遍历,求深度

 
阅读更多

/**
* @title:   二叉树遍历,求深度
* @author: Jay Chang
* @version: ver 1.0
* @date: 2009.7.25
*/
import java.util.Scanner;

/*二叉树的结点的定义*/
class BiTreeNode
{
private String nodeName;
private int    value;
/*没有解决好lChild,rChild两个属性的封装,存在些问题,不知道为什么,有待改进*/
public BiTreeNode lChild;   
public BiTreeNode rChild;

public BiTreeNode(){}

/*创建结点对象的构造器*/
public BiTreeNode(String nodeName,int value)
{
     this.nodeName=nodeName;
     this.value=value;
    this.lChild=null;
    this.rChild=null;
}

/*setName,getName,setValue,getValue,是对结点两个属性的封装 */
public void setName(String nodeName)
{
      this.nodeName=nodeName;
}

public String getName()
{
    return nodeName;
}

public void setValue(int value)
{
     this.value=value;
}

public int getValue()
{
    return this.value;
}

}

/*二叉树类定义*/
class BiTree
{
private BiTreeNode root;

public BiTree(){}

public BiTreeNode getRoot()
{
   return this.root;
}

public void create()
{
this.root=createBiTree(this.root);
}
/*递归创建二叉树*/
private BiTreeNode createBiTree(BiTreeNode node)
{
     String name;int value;
      Scanner sc=new Scanner(System.in);
    System.out.println("输入结点名称及值:");
    name=sc.next();value=sc.nextInt();
    if(name!="#"&&value!=-1){
        node =new BiTreeNode(name,value);
        node.lChild=createBiTree(node.lChild);     //node.lChild和node.rChild本应使用封装,但是不能用?
        node.rChild=createBiTree(node.rChild);
        return node;
      }else{
        return null;
      }
}

/*求二叉树的高度*/
public int getDepth(BiTreeNode node)
{
    int lDepth,rDepth;
    if(node==null){
    return 0;
    }
    lDepth=getDepth(node.lChild);
    rDepth=getDepth(node.rChild);
    return (lDepth>rDepth?lDepth:rDepth)+1;
}

   /*先序遍历二叉树*/
public void fTraverse(BiTreeNode node)
{
     if(node!=null){
         System.out.println("Node Name:"+node.getName()+" Node Value:"+node.getValue());
         fTraverse(node.lChild);
         fTraverse(node.rChild);
      }else{
         return;
      }
}

/*中序遍历二叉树*/
public void mTraverse(BiTreeNode node)
{
     if(node!=null){
      mTraverse(node.lChild);
          System.out.println("Node Name:"+node.getName()+" Node Value:"+node.getValue());
      mTraverse(node.rChild);
    }else{
        return;
     }
}

/*后序遍历二叉树*/
public void lTraverse(BiTreeNode node)
{
   if(node!=null){
          lTraverse(node.lChild);
       lTraverse(node.rChild);
           System.out.println("Node Name:"+node.getName()+" Node Value:"+node.getValue());
      }else{
       return;
    }
}

}

 

public class TestBiTree
{
   public static void main(String[] args)
   {
     BiTree biTree=new BiTree();
     biTree.create();
     System.out.println("先序遍历:");
     biTree.fTraverse(biTree.getRoot());
     System.out.println("中序遍历:");
     biTree.mTraverse(biTree.getRoot());
     System.out.println("后序遍历:");
     biTree.lTraverse(biTree.getRoot());
     System.out.println("二叉树的高度:");
     System.out.println(biTree.getDepth(biTree.getRoot()));
   }

}

分享到:
评论

相关推荐

    二叉树的遍历与求深度以及结点数

    ### 二叉树的遍历与求深度以及结点数 #### 一、二叉树的基本概念 在探讨二叉树的遍历方法及其深度与结点数的计算之前,我们首先简要回顾一下二叉树的基本定义。二叉树是一种特殊的树结构,其中每个节点最多有两个...

    二叉树遍历求树叶数、深度

    数据结构二叉树遍历求树叶数及树的深度,个人作业,仅供大家参考或改进

    二叉树遍历及其应用

    ### 二叉树遍历及其应用 #### 一、引言 在计算机科学领域,《数据结构》是一门极为重要的基础课程。它不仅涵盖了各种数据结构的设计与实现,还涉及到了算法的设计与分析。其中,二叉树作为一种常用的数据结构,在...

    二叉树遍历算法应用各种算法包括遍历创建求深度等

    二叉树遍历算法应用 二叉树是一种常见的数据结构,...二叉树遍历算法有多种应用,包括求二叉树的高度、遍历二叉树、删除二叉树等。不同的遍历算法有其特点和应用场景,选择合适的遍历算法可以提高程序的效率和可读性。

    二叉树遍历算法的应用

    总结来说,二叉树遍历算法在实际问题中具有广泛的实用性,不仅可以用于数据结构的分析,还能解决如统计信息和计算深度等实际问题。通过理解和掌握这些算法,开发者可以更有效地处理涉及二叉树的各种挑战。

    实现先序,中序和后序遍历的二叉树遍历程序

    二叉树遍历是针对这种数据结构的一种基本操作,用于按照特定顺序访问树中的所有节点。本程序实现了三种主要的二叉树遍历方法:先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释: 1. 先序遍历...

    二叉树遍历问题-二叉树遍历问题

    在实际应用中,二叉树遍历不仅限于这几种基本形式,还可以进行变种,如深度优先搜索(DFS)和广度优先搜索(BFS)。这些遍历方法为处理复杂的数据结构和问题提供了基础,例如在编译器中解析语法树、构建搜索引擎索引...

    二叉树遍历实验报告

    ### 二叉树遍历实验报告知识点概览 #### 一、实验背景及目标 **实验背景:** 本次实验属于《数据结构》课程的一部分,旨在通过实际编程加深学生对二叉树这一数据结构的理解和应用能力。二叉树作为一种基本且重要的...

    二叉树遍历,深度,路径,销毁

    根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 二叉树的基本功能: 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 ...6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁

    数据结构-二叉树遍历

    学习二叉树遍历,不仅要理解其概念,还要掌握各种遍历方法的实现,并通过实践来提高解决问题的能力。对于给定的"二叉树的实现"文件,它可能包含了具体的代码示例或练习题目,用于帮助你深入理解和应用这些遍历方法。...

    二叉树遍历问题 关于二叉树遍历问题的一些总结

    二叉树遍历是计算机科学中处理树结构数据时常用的一种技术,对于理解和解决与树相关的算法问题至关重要。本文将深入探讨二叉树的三种遍历方法:先序遍历、中序遍历和后序遍历,并提供相关算法模板。 1. **先序遍历*...

    erchashubianli.rar_erchashubianli_二叉树 深度_二叉树遍历_遍历

    总之,二叉树遍历和计算深度是数据结构与算法的基础,它们不仅对理解二叉树至关重要,也是解决许多计算机科学问题的基石。通过深入学习和实践,你可以提高解决问题的能力,并为更高级的算法和数据结构打下坚实基础。

    python二叉树遍历、求深度、已知前序中序 求树 求后序 - CSDN博客1

    二叉树遍历的算法对于理解和操作二叉树至关重要,它们在很多实际问题中都有应用,比如搜索、排序和树的序列化。理解这些概念并能熟练运用,对于编程能力的提升非常有帮助。在Python中,使用递归和迭代方法可以灵活地...

    二叉树遍历

    二叉树遍历是计算机科学中的一个重要概念,特别是在数据结构和算法领域。它涉及到对二叉树这种数据结构的所有节点进行有序访问。二叉树是由节点组成的,每个节点最多有两个子节点,通常分为左子节点和右子节点。在...

    二叉树遍历和图遍历演示系统

    二叉树遍历和图遍历是数据结构与算法领域中的重要概念,广泛应用于软件开发、计算机科学教学以及各种计算问题的求解。本系统旨在通过动态演示来帮助理解和掌握这两种遍历方法,并且提供了完整的C语言算法描述,以...

    二叉树_二叉树遍历_

    1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。

    二叉树遍历前序非递归算法

    C语言二叉树遍历前序非递归算法,简单易懂,正确无误

    二叉树遍历C++源代码

    从给定的C++源代码来看,这段代码主要实现了二叉树的基本构建和深度优先遍历中...总之,这段代码不仅构建了一颗简单的二叉树,还展示了如何使用非递归方式实现前序遍历,为理解和实践二叉树遍历算法提供了良好的示例。

    JavaScript二叉树遍历1

    二叉树遍历有两种方式:深度遍历和广度遍历。 深度遍历可以进一步分为三种方式: 1. 先序优先遍历(DLR):根结点 > 左子树 > 右子树 2. 中序优先遍历(LDR):左子树 > 根结点 > 右子树 3. 后序优先遍历(LRD):...

    二叉树遍历问题及节点统计

    在数据结构与算法的学习中,理解和掌握二叉树遍历至关重要,因为它不仅是许多高级算法的基础,如树的展开、平衡操作等,而且在软件开发中也有实际应用,如文件系统的目录遍历、表达式求值、编译器中的语法分析等。...

Global site tag (gtag.js) - Google Analytics