- it
- 数据结构学习JAVA(四)树
public class Tree {
class Node {
private Integer data
;
private Node left
;
private Node right
;
private Node parent
;
public Node(Integer data
) {
this.data
= data
;
this.left
= null
;
this.right
= null
;
this.parent
= null
;
}
}
private Node root
;
public Tree(Integer data
) {
this.root
= new Node(data
);
}
public void append(Integer data
) {
append(data
, this.root
);
}
public void append(Integer data
, Node parent
) {
if (data
> parent
.data
) {
if (parent
.right
== null
) {
System
.out
.println("添加成功,添加的为右节点。值为" + data
);
parent
.right
= new Node(data
);
parent
.right
.parent
= parent
;
return;
} else {
append(data
, parent
.right
);
}
} else if (data
== parent
.data
) {
System
.out
.println("添加失败,树中已存在该节点");
} else {
if (parent
.left
== null
) {
System
.out
.println("添加成功,添加的为左节点。值为" + data
);
parent
.left
= new Node(data
);
parent
.left
.parent
= parent
;
} else {
append(data
, parent
.left
);
return;
}
}
}
public void preorder() {
preorder(this.root
);
}
private void preorder(Node node
) {
if (node
!= null
) {
System
.out
.print(node
.data
+ " ");
preorder(node
.left
);
preorder(node
.right
);
}
}
public void inorder() {
inorder(this.root
);
}
private void inorder(Node node
) {
if (node
!= null
) {
inorder(node
.left
);
System
.out
.print(node
.data
+ " ");
inorder(node
.right
);
}
}
public void Subsequent() {
Subsequent(this.root
);
}
private void Subsequent(Node node
) {
if (node
!= null
) {
Subsequent(node
.left
);
Subsequent(node
.right
);
System
.out
.print(node
.data
+ " ");
}
}
public int treeDepth() {
return treeDepth(this.root
);
}
private int treeDepth(Node node
) {
if (node
== null
) {
return 0;
} else {
Integer left
= treeDepth(node
.left
);
Integer right
= treeDepth(node
.right
);
return left
> right
? left
+ 1 : right
+ 1;
}
}
public Boolean
find(Integer data
) {
return find(this.root
, data
);
}
private Boolean
find(Node node
, Integer data
) {
if (node
== null
) {
return false;
}
if (node
.data
.equals(data
)) {
return true;
}
if (node
.data
< data
) {
return find(node
.right
, data
);
} else {
return find(node
.left
, data
);
}
}
public void mergeTree(Tree tree
){
mergeTree(tree
.root
);
}
private void mergeTree(Node node
){
if(node
!=null
){
this.append(node
.data
);
}else{
return;
}
mergeTree(node
.left
);
mergeTree(node
.right
);
}
public boolean removeNode(Integer number
) {
return removeNode(this.root
, number
);
}
private void append(Node node
){
if(node
==null
){
return;
}
this.append(node
.data
);
append(node
.left
);
append(node
.right
);
}
private boolean removeNode(Node node
, Integer number
) {
while (true) {
if (node
== null
) {
return false;
}
if (node
.data
== number
) {
if (node
.parent
.left
== node
) {
node
.parent
.left
= node
.left
;
} else {
node
.parent
.right
= node
.left
;
}
this.append(node
.right
);
return true;
}
if (node
.data
> number
) {
node
= node
.left
;
} else {
node
= node
.right
;
}
}
}
}
