数据结构(十一) -- 完全二叉树

在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树(Complete Binary Tree)。

可以看出,在BinTree接口的基础上,这里增加了addLast()和delLast()两个操作。借助这两个操作,我们可以在完全二叉树中插入或删除末节点。如下图所示,这里所谓的“末节点”,是指完全二叉树的层次遍历序列中的末节点。

实际上,为了保证二叉树的完全性不致受到破坏,对完全二叉树的操作只能限于这两个方法。

完全二叉树接口:

package dsa.BinTree;

/*
* 完全二叉树接口
*/
public interface ComplBinTree extends BinTree {
    // 生成并返回一个存放e的外部节点,该节点成为新的末节点
    public BinTreePosition addLast(Object e);

    // 删除末节点,并返回其中存放的内容
    public Object delLast();

    // 返回按照层次遍历编号为i的节点的位置,0 <= i < size()
    public BinTreePosition posOfNode(int i);
}

完全二叉树节点——基于秩实现的:

package dsa.BinTree;

import dsa.Vector.Vector;

/*
* 基于秩实现的完全二叉树节点
*/
public class ComplBinTreeNode_Rank extends BinTreeNode implements BinTreePosition {
    private Vector T;// 所属的树
    private int rank;// 在所属树中的秩
    private Object element;// 存放的对象
    // 构造函数

    public ComplBinTreeNode_Rank(Vector t, Object obj) {
        element = obj;
        T = t;
        rank = T.getSize();
        T.insertAtRank(rank, this);
    }

    // 返回当前节点中存放的对象
    public Object getElem() {
        return element;
    }

    // 将对象obj存入当前节点,并返回此前的内容
    public Object setElem(Object obj) {
        Object bak = element;
        element = obj;
        return bak;
    }

    // 判断是否有父亲(为使代码描述简洁)
    public boolean hasParent() {
        return (0 != rank) ? true : false;
    }

    // 返回当前节点的父节点
    public BinTreePosition getParent() {
        return hasParent() ? (BinTreePosition) T.getAtRank((rank - 1) / 2) : null;
    }

    // 判断是否有左孩子(为使代码描述简洁)
    public boolean hasLChild() {
        return (1 + rank * 2 < T.getSize()) ? true : false;
    }

    // 返回当前节点的左孩子
    public BinTreePosition getLChild() {
        return hasLChild() ? (BinTreePosition) (T.getAtRank(1 + rank * 2)) : null;
    }

    // 判断是否有右孩子(为使代码描述简洁)
    public boolean hasRChild() {
        return (2 + rank * 2 < T.getSize()) ? true : false;
    }

    // 返回当前节点的右孩子
    public BinTreePosition getRChild() {
        return hasRChild() ? (BinTreePosition) (T.getAtRank(2 + rank * 2)) : null;
    }

    // 返回当前节点后代元素的数目
    public int getSize() {
        int size = 1;
        if (hasLChild())
            size += getLChild().getSize();
        if (hasRChild())
            size += getRChild().getSize();
        return size;
    }

    // 返回当前节点的高度
    public int getHeight() {
        int hL = hasLChild() ? getLChild().getHeight() : -1;
        int hR = hasRChild() ? getRChild().getHeight() : -1;
        return 1 + Math.max(hL, hR);
    }

    // 返回当前节点的深度
    public int getDepth() {
        return hasParent() ? 1 + getParent().getDepth() : 0;
    }
}

基于向量实现的完全二叉树

package dsa.BinTree;

import dsa.Sequence.Sequence;
import dsa.Vector.Vector;
import dsa.Vector.Vector_ExtArray;

/*
* 基于向量实现的完全二叉树
*/
public class ComplBinTree_Vector extends BinTree_LinkedList implements ComplBinTree {
    private Vector T;// 向量
    // 构造方法:默认的空树

    public ComplBinTree_Vector() {
        T = new Vector_ExtArray();
        root = null;
    }

    // 构造方法:按照给定的节点序列,批量式建立完全二叉树
    public ComplBinTree_Vector(Sequence s) {
        this();
        if (null != s)
            while (!s.isEmpty())
                addLast(s.removeFirst());
    }

    /*---------- BinaryTree接口中各方法的实现 ----------*/
    // 返回树根(重写)
    public BinTreePosition getRoot() {
        return T.isEmpty() ? null : posOfNode(0);
    }

    // 判断是否树空(重写)
    public boolean isEmpty() {
        return T.isEmpty();
    }

    // 返回树的规模(重写)
    public int getSize() {
        return T.getSize();
    }

    // 返回树(根)的高度(重写)
    public int getHeight() {
        return isEmpty() ? -1 : getRoot().getHeight();
    }

    /*---------- ComplBinTree接口中各方法的实现 ----------*/
    // 生成并返回一个存放e的外部节点,该节点成为新的末节点
    public BinTreePosition addLast(Object e) {
        BinTreePosition node = new ComplBinTreeNode_Rank(T, e);
        root = (BinTreePosition) T.getAtRank(0);
        return node;
    }

    // 删除末节点,并返回其中存放的内容
    public Object delLast() {
        if (isEmpty())
            return null;// 若树(堆)已空,无法删除
        if (1 == getSize())
            root = null;// 若删除最后一个节点,则树空
        return T.removeAtRank(T.getSize() - 1);
    }

    // 返回按照层次遍历编号为i的节点的位置,0 <= i < size()
    public BinTreePosition posOfNode(int i) {
        return (BinTreePosition) T.getAtRank(i);
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,491评论 1 31
  • 基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平...
    yhthu阅读 4,332评论 1 5
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,173评论 0 12
  • 一直以来,我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂,但是树在一些运算和查找中也不可避免的要使用到,那...
    24K男阅读 6,784评论 5 14
  • 德胜2017年5月9日咖啡冥想 我近期最想实现的一个愿望或目标是创造2万元的收入 发心:我今天不是为了我一个人而闻...
    何德胜觉悟阅读 133评论 0 0