0001 /* 0002 * 二叉树节点ADT接口 0003 */ 0004 0005 package dsa; 0006 0007 public interface BinTreePosition extends Position { 0008 //判断是否有父亲(为使代码描述简洁) 0009 public boolean hasParent(); 0010 //返回当前节点的父节点 0011 public BinTreePosition getParent(); 0012 //设置当前节点的父节点 0013 public void setParent(BinTreePosition p); 0014 0015 //判断是否为叶子 0016 public boolean isLeaf(); 0017 0018 //判断是否为左孩子(为使代码描述简洁) 0019 public boolean isLChild(); 0020 0021 //判断是否有左孩子(为使代码描述简洁) 0022 public boolean hasLChild(); 0023 //返回当前节点的左孩子 0024 public BinTreePosition getLChild(); 0025 //设置当前节点的左孩子(注意:this.lChild和c.parent都不一定为空) 0026 public void setLChild(BinTreePosition c); 0027 0028 //判断是否为右孩子(为使代码描述简洁) 0029 public boolean isRChild(); 0030 //判断是否有右孩子(为使代码描述简洁) 0031 public boolean hasRChild(); 0032 //返回当前节点的右孩子 0033 public BinTreePosition getRChild(); 0034 //设置当前节点的右孩子(注意:this.rChild和c.parent都不一定为空) 0035 public void setRChild(BinTreePosition c); 0036 0037 //返回当前节点后代元素的数目 0038 public int getSize(); 0039 //在孩子发生变化后,更新当前节点及其祖先的规模 0040 public void updateSize(); 0041 0042 //返回当前节点的高度 0043 public int getHeight(); 0044 //在孩子发生变化后,更新当前节点及其祖先的高度 0045 public void updateHeight(); 0046 0047 //返回当前节点的深度 0048 public int getDepth(); 0049 //在父亲发生变化后,更新当前节点及其后代的深度 0050 public void updateDepth(); 0051 0052 //按照中序遍历的次序,找到当前节点的直接前驱 0053 public BinTreePosition getPrev(); 0054 0055 //按照中序遍历的次序,找到当前节点的直接后继 0056 public BinTreePosition getSucc(); 0057 0058 //断绝当前节点与其父亲的父子关系 0059 //返回当前节点 0060 public BinTreePosition secede(); 0061 0062 //将节点c作为当前节点的左孩子 0063 public BinTreePosition attachL(BinTreePosition c); 0064 0065 //将节点c作为当前节点的右孩子 0066 public BinTreePosition attachR(BinTreePosition c); 0067 0068 //前序遍历 0069 public Iterator elementsPreorder(); 0070 0071 //中序遍历 0072 public Iterator elementsInorder(); 0073 0074 //后序遍历 0075 public Iterator elementsPostorder(); 0076 0077 //层次遍历 0078 public Iterator elementsLevelorder(); 0079 }