当前位置：首页 > news >正文

9、二叉树存储结构结点定义：三叉链表

news 来源：原创 2024/5/20 6:15:24

  1 package ren.laughing.datastructure.baseImpl;
  2 
  3 import ren.laughing.datastructure.base.Node;
  4 /**
  5  * 二叉树存储结构结点定义：三叉链表
  6  * 三个指针域包含父结点、左孩子、右孩子
  7  * @author Laughing_Lz
  8  * @time 2016年4月13日
  9  */
 10 public class BinTreeNode implements Node{
 11     private Object data;//数据域
 12     private BinTreeNode parent;//父结点
 13     private BinTreeNode lChild;//左孩子
 14     private BinTreeNode rChild;//右孩子
 15     private int height;//以该结点为根的子树高度
 16     private int size;//该结点子孙数，包含该结点本身
 17 
 18     public BinTreeNode() {
 19         this(null);
 20     }
 21 
 22     public BinTreeNode(Object data) {
 23         this.parent = null;
 24         this.lChild = null;
 25         this.rChild = null;
 26         this.size = 1;
 27         this.height = 0;
 28         this.data = data;
 29     }
 30 
 31     @Override
 32     public Object getData() {
 33         return data;
 34     }
 35 
 36     @Override
 37     public void setData(Object obj) {
 38         data = obj;
 39     }
 40     //has
 41     public boolean hasParent(){
 42         return parent != null;
 43     }
 44     public boolean hasLChild(){
 45         return lChild != null;
 46     }
 47     public boolean hasRChild(){
 48         return rChild != null;
 49     }
 50     //is
 51     public boolean isLeaf(){
 52         return !hasLChild()&&!hasRChild();
 53     }
 54     public boolean isLChild(){
 55         return hasParent()&&this == parent.lChild;
 56     }
 57     public boolean isRChild(){
 58         return hasParent()&&this == parent.rChild;
 59     }
 60     //get
 61     public int getHeight(){
 62         return height;
 63     }
 64     public int getSize(){
 65         return size;
 66     }
 67     public BinTreeNode getLChild(){
 68         return lChild;
 69     }
 70     public BinTreeNode getRChild(){
 71         return rChild;
 72     }
 73     public BinTreeNode getParent(){
 74         return parent;
 75     }
 76     
 77     //operate
 78     //★更新以结点为根的子树高度
 79     public void updateHeight(){
 80         int newH = 0;
 81         if (hasLChild()) {
 82             newH = Math.max(newH, getLChild().getHeight()+1);
 83         }
 84         if (hasRChild()) {
 85             newH = Math.max(newH, getRChild().getHeight()+1);
 86         }
 87         if(newH == height){
 88             return;
 89         }
 90         height = newH;
 91         if(hasParent()){
 92             this.getParent().updateHeight();//★递归更新父结点高度
 93         }
 94     }
 95     //更新该结点的子孙数
 96     public void updateSize(){
 97         size = 1;
 98         if(hasLChild()){
 99             size = size+getLChild().size;
100         }
101         if(hasRChild()){
102             size= size+getRChild().size;
103         }
104         if(hasParent()){
105             this.getParent().updateSize();
106         }
107     }
108     //断开与父结点的关联
109     public void server(){
110         if(hasParent()){
111             if(this == getParent().getLChild()){
112                 getParent().lChild = null;
113             }
114             if(this == getParent().getRChild()){
115                 getParent().rChild = null;
116             }
117             getParent().updateHeight();
118             getParent().updateSize();
119             parent = null;
120         }
121     }
122     public BinTreeNode setLChild(BinTreeNode lc){
123         BinTreeNode oldLChild = lChild;
124         if(hasLChild()){
125             lChild.server();
126         }
127         if(lc != null){
128             lc.server();
129             this.lChild = lc;
130             lc.parent = this;
131             this.updateHeight();
132             this.updateSize();
133         }
134         return oldLChild;
135     }
136     public BinTreeNode setRChild(BinTreeNode rc){
137         BinTreeNode oldRChild = rChild;
138         if(hasRChild()){
139             rChild.server();
140         }
141         if(rc != null){
142             rc.server();
143             this.rChild = rc;
144             rc.parent = this;
145             this.updateHeight();
146             this.updateSize();
147         }
148         return oldRChild;
149     }
150 }