0001 /* 0002 * 基于链表节点实现二叉树节点 0003 */ 0004 0005 package dsa; 0006 0007 public class BinTreeNode implements BinTreePosition { 0008 protected Object element;//该节点中存放的对象 0009 protected BinTreePosition parent;//父亲 0010 protected BinTreePosition lChild;//左孩子 0011 protected BinTreePosition rChild;//右孩子 0012 protected int size;//后代数目 0013 protected int height;//高度 0014 protected int depth;//深度 0015 0016 /**************************** 构造方法 ****************************/ 0017 public BinTreeNode() 0018 { this(null, null, true, null, null); } 0019 0020 public BinTreeNode( 0021 Object e,//节点内容 0022 BinTreePosition p,//父节点 0023 boolean asLChild,//是否作为父节点的左孩子 0024 BinTreePosition l,//左孩子 0025 BinTreePosition r) { //右孩子 0026 size = 1; height = depth = 0; parent = lChild = rChild = null;//初始化 0027 element = e;//存放的对象 0028 //建立与父亲的关系 0029 if (null != p) 0030 if (asLChild) p.attachL(this); 0031 else p.attachR(this); 0032 //建立与孩子的关系 0033 if (null != l) attachL(l); 0034 if (null != r) attachR(r); 0035 } 0036 0037 /**************************** Position接口方法 ********************************/ 0038 //返回当前节点中存放的对象 0039 public Object getElem() 0040 { return element; } 0041 0042 //将对象obj存入当前节点,并返回此前的内容 0043 public Object setElem(Object obj) 0044 { Object bak = element; element = obj; return bak; } 0045 0046 /**************************** BinTreePosition接口方法 *************************/ 0047 //判断是否有父亲(为使代码描述简洁) 0048 public boolean hasParent() 0049 { return null != parent; } 0050 //返回当前节点的父节点 0051 public BinTreePosition getParent() 0052 { return parent; } 0053 //设置当前节点的父节点 0054 public void setParent(BinTreePosition p) 0055 { parent = p; } 0056 0057 //判断是否为叶子 0058 public boolean isLeaf() 0059 { return !hasLChild() && !hasRChild(); } 0060 0061 //判断是否为左孩子(为使代码描述简洁) 0062 //若当前节点有父亲,而且是左孩子,则返回true;否则,返回false 0063 public boolean isLChild() 0064 { return (hasParent() && this == getParent().getLChild()) ? true : false; } 0065 0066 //判断是否有左孩子(为使代码描述简洁) 0067 public boolean hasLChild() 0068 { return null != lChild; } 0069 //返回当前节点的左孩子 0070 public BinTreePosition getLChild() 0071 { return lChild; } 0072 //设置当前节点的左孩子(注意:this.lChild和c.parent都不一定为空) 0073 public void setLChild(BinTreePosition c) 0074 { lChild = c; } 0075 0076 //判断是否为右孩子(为使代码描述简洁) 0077 //若当前节点有父亲,而且是右孩子,则返回true;否则,返回false 0078 public boolean isRChild() 0079 { return (hasParent() && this == getParent().getRChild()) ? true : false; } 0080 //判断是否有右孩子(为使代码描述简洁) 0081 public boolean hasRChild() 0082 { return null != rChild; } 0083 //返回当前节点的右孩子 0084 public BinTreePosition getRChild() 0085 { return rChild; } 0086 //设置当前节点的右孩子(注意:this.rChild和c.parent都不一定为空) 0087 public void setRChild(BinTreePosition c) 0088 { rChild = c; } 0089 0090 //返回当前节点后代元素的数目 0091 public int getSize() 0092 { return size; } 0093 //在孩子发生变化后,更新当前节点及其祖先的规模 0094 public void updateSize() { 0095 size = 1;//当前节点 0096 if (hasLChild()) size += getLChild().getSize();//左子树的规模 0097 if (hasRChild()) size += getRChild().getSize();//右子树的规模 0098 if (hasParent()) getParent().updateSize();//递归更新各个真祖先的规模记录 0099 } 0100 0101 //返回当前节点的高度 0102 public int getHeight() 0103 { return height; } 0104 //在孩子发生变化后,更新当前节点及其祖先的高度 0105 public void updateHeight() { 0106 height = 0;//先假设没有左、右孩子 0107 if (hasLChild()) height = Math.max(height, 1 + getLChild().getHeight()); //左孩子 0108 if (hasRChild()) height = Math.max(height, 1 + getRChild().getHeight()); //右孩子 0109 if (hasParent()) getParent().updateHeight();//递归更新各个真祖先的高度记录 0110 } 0111 0112 //返回当前节点的深度 0113 public int getDepth() 0114 { return depth; } 0115 //在父亲发生变化后,更新当前节点及其后代的深度 0116 public void updateDepth() { 0117 depth = hasParent() ? 1 + getParent().getDepth() : 0; //当前节点 0118 if (hasLChild()) getLChild().updateDepth();//沿孩子引用逐层向下, 0119 if (hasRChild()) getRChild().updateDepth();//递归地更新所有后代的深度记录 0120 } 0121 0122 //按照中序遍历的次序,找到当前节点的直接前驱 0123 public BinTreePosition getPrev() { 0124 //若左子树非空,则其中的最大者即为当前节点的直接前驱 0125 if (hasLChild()) return findMaxDescendant(getLChild()); 0126 //至此,当前节点没有左孩子 0127 if (isRChild()) return getParent();//若当前节点是右孩子,则父亲即为其直接前驱 0128 //至此,当前节点没有左孩子,而且是左孩子 0129 BinTreePosition v = this;//从当前节点出发 0130 while (v.isLChild()) v = v.getParent();//沿左孩子链一直上升 0131 //至此,v或者没有父亲,或者是父亲的右孩子 0132 return v.getParent(); 0133 } 0134 0135 //按照中序遍历的次序,找到当前节点的直接后继 0136 public BinTreePosition getSucc() { 0137 //若右子树非空,则其中的最小者即为当前节点的直接后继 0138 if (hasRChild()) return findMinDescendant(getRChild()); 0139 //至此,当前节点没有右孩子 0140 if (isLChild()) return getParent();//若当前节点是左孩子,则父亲即为其直接后继 0141 //至此,当前节点没有右孩子,而且是右孩子 0142 BinTreePosition v = this;//从当前节点出发 0143 while (v.isRChild()) v = v.getParent();//沿右孩子链一直上升 0144 //至此,v或者没有父亲,或者是父亲的左孩子 0145 return v.getParent(); 0146 } 0147 0148 //断绝当前节点与其父亲的父子关系 0149 //返回当前节点 0150 public BinTreePosition secede() { 0151 if (null != parent) { 0152 if (isLChild()) parent.setLChild(null);//切断父亲指向当前节点的引用 0153 else parent.setRChild(null); 0154 parent.updateSize();//更新当前节点及其祖先的规模 0155 parent.updateHeight();//更新当前节点及其祖先的高度 0156 parent = null;//切断当前节点指向原父亲的引用 0157 updateDepth();//更新节点及其后代节点的深度 0158 } 0159 return this;//返回当前节点 0160 } 0161 0162 //将节点c作为当前节点的左孩子 0163 public BinTreePosition attachL(BinTreePosition c) { 0164 if (hasLChild()) getLChild().secede();//摘除当前节点原先的左孩子 0165 if (null != c) { 0166 c.secede();//c脱离原父亲 0167 lChild = c; c.setParent(this);//确立新的父子关系 0168 updateSize();//更新当前节点及其祖先的规模 0169 updateHeight();//更新当前节点及其祖先的高度 0170 c.updateDepth();//更新c及其后代节点的深度 0171 } 0172 return this; 0173 } 0174 0175 //将节点c作为当前节点的右孩子 0176 public BinTreePosition attachR(BinTreePosition c) { 0177 if (hasRChild()) getRChild().secede();//摘除当前节点原先的右孩子 0178 if (null != c) { 0179 c.secede();//c脱离原父亲 0180 rChild = c; c.setParent(this);//确立新的父子关系 0181 updateSize();//更新当前节点及其祖先的规模 0182 updateHeight();//更新当前节点及其祖先的高度 0183 c.updateDepth();//更新c及其后代节点的深度 0184 } 0185 return this; 0186 } 0187 0188 //前序遍历 0189 public Iterator elementsPreorder() { 0190 List list = new List_DLNode(); 0191 preorder(list, this); 0192 return list.elements(); 0193 } 0194 0195 //中序遍历 0196 public Iterator elementsInorder() { 0197 List list = new List_DLNode(); 0198 inorder(list, this); 0199 return list.elements(); 0200 } 0201 0202 //后序遍历 0203 public Iterator elementsPostorder() { 0204 List list = new List_DLNode(); 0205 postorder(list, this); 0206 return list.elements(); 0207 } 0208 0209 //层次遍历 0210 public Iterator elementsLevelorder() { 0211 List list = new List_DLNode(); 0212 levelorder(list, this); 0213 return list.elements(); 0214 } 0215 0216 /**************************** 辅助方法 ****************************/ 0217 //在v的后代中,找出最小者 0218 protected static BinTreePosition findMinDescendant(BinTreePosition v) { 0219 if (null != v) 0220 while (v.hasLChild()) v = v.getLChild();//从v出发,沿左孩子链一直下降 0221 //至此,v或者为空,或者没有左孩子 0222 return v; 0223 } 0224 0225 //在v的后代中,找出最大者 0226 protected static BinTreePosition findMaxDescendant(BinTreePosition v) { 0227 if (null != v) 0228 while (v.hasRChild()) v = v.getRChild();//从v出发,沿右孩子链一直下降 0229 //至此,v或者为空,或者没有右孩子 0230 return v; 0231 } 0232 0233 //前序遍历以v为根节的(子)树 0234 protected static void preorder(List list, BinTreePosition v) { 0235 if (null == v) return;//递归基:空树 0236 list.insertLast(v);//访问v 0237 preorder(list, v.getLChild());//遍历左子树 0238 preorder(list, v.getRChild());//遍历右子树 0239 } 0240 0241 //中序遍历以v为根节的(子)树 0242 protected static void inorder(List list, BinTreePosition v) { 0243 if (null == v) return;//递归基:空树 0244 inorder(list, v.getLChild());//遍历左子树 0245 list.insertLast(v);//访问v 0246 inorder(list, v.getRChild());//遍历右子树 0247 } 0248 0249 //后序遍历以v为根节的(子)树 0250 protected static void postorder(List list, BinTreePosition v) { 0251 if (null == v) return;//递归基:空树 0252 postorder(list, v.getLChild());//遍历左子树 0253 postorder(list, v.getRChild());//遍历右子树 0254 list.insertLast(v);//访问v 0255 } 0256 0257 //层次遍历以v为根节的(子)树 0258 protected static void levelorder(List list, BinTreePosition v) { 0259 Queue_List Q = new Queue_List();//空队 0260 Q.enqueue(v);//根节点入队 0261 while (!Q.isEmpty()) { 0262 BinTreePosition u = (BinTreePosition) Q.dequeue();//出队 0263 list.insertLast(u);//访问v 0264 if (u.hasLChild()) Q.enqueue(u.getLChild()); 0265 if (u.hasRChild()) Q.enqueue(u.getRChild()); 0266 } 0267 } 0268 }