0001 /* 0002 * 基于向量实现的完全二叉树 0003 */ 0004 0005 package dsa; 0006 0007 public class ComplBinTree_Vector extends BinTree_LinkedList implements ComplBinTree { 0008 private Vector T;//向量 0009 0010 //构造方法:默认的空树 0011 public ComplBinTree_Vector() 0012 { T = new Vector_ExtArray(); root = null; } 0013 0014 //构造方法:按照给定的节点序列,批量式建立完全二叉树 0015 public ComplBinTree_Vector(Sequence s) 0016 { this(); if (null != s) while (!s.isEmpty()) addLast(s.removeFirst()); } 0017 0018 /*---------- BinaryTree接口中各方法的实现 ----------*/ 0019 //返回树根(重写) 0020 public BinTreePosition getRoot() 0021 { return T.isEmpty() ? null : posOfNode(0); } 0022 0023 //判断是否树空(重写) 0024 public boolean isEmpty() 0025 { return T.isEmpty(); } 0026 0027 //返回树的规模(重写) 0028 public int getSize() 0029 { return T.getSize(); } 0030 0031 //返回树(根)的高度(重写) 0032 public int getHeight() 0033 {return isEmpty() ? -1 : getRoot().getHeight(); } 0034 0035 /*---------- ComplBinTree接口中各方法的实现 ----------*/ 0036 //生成并返回一个存放e的外部节点,该节点成为新的末节点 0037 public BinTreePosition addLast(Object e) { 0038 BinTreePosition node = new ComplBinTreeNode_Rank(T, e); 0039 root = (BinTreePosition) T.getAtRank(0); 0040 return node; 0041 } 0042 0043 //删除末节点,并返回其中存放的内容 0044 public Object delLast() { 0045 if (isEmpty()) return null;//若树(堆)已空,无法删除 0046 if (1 == getSize()) root = null;//若删除最后一个节点,则树空 0047 return T.removeAtRank(T.getSize() - 1); 0048 } 0049 0050 //返回按照层次遍历编号为i的节点的位置,0 <= i < size() 0051 public BinTreePosition posOfNode(int i) { 0052 return (BinTreePosition)T.getAtRank(i); 0053 } 0054 }