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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注