二叉木の並べ替え(Java)
5380 ワード
性質:左のサブツリーが空でない場合、左のサブツリーのすべてのノードの値は、そのルートノードの値よりも小さい。 右のサブツリーが空でない場合、右のサブツリーのすべてのノードの値は、そのルートノードの値よりも大きい。 左右の子木は、二叉の木を並べ替える である。
package com.answer.binaryTree;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
public class SortedBinTree {
private static class Node{
private Object data;
private Node left;
private Node right;
private Node parent;
public Node(Object data,Node parent,Node left,Node right){
this.data=data;
this.parent=parent;
this.left=left;
this.right=right;
}
public boolean compareTo(Object object){
if(this==object){
return true;
}
if(object.getClass()==Node.class){
Node target=(Node)object;
return data.equals(target.data)
&&left==target.left
&&right==target.right
&&parent==target.parent;
}return false;
}
public String toString(){
return "data:"+data;
}
}
private Node root;
public SortedBinTree(){
root=null;
}
public SortedBinTree(String data){
root=new Node(data,null,null,null);
}
public void insert(T data){
if(root==null){
root=new Node(data,null,null,null);
}else{
Node current=root;
Node parrent=null;
int cmp=0;
do{
parrent=current;
cmp=data.compareTo(current.data);
if(cmp<=0){
current=current.left;
}else{
current=current.right;
}
}while(current!=null);
Node node=new Node(data,parrent,null,null);
if(cmp<0){
parrent.left=node;
}else {
parrent.right=node;
}
}
}
public void remove(T data){
Node target=getNode(data);
if(target==null){
return;
}
if(target.left==null&&target.right==null){
if(target==root){
root=null;
}else {
if(target==target.parent.left){
target.parent.left=null;
}
else{
target.parent.right=null;
}
}
}else if(target.left!=null&&target.right==null){
if(target==root){
root=target.left;
}else {
if(target==target.parent.left){
target.parent.left=target.left;
}
else {
target.parent.right=target.left;
}
target.left.parent=target.parent;
}
}else if(target.left==null&&target.right!=null){
if(target==root){
root=target.right;
}else {
if(target==target.parent.left){
target.parent.left=target.right;
}
else{
target.parent.right=target.right;
}
target.right.parent=target.parent;
}
}else{// ,
Node leftMaxNode=target.left;
while(leftMaxNode.right!=null){
leftMaxNode=leftMaxNode.right;
}
leftMaxNode.parent.right=null;
leftMaxNode.parent=target.parent;
if(target==target.parent.left){
target.parent.left=leftMaxNode;
}else {
target.parent.right=leftMaxNode;
}
leftMaxNode.left=target.left;
leftMaxNode.right=target.right;
target.parent=target.left=target.right=null;
}
}
private Node getNode(T data) {
Node current=root;
while(current!=null){
int cmp=data.compareTo(current.data);
if(cmp<0){
current=current.left;
}else if(cmp>0){
current=current.right;
}else{
return current;
}
}
return null;
}
public ArrayList level(){
ArrayList list=new ArrayList<>();
Queue queue=new ArrayDeque<>();
if(root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
Node node=queue.remove();
list.add(node);
if(node.left!=null){
queue.add(node.left);
}
if (node.right!=null){
queue.add(node.right);
}
}return list;
}
public static void main(String[] args) {
SortedBinTree tree=new SortedBinTree<>();
tree.insert(5);
tree.insert(20);
tree.insert(10);
tree.insert(3);
tree.insert(8);
tree.insert(15);
tree.insert(30);
tree.insert(4);
System.out.println(tree.level());
tree.remove(20);
System.out.println(tree.level());
}
}