之前的篇章主要讲解了数据结构中的线性结构, 所谓线性结构就是数据与数据之间是一对一的关系, 接下来我们就要进入非线性结构的世界了, 主要是树与图, 好了接下来我们将会了解到树以及二叉树, 二叉平衡树, 赫夫曼树等原理以及 java 代码的实现, 先从最基础的开始学习吧.
一, 树
树的定义:
树是 n(n>=0) 个结点的有限集合.
当 n=0 时, 集合为空, 称为空树.
在任意一颗非空树中, 有且仅有一个特定的结点称为根.
当 n>1 时, 除根结点以外的其余结点可分成 m(m>=0) 个不相交的有限结点集合 T1,T2....Tm. 其中每个集合本身也是一棵树, 称为根的子树.
如下图就是一棵树:
可以看到, 树这种数据结构数据之间是一对一或者一对多关系, 不再是一对一的关系
在上图中节点 A 叫做整棵树的根节点, 一棵树中只有一个根节点.
根节点可以生出多个孩子节点, 孩子节点又可以生出多个孩子节点. 比如 A 的孩子节点为 B 和 C,D 的孩子节点为 G,H,I.
每个孩子节点只有一个父节点, 比如 D 的父节点为 B,E 的父节点为 C.
好了, 关于树的定义介绍到这, 很简单.
二, 树的相关术语
节点的度
节点含有的子树个数, 叫做节点的度. 度为 0 的节点成为叶子结点或终端结点. 比如上图中 D 的度为 3,E 的度为 1.
G,H,I,J 的度为 0, 叫做叶子结点.
树的度
一棵树中 最大节点的度树的度. 比如上图中树的度为 3
结点的层次
从根结点算起, 为第一层, 其余依次类推如上图. B,C 的层次为 2,G,H 的层次为 4.
树中节点的最大层次称为树的高度或深度. 上图中树的高度或深度为 4
三, 树的存储结构
简单的顺序存储不能满足树的实现, 需要结合顺序存储和链式存储来解决.
树的存储方式主要有三种:
双亲表示法: 每个节点不仅保存自己数据还附带一个指示器指示其父节点的角标, 这种方式可以用数组来存储.
如图:
这种存储方式特点是: 查找一个节点的孩子节点会很麻烦但是查找其父节点很简单.
孩子表示法: 每个节点不仅保存自己数据信息还附带指示其孩子的指示器, 这种方式用链表来存储比较合适.
如图:
这种存储方式特点是: 查找一个节点的父亲节点会很麻烦但是查找其孩子节点很简单.
理想表示法: 数组 + 链表的存储方式, 把每个结点的孩子结点排列起来, 以单链表方式连接起来, 则 n 个孩子有 n 个孩子链表, 如果是叶子结点则此链表为空, 然后 n 个头指针又组成线性表, 采用顺序存储方式, 存储在一个一维数组中.
如图:
这种方式查找父节点与孩子结点都比较简便.
以上主要介绍了树的一些概念以及存储方式介绍, 实际我们用的更多的是二叉树, 接下来我们看下二叉树.
四, 二叉树的概念
二叉树定义: 二叉树是 n(n>=0) 个结点的有限集合, 该集合或者为空, 或者由一个根结点和两课互不相交的, 分别称为根结点左子树和右子树的二叉树组成.
用人话说, 二叉树是每个节点至多有两个子树的树.
如图就是一颗二叉树:
五, 特殊二叉树
斜树: 所有结点只有左子树的二叉树叫做左斜树, 所有结点只有右子树的二叉树叫做右斜树.
如图:
满二叉树: 在一棵二叉树中, 所有分支结点都有左子树与右子树, 并且所有叶子结点都在同一层则为满二叉树.
如图:
完全二叉树: 所有叶子节点都出现在 k 或者 k-1 层, 而且从 1 到 k-1 层必须达到最大节点数, 第 k 层可是不是慢的, 但是第 k 层的所有节点必须集中在最左边.
如图:
六, 二叉树的遍历
二叉树的遍历主要有三种: 先序遍历, 中序遍历, 后续遍历, 接下来我们挨个了解一下.
先序遍历: 先访问根结点, 再先序遍历左子树, 再先序遍历右子树.
如图所示:
先序遍历结果为: ABDGHCEIF
中序遍历: 先中序遍历左子树, 再访问根结点, 再中序遍历右子树.
如图:
中序遍历结果为: GDHBAEICF
后序遍历: 先后序遍历左子树, 再后序遍历右子树, 再访问根结点.
如图:
后序遍历结果: GHDBIEFCA
七, java 实现二叉树
先来看看每个结点类:
- public class TreeNode{
- private String data;// 自己结点数据
- private TreeNode leftChild;// 左孩子
- private TreeNode rightChild;// 右孩子
- public String getData() {
- return data;
- }
- public void setData(String data) {
- this.data = data;
- }
- public TreeNode(String data){
- this.data = data;
- this.leftChild = null;
- this.rightChild = null;
- }
- }
很简单, 每个结点信息包含自己结点数据以及指向左右孩子的指针 (为了方便, 我这里就叫指针了).
二叉树的创建
我们创建如下二叉树:
代码实现:
- public class BinaryTree {
- private TreeNode root = null;
- public TreeNode getRoot() {
- return root;
- }
- public BinaryTree(){
- root = new TreeNode("A");
- }
- /**
- * 构建二叉树
- * A
- * B C
- * D E F G
- */
- public void createBinaryTree(){
- TreeNode nodeB = new TreeNode("B");
- TreeNode nodeC = new TreeNode("C");
- TreeNode nodeD = new TreeNode("D");
- TreeNode nodeE = new TreeNode("E");
- TreeNode nodeF = new TreeNode("F");
- TreeNode nodeG = new TreeNode("G");
- root.leftChild = nodeB;
- root.rightChild = nodeC;
- nodeB.leftChild = nodeD;
- nodeB.rightChild = nodeE;
- nodeC.leftChild = nodeF;
- nodeC.rightChild = nodeG;
- }
- .......
- }
创建 BinaryTree 的时候就已经创建根结点 A,createBinaryTree() 方法中创建其余结点并且建立相应关系.
获得二叉树的高度
树中节点的最大层次称为树的高度, 因此获得树的高度需要递归获取所有节点的高度, 取最大值.
- /**
- * 求二叉树的高度
- * @author Administrator
- *
- */
- public int getHeight(){
- return getHeight(root);
- }
- private int getHeight(TreeNode node) {
- if(node == null){
- return 0;
- }else{
- int i = getHeight(node.leftChild);
- int j = getHeight(node.rightChild);
- return (i<j)?j+1:i+1;
- }
- }
获取二叉树的结点数
获取二叉树结点总数, 需要遍历左右子树然后相加
- /**
- * 获取二叉树的结点数
- * @author Administrator
- *
- */
- public int getSize(){
- return getSize(root);
- }
- private int getSize(TreeNode node) {
- if(node == null){
- return 0;
- }else{
- return 1+getSize(node.leftChild)+getSize(node.rightChild);
- }
- }
二叉树的遍历
二叉树遍历分为前序遍历, 中序遍历, 后续遍历, 主要也是递归思想, 下面直接给出代码
- /**
- * 前序遍历 -- 迭代
- * @author Administrator
- *
- */
- public void preOrder(TreeNode node){
- if(node == null){
- return;
- }else{
- System.out.println("preOrder data:"+node.getData());
- preOrder(node.leftChild);
- preOrder(node.rightChild);
- }
- }
- /**
- * 中序遍历 -- 迭代
- * @author Administrator
- *
- */
- public void midOrder(TreeNode node){
- if(node == null){
- return;
- }else{
- midOrder(node.leftChild);
- System.out.println("midOrder data:"+node.getData());
- midOrder(node.rightChild);
- }
- }
- /**
- * 后序遍历 -- 迭代
- * @author Administrator
- *
- */
- public void postOrder(TreeNode node){
- if(node == null){
- return;
- }else{
- postOrder(node.leftChild);
- postOrder(node.rightChild);
- System.out.println("postOrder data:"+node.getData());
- }
- }
获取某一结点的父结点
获取结点的父节点也是递归思想, 先判断当前节点左右孩子是否与给定节点信息相等, 相等则当前结点即为给定结点的父节点, 否则继续递归左子树, 右子树.
- /**
- * 查找某一结点的父结点
- * @param data
- * @return
- */
- public TreeNode getParent(String data){
- // 封装为内部结点信息
- TreeNode node = new TreeNode(data);
- //
- if (root == null || node.data.equals(root.data)){
- // 根结点为 null 或者要查找的结点就为根结点, 则直接返回 null, 根结点没有父结点
- return null;
- }
- return getParent(root, node);// 递归查找
- }
- public TreeNode getParent(TreeNode subTree, TreeNode node) {
- if (null == subTree){// 子树为 null, 直接返回 null
- return null;
- }
- // 判断左或者右结点是否与给定结点相等, 相等则此结点即为给定结点的父结点
- if(subTree.leftChild.data.equals(node.data) || subTree.rightChild.data.equals(node.data)){
- return subTree;
- }
- // 以上都不符合, 则递归查找
- if (getParent(subTree.leftChild,node)!=null){// 先查找左子树, 左子树找不到查询右子树
- return getParent(subTree.leftChild,node);
- }else {
- return getParent(subTree.rightChild,node);
- }
- }
八, 总结
以上总结了树与二叉树的一些概念, 重点就是二叉树的遍历以及 java 代码实现, 比较简单, 没什么多余解释, 下一篇了解一下赫夫曼树以及二叉排序树.
来源: https://www.cnblogs.com/leipDao/p/9707613.html