`

二叉树

 
阅读更多

温习下二叉树。
二叉树——二叉双亲链~~各种遍历方式大家还记得吗?
不过要构建的节点很吓人....2的k次方。所以,顺手就加了个超出范围就抛出异常,    
这个树形输出还比较犀利对吧 ?

本来已经要早睡了,听到一首怀旧的歌,于是就....

import java.util.Random;
 
public classBiTree {
   class BiNode {
      public BiNode left;
      public BiNode right;
      public BiNode parent;
      public int value;
      public int no;
     
      public BiNode(int no, int val) {
         value = val;
         this.no = no;
      }
 
      @Override
      public String toString() {
         return this.no + "/" + this.value;
      }
   }
 
   private BiNode root;
   private Random random;
 
   public BiNode getRoot() { return root;}
  
   public BiTree() throws Exception {
      random = new Random();
      createCBTree(5);
   }
  
   //生成随机值满二叉树
   public void createCBTree(int degree) throws Exception {
      if(degree < 1&& degree > 15) {
         throw new Exception("该二叉树的深度应在1~15以内");
      }
     
      root = new BiNode(1, 1/*random.nextInt() % 100*/);   
      buildCBiTree(root, degree);
   }
   int no = 2;
   private void buildCBiTree(BiNode bn,intdegree) {
      if(degree == 1) {
         return;
      }
      BiNodeleft = newBiNode(no, random.nextInt() % 100); no++;
      bn.left = left;
      left.parent = bn;
     
      BiNoderight = newBiNode(no, random.nextInt() % 100); no++;
      bn.right = right;
      right.parent = bn;
 
      buildCBiTree(left,degree - 1);
      buildCBiTree(right,degree - 1);
   }
  
   private void printSpace(int num) {
      for(int i = 0; i < num; ++i){
         System.out.print("|..");
      }
   }
  
   public void visit(int order) {
      switch(order) {
      case 1:
         System.out.println("先序遍历:");
         firstVisit(root);
         break;
      case 2:
         System.out.println("中序遍历:");
         midVisit(root);
         break;
      case 3:
         System.out.println("后序遍历:");
         lastVisit(root);
         break;
      default:
         System.out.println("先序遍历:");
         firstVisit(root);
         break;
      }
      System.out.println();
   }
   public void formatOutput() {
      System.out.println(getRoot());
      output(getRoot(),0);
   }
 
   //格式化输出
   public void output(BiNode bn, int degree) {
      if(bn != null) {
         if(bn.left != null) {
            printSpace(degree);
            System.out.println("|.." + bn.left);
         }
         output(bn.left, degree + 1);
       
         if(bn.right != null) {
            printSpace(degree);
            System.out.println("|.." + bn.right);
         }
         output(bn.right, degree + 1);
      }
   }
 
   //先序递归遍历
   public void firstVisit(BiNode bn) {
      if(bn != null) {
         System.out.print(bn.value + "..");
         firstVisit(bn.left);
         firstVisit(bn.right);
      }
   }
  
   //中序递归遍历
   public void midVisit(BiNode bn) {
      if(bn != null) {
         midVisit(bn.left);
         System.out.print(bn.value + "..");
         midVisit(bn.right);
      }
   }
   //后序递归遍历
   public void lastVisit(BiNode bn) {
      if(bn != null) {
         lastVisit(bn.left);
         lastVisit(bn.right);
         System.out.print(bn.value + "..");
      }
   }
 
   public static void main(String[] args) {
      BiTreebt = null;
      try {
         bt= newBiTree();
      }catch(Exception e) {
         e.printStackTrace();
      }     
      bt.visit(1);
      bt.visit(2);
      bt.visit(3);
      bt.formatOutput();
   }
}

 

分享到:
评论

相关推荐

    二叉树建立 二叉树基本算法的实现

    (2)先序、中序、后序遍历二叉树:递归算法。 (3)中序遍历二叉树:非递归算法(最好也能实现先序,后序非递归算法)。 (4)求二叉树的高度 。 (5)求二叉树的叶子个数。 (6)对于树中每一个元素值为x的结点...

    二叉树的基本运算

    建立一棵二叉树,试编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目...

    二叉树相关算法的实验验证+判别给定二叉树是否为完全二叉树。

    1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树; 3) 在二叉树中搜索给定结点的父结点; 4) 搜索二叉树中符合...

    二叉树的建立与基本操作

    编写程序实现二叉树的如下操作: 1) 建立二叉链表 2) 二叉树的先序、中序、后序遍历 3) 求解二叉树的叶子结点个数 4) 将二叉树中所有结点的左、右子树相互交换 输入:  扩展二叉树先序序列:ab#d##ce###。其中#...

    数据结构试验3二叉树建立,遍历等

    数据结构试验3二叉树建立,遍历等操作代码及运行结果。 实验内容: 采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,...

    二叉树课程设计的实验报告

    3 程序所能达到的功能:生成一个新的二叉树,实现对二叉树的先序,中序,后序和层次遍历,计算二叉树的深度,结点数,叶结点数,。 4 测式数据: A生成一个新的二叉树后,直接在键盘上按要求输入字符,可以依次输入...

    二叉树的建立及遍历

    如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...

    数据结构 树和二叉树ppt教程

    详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针...

    二叉树的建立与遍历

    按先序序列构造一棵二叉链表表示的二叉树T,并输出该T的中序遍历序列。实现提示: 1) 按先序序列建立一棵二叉树时,先构造根结点,再构造根的左子树,然后构造右子树;每棵子树又都是二叉树,所以构造一棵子树的过程...

    二叉树_二叉树遍历_

    1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;(2)对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出...

    根据先序与中序遍历结果建立二叉树

    根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...

    数据结构实验-二叉树的基本操作

    运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...

    数据结构实验——二叉树的建立和遍历.zip

    1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...

    数据结构——二叉树有关操作程序

    一)建立二叉树+判空+遍历 (1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现...

    二叉树---数据结构

    二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树

    数据结构实验 二叉树的遍历方法

    一、实验名称:二叉树的遍历方法 二、实验目的: (1)熟悉C语言的上机环境,进一步掌握C语言的结构特点; (2)掌握二叉树的储存结构的定义及C语言实现; (3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,...

    C++ 数据库二叉树的实现

    4.掌握计算二叉树的结点个数、二叉树的深度、二叉树的叶子结点和二叉树复制算法。 二、实验内容 1、构造基于先序遍历的二叉链表。 要求:按先序遍历规则,从键盘连续输入二叉树的先序序列,若无孩子结点,则用#代替...

    数据结构二叉树实验头文件

    在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为k,且有2^k-1个结点的...

    北京邮电大学_信通院_数据结构_二叉树 C++

    根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 二叉树的基本功能: 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定...

Global site tag (gtag.js) - Google Analytics