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实现二叉树

先来看看每个结点类:

 1     public class TreeNode{
 2         private String data;//自己结点数据
 3         private TreeNode leftChild;//左孩子
 4         private TreeNode rightChild;//右孩子
 5         
 6         public String getData() {
 7             return data;
 8         }
 9         
10         public void setData(String data) {
11             this.data = data;
12         }
13         
14         public TreeNode(String data){
15             this.data = data;
16             this.leftChild = null;
17             this.rightChild = null;
18         }
19     }

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

二叉树的创建

我们创建如下二叉树:

代码实现:

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;
        }
    }        

获取二叉树的结点数

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

 1     /**
 2      * 获取二叉树的结点数
 3      * @author Administrator
 4      *
 5      */
 6     public int getSize(){
 7         return getSize(root);
 8     }
 9     
10     private int getSize(TreeNode node) {
11         if(node == null){
12             return 0;
13         }else{
14             return 1+getSize(node.leftChild)+getSize(node.rightChild);
15         }
16     }

二叉树的遍历

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

    /**
     * 前序遍历——迭代
     * @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());
        }
    }

获取某一结点的父结点

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

 1 /**
 2      * 查找某一结点的父结点
 3      * @param data
 4      * @return
 5      */
 6     public TreeNode getParent(String data){
 7         //封装为内部结点信息
 8         TreeNode node = new TreeNode(data);
 9         //
10         if (root == null || node.data.equals(root.data)){
11             //根结点为null或者要查找的结点就为根结点,则直接返回null,根结点没有父结点
12             return null;
13         }
14         return getParent(root, node);//递归查找
15     }
16 
17     public TreeNode getParent(TreeNode subTree, TreeNode node) {
18 
19         if (null == subTree){//子树为null,直接返回null
20             return null;
21         }
22         //判断左或者右结点是否与给定结点相等,相等则此结点即为给定结点的父结点
23         if(subTree.leftChild.data.equals(node.data) || subTree.rightChild.data.equals(node.data)){
24             return subTree;
25         }
26         //以上都不符合,则递归查找
27         if (getParent(subTree.leftChild,node)!=null){//先查找左子树,左子树找不到查询右子树
28             return getParent(subTree.leftChild,node);
29         }else {
30             return getParent(subTree.rightChild,node);
31         }
32     }

八、总结

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