（java实现）数据结构（二）：二叉树初识（构建、遍历） |
您所在的位置：网站首页 › java实现二叉树遍历 › （java实现）数据结构（二）：二叉树初识（构建、遍历） |
（java实现）数据结构（二）：二叉树初识（构建、遍历）
|
树存储不同于数组和链表的地方在于既可以保证数据检索的速度，又可以保证数据插入删除修改的速度，二者兼顾。 二叉树是一种很重要的数据结构，是非线性的结构，非常多其他数据结构都是基于二叉树的基础演变而来的。如：一般二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉排序树、平衡二叉树、红黑树、B树。 普通的二叉树，很难构成现实的应用场景，但因其简单，常用于学习研究，平衡二叉树则是实际应用比较多的。常见于快速匹配、搜索等方面。常用的树有：AVL树、红黑树、B+树、Trie（字典）树。1、AVL树: 最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。2、红黑树: 平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的。还有Linux文件管理。3、B/B+树: 用在磁盘文件组织 数据索引和数据库索引。4、Trie树(字典树): 用在统计和排序大量字符串，如自动机、M数据库索引。 树常用术语: 1.节点：A、B、C、D、E、F、G、H 2.根节点：A 3.父节点、子节点：相对关系，如A是B、C的父节点，B、C是A的子节点 4.叶节点：没有子节点的节点，H、E、F、G 5.节点的权：节点值 6.路径：从root节点到该节点的路径 7.层（如图有四层） 8.子树（如图中虚线框中） 9.树的高度：最大层数 10.森林：多棵子树构成森林 而二叉树的每个节点最多只能有两个子节点（左、右节点） 若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。  完全二叉树满二叉树按国内的定义，如果所有的叶节点都在最后一层，除叶节点外每个节点都有两个子节点（节点总数2^n-1,n为层数）  满二叉树还有更多树就不详细展开写了，有需要以后再写。 下面来看看一些二叉树的基本实现，手动构建二叉树，得到总节点数，遍历，二叉树转数组（按层遍历创建），数组转二叉树等 首先需要一个小类来定义二叉树的各个节点： class TreeNode { public TreeNode parent;//父节点 public TreeNode left;//左节点 public TreeNode right;//右节点 //节点是用来存数据的，节点内部的数据： public Object data; }手动构建二叉树，就需要给每个节点赋值，再将各节点之间指向连接好，比较繁杂 //手工创建一个二叉树，返回其根节点 public TreeNode createTree(){ TreeNode root=new TreeNode(); root.data=11; TreeNode r1=new TreeNode(); r1.data=23; TreeNode r11=new TreeNode(); r11.data=43; TreeNode r12=new TreeNode(); r12.data=65; r1.left=r11; r1.right=r12; r11.parent=r1; r12.parent=r1; TreeNode r2=new TreeNode(); r2.data=32; TreeNode r21=new TreeNode(); r21.data=12; TreeNode r22=new TreeNode(); r22.data=53; r2.left=r21; r2.right=r22; r21.parent=r2; r22.parent=r2; //连直来三个节点: root.left=r1; root.right=r2; r1.parent=root; r2.parent=root; return root; }要将数组转成二叉树，先随机创建一个数组 public int[] createArray(int len){ int[] ary=new int[len]; java.util.Random ran=new Random(); for(int i=0;i各种遍历的结果： 前序遍历：1 2 4 5 7 8 3 6 中序遍历：4 2 7 5 8 1 3 6 后序遍历：4 7 8 5 2 6 3 1 层次遍历：1 2 3 4 5 6 7 8 递归版本的遍历比较简单写出，前中后序的遍历思想如下 前序遍历：根结点 ---> 左子树 ---> 右子树 中序遍历：左子树---> 根结点 ---> 右子树 后序遍历：左子树 ---> 右子树 ---> 根结点 public void trav(TreeNode root){ if(null!=root){ TreeNode left=root.left; TreeNode right=root.right; System.out.println(root.data); //先序：输出节点内的值 // Object data=root.data; // System.out.println("此节点值是 "+data); //递归其它的节点： trav(left); //中序 // Object data=root.data; // System.out.println("此节点值是 "+data); trav(right); //后序：输出节点内的值 // Object data=root.data; // System.out.println("此节点值是 "+data); } }非递归版本就较为困难了，有机会以后学会了再来讲哈哈 |
【本文地址】
今日新闻 |
推荐新闻 |