`
dingjun1
  • 浏览: 214338 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二叉树相关知识

阅读更多
一、二叉树的构建与打印

Node.java

public class Node {
	private int value;
	private Node left;
	private Node right;
	public Node(int value){
		this.value = value;
	}
	public void setLeft(Node left){
		this.left = left;
	}
	public void setRight(Node right){
		this.right = right;
	}
	
	public Node getLeft(){
		return this.left;
	}
	public Node getRight(){
		return this.right;
	}
	
	public void setValue(int value){
		this.value = value;
	}
	public int getValue(){
		return this.value;
	}
}



BinaryTree.java
import java.util.ArrayList;
import java.util.List;


public class BinaryTree {
	private int[] bTreeValue = new int[]{89,100,34,20,200,102,50,300,178,145,134,7,18,4,1};
	
	private void order(){
		
		//冒泡法
		if(bTreeValue.length==0){
			return;
		}
		
		//相临两个值依次比较,如果前一个值小于或等于第二个值则不变位置
		//如果第一个值大于第二个值,第一个值与第二个值交换位置
		//经过第一轮后,本数组中最大值会排在数组最后一个位置
		
		//然后第二次比较,重覆上一次的比较,唯一不同的是不需要和最后一个值比较(N次比较时,进行到倒数第(N-1)个值就可以结束比较)
		//因为进行一轮比较,后面的序列就是有序的了。
		
		int k=0,j=0;
		for(k=0;k<bTreeValue.length-1;k++){//当只剩下一个数时,就不需要和自己比较了
			for(j=0;j<bTreeValue.length-1-k;j++){
				if(bTreeValue[j]>bTreeValue[j+1]){
					int tmp = bTreeValue[j];
					bTreeValue[j] =  bTreeValue[j+1];
					bTreeValue[j+1] = tmp;
				}
			}
			for(int t=0;t<bTreeValue.length;t++){
				System.out.print(bTreeValue[t]+",");
			}
			System.out.println();
		}
		
		
		
		
	}
	
	
	public Node buildTree(){
		if(bTreeValue.length==0){
			return null;
		}
		
		
		int[] remain = bTreeValue;
		int i = remain.length/2;
		Node root =new Node(remain[i]);
		
		buildSubTree(root,remain);
		
		return root;
		
	}
	
	
	private void buildSubTree(Node root,int[] remain){
		
		if(remain.length==1){
			return;
		}
		
		int i = remain.length/2;
		
		if(i>0){
			int[]leftArr = new int[i];
			for(int j=0;j<i;j++){
				leftArr[j] = remain[j];
			}
			int lInd = leftArr.length/2;
			Node left = new Node(leftArr[lInd]);
			root.setLeft(left);
			buildSubTree(left,leftArr);
		}
		
		if(remain.length-i-1>0){
			int[]rightArr = new int[remain.length-i-1];
			for(int j=0;j<remain.length-i-1;j++){
				rightArr[j] = remain[i+1+j];
			}
			int rInd = rightArr.length/2;
			Node right = new Node(rightArr[rInd]);
			root.setRight(right);
			buildSubTree(right,rightArr);
		}
		
	}
	
	/**
	 * 根据节点数计算二叉树的层数
	 * @return
	 */
	public int calculateLevel(int n){
		return (int)Math.floor(Math.log(n+1)/Math.log(2))+1;	
	}
	
	/**
	 * 计算某层的最大节点数
	 * @param level
	 * @return
	 */
	public int nodesNum(int level){
		return (int)Math.pow(2, level-1);
	}
	
	//逐层打印节点
	public void levelStructure(List list,List all){
		//同层数之间以三个字符与10个*分开
		//根为其所在子树的下底中点上
		List subList = new ArrayList();
		for(int i=0;i<list.size();i++){
			Node node = (Node)list.get(i);
			if(node.getLeft()!=null){
				subList.add(node.getLeft());
			}
			if(node.getRight()!=null){
				subList.add(node.getRight());
			}
		}
		if(subList.size()>0){
			all.add(subList);
			levelStructure(subList,all);
		}
	}
	
	
	public void print(List all){
		int len = 6;
		int wordLen = 3;
		//设定最底层二节点之间的长为10个字符宽,节点宽先忽略
		//根节点的左边,最下层有2的(level-1)次幂个节点,那么距离最下层左边的距离也就是2的(level-1)次幂减1乘以10/2
		
		//从下往上数,第二层开始,第一个节点距左边距离为(math.pow(2,level-1)-1)*(10/2)
		//当层节点之间的距离为下层节点之间长度的两倍可以推出从下住上数,节点之间距离为math.pow(2,level-1)*10
		
		
		for(int i=0;i<all.size();i++){
			List tmp = (List)all.get(i);
			int level = all.size()-i;//倒数第几层,最下层为第一层
			//左边的跟离
			StringBuffer sb = new StringBuffer(200);
			
			//==============================
			sb.append(separator(Math.pow(2, level-1)*(len/2)));
			if(level>=2){
				sb.append(separator(wordLen*Math.pow(2, level-2)));
			}
			//没有实际依据
			//==============================
			for(int k=0;k<tmp.size();k++){
				Node n = (Node)tmp.get(k);
				sb.append(value(n.getValue()));
				if(k<tmp.size()-1){
					sb.append(separator(Math.pow(2, level-1)*len+(Math.pow(2, level-1)-1)*wordLen));
				}
			}
			
			//if(level>=2){
			//	sb.append(separator(Math.pow(2, level-1)*len/2));
			//}
			
			//sb.append("\n\r");
			System.out.println(sb.toString());
			if(i<all.size()-1){//空两行,更美观一些
				System.out.println();
				System.out.println();
			}
		}
		
		
		
	}
	
	
	private String value(int v){
		//只考虑三个字符长度
		if(v<10){
			return " "+v+" ";
		}else if(v<100){
			return v+" ";
		}
		return v+"";
		
	}
	
	private String separator(double len){
		StringBuffer sb = new StringBuffer((int)len);
		for(int i=0;i<len;i++){
			sb.append(" ");
		}
		return sb.toString();
	}
	
	private int len(int l,int num){
		return (num-1)*l;
	}
	
	
	public static void main(String[] args){
		BinaryTree tree = new BinaryTree();
		tree.order();
		List all = new ArrayList();
		
		List subL = new ArrayList();
		subL.add(tree.buildTree());
		all.add(subL);
		
		tree.levelStructure(subL, all);
		
		tree.print(all);
		
	}
}





打印结果

                                    89


                  18                                  145


          4                34                102               200


    1        7       20       50       100      134      178      300




二、遍历算法
(未完)
分享到:
评论

相关推荐

    LeetCode_二叉树实用知识库分享

    本资源库整合了 LeetCode 中的二叉树相关知识点,涵盖二叉树的种类、遍历方式、定义等内容,并提供了多个 LeetCode 题目的解决方案。通过本资源库,开发者可以快速了解二叉树的基本概念和应用场景,提高编程技能和...

    数据结构中数与二叉树的相关知识汇总

    在本讲座中,主讲人游洪跃教授详细讲解了关于树和二叉树的知识。 首先,树是一种抽象数据类型,其定义包含以下几个要点: 1. 树是一个数据元素(节点)的集合,可以为空(称为空树)。 2. 树有一个唯一的根节点,它...

    noi初赛知识点 电脑基础知识 二叉树知识点

    信息学奥林匹克分区联赛的基础知识 包括CPU运行原理 电脑基础知识,后面有有关二叉树的详细知识点 共233页

    二叉树基础知识 包含ppt 和示例代码

    本资源包含“二叉树基础知识”的PPT讲解和实际的示例代码,为学习者提供了理论与实践相结合的学习体验。 二叉树的定义: 二叉树是由n(n&gt;=0)个有限节点组成的一个有穷集合。这些节点通过一对一的关系进行连接,...

    二叉树的基础知识

    二叉树的基础知识是理解和掌握更复杂数据结构和算法的基础,包括堆、图以及各种高级数据结构的实现。对二叉树的深入理解将有助于提升编程能力,特别是在解决涉及数据组织和查找效率的问题时。对于初学者来说,熟练...

    第六章 树和二叉树 耿国华

    树和二叉树相关知识点总结 在计算机科学中,树是一种重要的数据结构,广泛应用于计算机科学和信息技术领域中。本资源将对树和二叉树的相关知识点进行总结和分析。 一、树的基本概念 树是一种非线性数据结构,由...

    华科计算机学院数据结构二叉树实验报告

    这篇实验报告是关于华科计算机学院数据结构课程中二叉树相关知识的实践应用,主要涉及二叉树的创建、遍历以及相关属性的计算。以下是该实验报告中涵盖的知识点: 1. **二叉树的基本概念**:二叉树是一种特殊的树...

    数据结构课件---二叉树

    以下是对二叉树相关知识的详细阐述: 1. **树的定义与术语**: - 树是由n(n&gt;0)个节点组成的集合,其中有一个特定的节点称为根节点,其余节点分为m(m&gt;=0)个互不相交的子树。 - 节点的度:一个节点的子树数量,...

    树及二叉树的有关知识与编程

    二叉树是计算机科学中的一种基本数据结构,它在算法设计和数据组织中扮演着重要角色。二叉树的每个节点最多拥有两个子节点,分别称为左子节点和右子节点。这种特性使得二叉树成为实现特定算法的理想选择,如二叉查找...

    python二叉树的基础知识.docx

    Python 二叉树的基础知识 二叉树是数据结构中的一种重要概念,广泛应用于计算机科学和软件工程中。本文旨在介绍 Python 中二叉树的基础知识,包括二叉树的定义、代码创建及遍历等。 一、树的定义 树是一种数据...

    二叉树的实现(前序,中序,后序)

    在二叉树的实现中,我们通常...以上就是给定代码实现的二叉树相关知识点,包括二叉树的基本概念、节点结构、创建、遍历和辅助函数的实现。这些知识对于理解和操作二叉树至关重要,它们构成了许多数据结构和算法的基础。

    数据结构\例题\二叉树

    根据提供的文件信息,我们可以归纳出以下...以上是对给定文件中二叉树相关知识点的总结和解释。这些知识点对于理解二叉树的基本操作非常重要,也是后续深入学习二叉树其他高级特性(如平衡二叉树、红黑树等)的基础。

    数据结构二叉树专题java代码实现

    本专题聚焦于Java语言实现的二叉树相关知识,通过`BinaryTree.java`和`TreeNode.java`两个源文件,我们可以深入理解二叉树的构建、操作及其实现细节。 首先,`TreeNode.java`文件通常定义了一个二叉树节点类,它...

    二叉树基础知识和遍历算法等

    ### 二叉树基础知识与遍历算法详解 #### 一、二叉树基本概念 **二叉树**是一种特殊的树形结构,在计算机科学领域极为常见。它是一种数据结构,其中每个节点最多有两个子节点,通常被称为左子节点和右子节点。 ###...

    复制一棵二叉树

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

    二叉树_二叉树_

    以下是对二叉树相关知识点的详细阐述: 1. **二叉树的定义**: 二叉树是由n(n&gt;=0)个有限节点组成的一个有穷集合。这个集合或者为空(即n=0),或者由一个根节点及两个不相交的、分别称为左子树和右子树的二叉树...

    Practice0601_二叉树代码_

    以下是对二叉树相关知识的详细阐述: 一、二叉树的基本概念 1. 节点:二叉树由若干个节点组成,每个节点包含一个值以及指向其子节点的引用。根节点是树的起始点,没有父节点;叶节点是没有任何子节点的节点;非叶...

    二叉树,简单的二叉树范例程序

    二叉树是计算机科学中一种重要的数据结构,它在很多算法和问题解决中都有广泛应用。在数据结构课程中,学习二叉树可以帮助我们理解和掌握...通过阅读和分析这个程序,你可以进一步提升自己在二叉树方面的知识和技能。

    二叉树实验三 二叉树的综合操作

    根据给定的文件信息,我们可以总结出以下关于“二叉树实验三 二叉树的综合操作”的相关知识点: ### 一、实验性质与要求 #### 实验性质 本实验为综合性实验,旨在通过实际编程操作来加深对二叉树理论的理解。 ###...

    二叉树联系

    下面将详细解析这段代码所包含的二叉树相关知识点。 ### 二叉树概念 二叉树是一种树形结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。在计算机科学中,二叉树广泛应用于数据存储与检索,如二叉搜索...

Global site tag (gtag.js) - Google Analytics