在一棵二叉樹中，除最后一層外妈倔，若其余層都是滿的冠骄，并且最后一層或者是滿的逛裤，或者是在右邊缺少連續(xù)若干節(jié)點，則此二叉樹為完全二叉樹（Complete Binary Tree）猴抹。
可以看出，在BinTree接口的基礎(chǔ)上锁荔，這里增加了addLast()和delLast()兩個操作蟀给。借助這兩個操作，我們可以在完全二叉樹中插入或刪除末節(jié)點阳堕。如下圖所示跋理，這里所謂的“末節(jié)點”，是指完全二叉樹的層次遍歷序列中的末節(jié)點恬总。
實際上前普，為了保證二叉樹的完全性不致受到破壞，對完全二叉樹的操作只能限于這兩個方法壹堰。
完全二叉樹接口：
package dsa.BinTree;
/*
* 完全二叉樹接口
*/
public interface ComplBinTree extends BinTree {
// 生成并返回一個存放e的外部節(jié)點拭卿，該節(jié)點成為新的末節(jié)點
public BinTreePosition addLast(Object e);
// 刪除末節(jié)點，并返回其中存放的內(nèi)容
public Object delLast();
// 返回按照層次遍歷編號為i的節(jié)點的位置贱纠，0 <= i < size()
public BinTreePosition posOfNode(int i);
}
完全二叉樹節(jié)點——基于秩實現(xiàn)的：
package dsa.BinTree;
import dsa.Vector.Vector;
/*
* 基于秩實現(xiàn)的完全二叉樹節(jié)點
*/
public class ComplBinTreeNode_Rank extends BinTreeNode implements BinTreePosition {
private Vector T;// 所屬的樹
private int rank;// 在所屬樹中的秩
private Object element;// 存放的對象
// 構(gòu)造函數(shù)
public ComplBinTreeNode_Rank(Vector t, Object obj) {
element = obj;
T = t;
rank = T.getSize();
T.insertAtRank(rank, this);
}
// 返回當(dāng)前節(jié)點中存放的對象
public Object getElem() {
return element;
}
// 將對象obj存入當(dāng)前節(jié)點峻厚，并返回此前的內(nèi)容
public Object setElem(Object obj) {
Object bak = element;
element = obj;
return bak;
}
// 判斷是否有父親（為使代碼描述簡潔）
public boolean hasParent() {
return (0 != rank) ? true : false;
}
// 返回當(dāng)前節(jié)點的父節(jié)點
public BinTreePosition getParent() {
return hasParent() ? (BinTreePosition) T.getAtRank((rank - 1) / 2) : null;
}
// 判斷是否有左孩子（為使代碼描述簡潔）
public boolean hasLChild() {
return (1 + rank * 2 < T.getSize()) ? true : false;
}
// 返回當(dāng)前節(jié)點的左孩子
public BinTreePosition getLChild() {
return hasLChild() ? (BinTreePosition) (T.getAtRank(1 + rank * 2)) : null;
}
// 判斷是否有右孩子（為使代碼描述簡潔）
public boolean hasRChild() {
return (2 + rank * 2 < T.getSize()) ? true : false;
}
// 返回當(dāng)前節(jié)點的右孩子
public BinTreePosition getRChild() {
return hasRChild() ? (BinTreePosition) (T.getAtRank(2 + rank * 2)) : null;
}
// 返回當(dāng)前節(jié)點后代元素的數(shù)目
public int getSize() {
int size = 1;
if (hasLChild())
size += getLChild().getSize();
if (hasRChild())
size += getRChild().getSize();
return size;
}
// 返回當(dāng)前節(jié)點的高度
public int getHeight() {
int hL = hasLChild() ? getLChild().getHeight() : -1;
int hR = hasRChild() ? getRChild().getHeight() : -1;
return 1 + Math.max(hL, hR);
}
// 返回當(dāng)前節(jié)點的深度
public int getDepth() {
return hasParent() ? 1 + getParent().getDepth() : 0;
}
}
基于向量實現(xiàn)的完全二叉樹
package dsa.BinTree;
import dsa.Sequence.Sequence;
import dsa.Vector.Vector;
import dsa.Vector.Vector_ExtArray;
/*
* 基于向量實現(xiàn)的完全二叉樹
*/
public class ComplBinTree_Vector extends BinTree_LinkedList implements ComplBinTree {
private Vector T;// 向量
// 構(gòu)造方法：默認(rèn)的空樹
public ComplBinTree_Vector() {
T = new Vector_ExtArray();
root = null;
}
// 構(gòu)造方法：按照給定的節(jié)點序列，批量式建立完全二叉樹
public ComplBinTree_Vector(Sequence s) {
this();
if (null != s)
while (!s.isEmpty())
addLast(s.removeFirst());
}
/*---------- BinaryTree接口中各方法的實現(xiàn) ----------*/
// 返回樹根（重寫）
public BinTreePosition getRoot() {
return T.isEmpty() ? null : posOfNode(0);
}
// 判斷是否樹空（重寫）
public boolean isEmpty() {
return T.isEmpty();
}
// 返回樹的規(guī)模（重寫）
public int getSize() {
return T.getSize();
}
// 返回樹（根）的高度（重寫）
public int getHeight() {
return isEmpty() ? -1 : getRoot().getHeight();
}
/*---------- ComplBinTree接口中各方法的實現(xiàn) ----------*/
// 生成并返回一個存放e的外部節(jié)點谆焊，該節(jié)點成為新的末節(jié)點
public BinTreePosition addLast(Object e) {
BinTreePosition node = new ComplBinTreeNode_Rank(T, e);
root = (BinTreePosition) T.getAtRank(0);
return node;
}
// 刪除末節(jié)點惠桃，并返回其中存放的內(nèi)容
public Object delLast() {
if (isEmpty())
return null;// 若樹（堆）已空，無法刪除
if (1 == getSize())
root = null;// 若刪除最后一個節(jié)點辖试，則樹空
return T.removeAtRank(T.getSize() - 1);
}
// 返回按照層次遍歷編號為i的節(jié)點的位置辜王，0 <= i < size()
public BinTreePosition posOfNode(int i) {
return (BinTreePosition) T.getAtRank(i);
}
}
