`

二叉树

 
阅读更多

温习下二叉树。
二叉树——二叉双亲链~~各种遍历方式大家还记得吗?
不过要构建的节点很吓人....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的结点...

    第六章 树和二叉树作业及答案(100分).docx

    - **答案解析**:如果一棵二叉树的中序遍历序列和后序遍历序列正好相反,那么该二叉树一定是任一结点都没有左孩子的二叉树。 #### 5. 二叉树的结点数范围 - **答案解析**:深度为k的二叉树最多有\(2^k - 1\)个结点...

    将满二叉树转化为求和二叉树_二叉树_

    在IT领域,特别是数据结构和算法的学习中,二叉树是一种重要的抽象数据类型。满二叉树是一种特殊的二叉树,其中每一层都是完全填充的,除了可能的最后一层,且最后一层的所有节点都尽可能地向左靠拢。而将满二叉树...

    二叉树的各种操作各种遍历,复制,求高度,判断是否为一棵完全二叉树以及计算用二叉树存储的表达式

    根据给定的信息,本文将详细介绍二叉树的基本概念及其在程序中的实现方法,包括二叉树的创建、遍历(前序、中序、后序)、复制、求高度、判断是否为完全二叉树以及利用二叉树进行表达式的计算等操作。 ### 一、...

    构造二叉树与遍历二叉树

    ### 构造二叉树与遍历二叉树 #### 一、二叉树的基本概念 二叉树(Binary Tree)是一种非线性数据结构,在计算机科学中被广泛应用于各种算法和程序设计中。一个二叉树由零个或多个节点组成,其中每个节点最多有两个子...

    按凹入表形式横向打印任意二叉树结构,即二叉树的根在屏幕的最左边,二叉树的左子树在屏幕的下边,二叉树的右子树在屏幕的上边。

    二叉树横向打印算法的实现 二叉树是一种基本的数据结构,在计算机科学和编程中广泛应用。本资源介绍了一种特殊的二叉树打印算法,即横向打印二叉树结构。该算法将二叉树的根节点放在屏幕的最左边,左子树在屏幕的...

    复制一棵二叉树

    ### 知识点:复制一棵二叉树 #### 一、引言 在计算机科学领域,数据结构中的二叉树是一种常见的非线性数据结构,它由节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。复制二叉树是指创建一个与原...

    二叉树的基本运算

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

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

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

    二叉树的建立与遍历

    二叉树的建立与遍历 二叉树是一种重要的数据结构,它广泛应用于计算机科学和软件工程中。在这篇文章中,我们将讨论二叉树的建立和遍历,包括先序遍历、中序遍历和后序遍历。 一、数据结构的重要性 数据结构是...

    二叉树_二叉树遍历_

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

    求二叉树最大宽度 求二叉树最大宽度 数据结构

    在探讨“求二叉树最大宽度”的数据结构问题时,我们深入分析了如何通过特定算法找到一棵二叉树中每一层节点的最大数量,这一过程涉及到了数据结构与算法设计的关键概念和技术。 ### 一、二叉树的概念 二叉树是一种...

    二叉树模拟器.py二叉树模拟器.py

    二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py...

    设计程序实现二叉树结点的类型定义和对二叉树的基本操作

    ### 二叉树基本操作知识点解析 #### 一、实验目的 在本实验中,学习者将通过实际编程练习来加深对二叉树这一数据结构的理解,并熟练掌握其基本操作。具体目标包括: 1. **熟悉二叉树结点的结构和对二叉树的基本...

    二叉树遍历实验报告

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

    画二叉树小工具dtree源码

    【标题】"画二叉树小工具dtree源码"涉及的是一个用于绘制二叉树图形的编程工具,它的核心是通过源代码实现对二叉树结构的可视化展示。二叉树是一种重要的数据结构,广泛应用于计算机科学的多个领域,如搜索、排序、...

Global site tag (gtag.js) - Google Analytics