在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（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);
}
}
网友评论