Android 版数据结构与算法 (六): 树与二叉树

之前的篇章主要讲解了数据结构中的线性结构, 所谓线性结构就是数据与数据之间是一对一的关系, 接下来我们就要进入非线性结构的世界了, 主要是树与图, 好了接下来我们将会了解到树以及二叉树, 二叉平衡树, 赫夫曼树等原理以及 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 实现二叉树

先来看看每个结点类:publicclassTreeNode{

privateStringdata;// 自己结点数据

privateTreeNodeleftChild;// 左孩子

privateTreeNoderightChild;// 右孩子

publicStringgetData(){

returndata;

}

publicvoidsetData(Stringdata){

this.data=data;

}

publicTreeNode(Stringdata){

this.data=data;

this.leftChild=null;

this.rightChild=null;

}

}

很简单, 每个结点信息包含自己结点数据以及指向左右孩子的指针 (为了方便, 我这里就叫指针了).

二叉树的创建

我们创建如下二叉树:

代码实现:publicclassBinaryTree{

privateTreeNoderoot=null;

publicTreeNodegetRoot(){

returnroot;

}

publicBinaryTree(){

root=newTreeNode("A");

}

/**

* 构建二叉树

* A

* B C

* D E F G

*/

publicvoidcreateBinaryTree(){

TreeNodenodeB=newTreeNode("B");

TreeNodenodeC=newTreeNode("C");

TreeNodenodeD=newTreeNode("D");

TreeNodenodeE=newTreeNode("E");

TreeNodenodeF=newTreeNode("F");

TreeNodenodeG=newTreeNode("G");

root.leftChild=nodeB;

root.rightChild=nodeC;

nodeB.leftChild=nodeD;

nodeB.rightChild=nodeE;

nodeC.leftChild=nodeF;

nodeC.rightChild=nodeG;

}

.......

}

创建 BinaryTree 的时候就已经创建根结点 A,createBinaryTree() 方法中创建其余结点并且建立相应关系.

获得二叉树的高度

树中节点的最大层次称为树的高度, 因此获得树的高度需要递归获取所有节点的高度, 取最大值./**

* 求二叉树的高度

* @author Administrator

*

*/

publicintgetHeight(){

returngetHeight(root);

}

privateintgetHeight(TreeNodenode){

if(node==null){

return0;

}else{

inti=getHeight(node.leftChild);

intj=getHeight(node.rightChild);

return(i

}

}

获取二叉树的结点数

获取二叉树结点总数, 需要遍历左右子树然后相加/**

* 获取二叉树的结点数

* @author Administrator

*

*/

publicintgetSize(){

returngetSize(root);

}

privateintgetSize(TreeNodenode){

if(node==null){

return0;

}else{

return1+getSize(node.leftChild)+getSize(node.rightChild);

}

}

二叉树的遍历

二叉树遍历分为前序遍历, 中序遍历, 后续遍历, 主要也是递归思想, 下面直接给出代码/**

* 前序遍历 -- 迭代

* @author Administrator

*

*/

publicvoidpreOrder(TreeNodenode){

if(node==null){

return;

}else{

System.out.println("preOrder data:"+node.getData());

preOrder(node.leftChild);

preOrder(node.rightChild);

}

}

/**

* 中序遍历 -- 迭代

* @author Administrator

*

*/

publicvoidmidOrder(TreeNodenode){

if(node==null){

return;

}else{

midOrder(node.leftChild);

System.out.println("midOrder data:"+node.getData());

midOrder(node.rightChild);

}

}

/**

* 后序遍历 -- 迭代

* @author Administrator

*

*/

publicvoidpostOrder(TreeNodenode){

if(node==null){

return;

}else{

postOrder(node.leftChild);

postOrder(node.rightChild);

System.out.println("postOrder data:"+node.getData());

}

}

获取某一结点的父结点

获取结点的父节点也是递归思想, 先判断当前节点左右孩子是否与给定节点信息相等, 相等则当前结点即为给定结点的父节点, 否则继续递归左子树, 右子树./**

* 查找某一结点的父结点

* @param data

* @return

*/

publicTreeNodegetParent(Stringdata){

// 封装为内部结点信息

TreeNodenode=newTreeNode(data);

//

if(root==null||node.data.equals(root.data)){

// 根结点为 null 或者要查找的结点就为根结点, 则直接返回 null, 根结点没有父结点

returnnull;

}

returngetParent(root,node);// 递归查找

}

publicTreeNodegetParent(TreeNodesubTree,TreeNodenode){

if(null==subTree){// 子树为 null, 直接返回 null

returnnull;

}

// 判断左或者右结点是否与给定结点相等, 相等则此结点即为给定结点的父结点

if(subTree.leftChild.data.equals(node.data)||subTree.rightChild.data.equals(node.data)){

returnsubTree;

}

// 以上都不符合, 则递归查找

if(getParent(subTree.leftChild,node)!=null){// 先查找左子树, 左子树找不到查询右子树

returngetParent(subTree.leftChild,node);

}else{

returngetParent(subTree.rightChild,node);

}

}

八, 总结

以上总结了树与二叉树的一些概念, 重点就是二叉树的遍历以及 java 代码实现, 比较简单, 没什么多余解释, 下一篇了解一下赫夫曼树以及二叉排序树.

来源: https://www.cnblogs.com/leipDao/p/9707613.html