ツリーの追加削除操作
二叉ソートツリーは二叉検索ツリーとも呼ばれます.
-ルートノードの左サブツリーが空でない場合、左サブツリー上のすべてのノードのキー値はルートノードに等しいキーよりも小さくなります.
-ルートノードの右サブツリーが空でない場合、右サブツリー上のすべてのノードのキーはルートノードに等しいキーよりも大きくなります.
-ルートノードの左右のサブツリーも、それぞれ二叉ソートツリーです.
--ツリーのルート間ループは、キーワードの昇順で並べられています.
ノードクラス
-ルートノードの左サブツリーが空でない場合、左サブツリー上のすべてのノードのキー値はルートノードに等しいキーよりも小さくなります.
-ルートノードの右サブツリーが空でない場合、右サブツリー上のすべてのノードのキーはルートノードに等しいキーよりも大きくなります.
-ルートノードの左右のサブツリーも、それぞれ二叉ソートツリーです.
--ツリーのルート間ループは、キーワードの昇順で並べられています.
ノードクラス
package com.ITree.Demo;
public class BinaryOrderTreeNode
{
String name;
String action;
String grade;
BinaryOrderTreeNode left, right;
public BinaryOrderTreeNode(String name, String action, String grade)
{
this.name = name;
this.action = action;
this.grade = grade;
}
}
package com.ITree.Demo;
public class BinaryOrderTree
{
/**
*
*/
BinaryOrderTreeNode root;
/**
*
*
* @param name
* @param isPre
* @return
*/
private BinaryOrderTreeNode search(String name, boolean isPre)
{
BinaryOrderTreeNode res = null;
BinaryOrderTreeNode preNode = null;
BinaryOrderTreeNode node = root;
while (node != null && res == null)
{
int greater = name.compareTo(node.name);
// System.out.println("search:" + node.name);
if (greater == 0)
{
res = node;
}
else
{
preNode = node;
if (greater < 0)
node = node.left;
else
node = node.right;
}
}
if (isPre && res != null)
{
return preNode == null ? res : preNode;
}
return res;
}
/**
*
*
* @param name
*/
public void addNode(String name)
{
// System.out.println("addNode:" + name);
root = insert(name, root);
}
/**
*
*
* @param name
* @param node
* @return
*/
private BinaryOrderTreeNode insert(String name, BinaryOrderTreeNode node)
{
if (node == null)
{
node = new BinaryOrderTreeNode(name, "", "");
}
else
{
int greater = name.compareTo(node.name);
if (greater < 0)
{
node.left = insert(name, node.left);
}
else if (greater > 0)
{
node.right = insert(name, node.right);
}
}
return node;
}
public void removeNode(String name)
{
BinaryOrderTreeNode preNode = search(name, true);
// System.out.println("removeNode=" + name + " : " + preNode);
if (preNode != null)
{
// System.out.println("removeNode=" + name + " : " + preNode.name);
if (name.equals(preNode.name))
{
//
if (preNode.left != null)
{
root = preNode.left;
sortNode(preNode.right);
}
else
{
root = preNode.right;
}
preNode = null;
}
else
{
BinaryOrderTreeNode node = null;
if (preNode.left != null && name.equals(preNode.left.name))
{
//
node = preNode.left;
//
preNode.left = null;
}
else
{
//
node = preNode.right;
preNode.right = null;
}
if (node != null)
{
sortNode(node.left);
sortNode(node.right);
}
}
}
}
private void sortNode(BinaryOrderTreeNode data)
{
if (data != null)
{
// System.out.println("sortNode=" + data.name);
getNode(data);
}
}
private BinaryOrderTreeNode getNode(BinaryOrderTreeNode node)
{
if (node != null)
{
getNode(node.left);
// System.out.println("insert : " + node.name);
insert(node.name, root);
getNode(node.right);
}
return node;
}
public void update(BinaryOrderTreeNode data)
{
BinaryOrderTreeNode node = search(data.name, false);
// System.out.println("update=" + data.name + " : " + node);
if (node != null)
{
// System.out.println("update=" + data.name + " : " + node.name);
node.name = data.name;
node.action = data.action;
node.grade = data.grade;
}
else
{
addNode(data.name);
}
}
/**
*
*/
public void outPrint()
{
System.out.println("print start...");
inOrder(root);
System.out.println("
print end...
");
}
/**
*
*
* @param node
* @return
*/
private BinaryOrderTreeNode inOrder(BinaryOrderTreeNode node)
{
if (node != null)
{
inOrder(node.left);
System.out.print(" (" + node.name + "," + node.action + ","
+ node.grade + ")");
inOrder(node.right);
}
return node;
}
}
package com.ITree.Demo;
public class TreeManager
{
/**
* 1-add 2-del 3-update grade 123
*
* @param args
*/
public static void main(String[] args)
{
BinaryOrderTree tree = new BinaryOrderTree();
/**
*
*/
String[][] data = new String[][] { {"2", "2", "2" }, {"4", "0", "2" },
{"3", "2", "3" }, {"6", "0", "1" }, {"8", "0", "3" },
{"1", "0", "2" }, {"5", "0", "1" }, {"0", "2", "1" },
{"7", "0", "3" }, {"3", "3", "3" }, {"0", "1", "3" } };
int len = data.length;
for (int i = 0; i < len - 2; i++)
{
tree.addNode(data[i][0]);
tree.outPrint();
}
for (int i = 0; i < len; i++)
{
String action = data[i][1];
if (action == "1")
{
tree.addNode(data[i][0]);
tree.outPrint();
}
else if (action == "2")
{
tree.removeNode(data[i][0]);
tree.outPrint();
}
else if (action == "3")
{
tree.update(new BinaryOrderTreeNode(data[i][0], data[i][1],
data[i][2]));
tree.outPrint();
}
}
}
}