《Java数据结构跟算法》第二版 Robert lafore 编程作业 第十章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第十章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第十章
/*
编程作业
10.1 这个作业很容易。编写一个方法能返回2-3-4树中的最小值.
10.2 编写方法中序遍历2-3-4树。它能有序地显示所有的数据项。
10.3 2-3-4树可以用于排序。编写sort()方法，从main()方法中传入关键字的数组
并在排序后把它们写回数组中去。
10.4 修改tree234.java程序（清单10.1），使它可以创建并操作2-3树。要求显示
树并可以查找。还要能够插入数据项，但是只限在叶节点（要分裂的）的父节
点不需要再分裂的情况。这就是说split()方法不需要递归。编写insert()方
法，记得在找到要插入合适的叶节点之前不需要节点分裂。找到后，如果叶节
点满了就要分裂。也需要能够分裂根，但只限它是叶节点的情况下。根据这个
限制，只能插入少于9个数据项，否则程序就会起冲突了。
10.5 扩展编程作业10.4的程序，使split()方法是递归的并可以处理一个满的子节
点的满父节点的情况。这就允许不限个数地插入节点。注意在递归的split()
例程中，在决定数据项要转向何处和子节点要连接到哪个里之前要先分裂父节
点。
*/
package chap10;
// tree234.java
// demonstrates 234 tree
// to run this program: C>java Tree234App
import java.io.*;
////////////////////////////////////////////////////////////////
class DataItem {
public long dData; // one data item
// --------------------------
public DataItem(long dd) // constructor
{
dData = dd;
}
// --------------------------
public void displayItem() // display item, format "/27"
{
System.out.print("/" + dData);
}
// --------------------------
} // end class DataItem
// //////////////////////////////////////////////////////////////
class Node {
private static final int ORDER = 4;
private int numItems;
private Node parent;
private Node childArray[] = new Node[ORDER];
private DataItem itemArray[] = new DataItem[ORDER - 1];
// -------------------------
// connect child to this node
public void connectChild(int childNum, Node child) {
childArray[childNum] = child;
if (child != null)
child.parent = this;
}
// -------------------------
// disconnect child from this node, return it
public Node disconnectChild(int childNum) {
Node tempNode = childArray[childNum];
childArray[childNum] = null;
return tempNode;
}
// -------------------------
public Node getChild(int childNum) {
return childArray[childNum];
}
// -------------------------
public Node getParent() {
return parent;
}
// -------------------------
public boolean isLeaf() {
return (childArray[0] == null) ? true : false;
}
// -------------------------
public int getNumItems() {
return numItems;
}
// -------------------------
public DataItem getItem(int index) // get DataItem at index
{
return itemArray[index];
}
// -------------------------
public boolean isFull() {
return (numItems == ORDER - 1) ? true : false;
}
// -------------------------
public int findItem(long key) // return index of
{ // item (within node)
for (int j = 0; j < ORDER - 1; j++) // if found,
{ // otherwise,
if (itemArray[j] == null) // return -1
break;
else if (itemArray[j].dData == key)
return j;
}
return -1;
} // end findItem
// -------------------------
public int insertItem(DataItem newItem) {
// assumes node is not full
numItems++; // will add new item
long newKey = newItem.dData; // key of new item
for (int j = ORDER - 2; j >= 0; j--) // start on right,
{ // examine items
if (itemArray[j] == null) // if item null,
continue; // go left one cell
else // not null,
{ // get its key
long itsKey = itemArray[j].dData;
if (newKey < itsKey) // if it's bigger
itemArray[j + 1] = itemArray[j]; // shift it right
else {
itemArray[j + 1] = newItem; // insert new item
return j + 1; // return index to
} // new item
} // end else (not null)
} // end for // shifted all items,
itemArray[0] = newItem; // insert new item
return 0;
} // end insertItem()
// -------------------------
public DataItem removeItem() // remove largest item
{
// assumes node not empty
DataItem temp = itemArray[numItems - 1]; // save item
itemArray[numItems - 1] = null; // disconnect it
numItems--; // one less item
return temp; // return item
}
// -------------------------
public void displayNode() // format "/24/56/74/"
{
for (int j = 0; j < numItems; j++)
itemArray[j].displayItem(); // "/56"
System.out.println("/"); // final "/"
}
// -------------------------
} // end class Node
// //////////////////////////////////////////////////////////////
class Tree234 {
private Node root = new Node(); // make root node
// -------------------------
public int find(long key) {
Node curNode = root;
int childNumber;
while (true) {
if ((childNumber = curNode.findItem(key)) != -1)
return childNumber; // found it
else if (curNode.isLeaf())
return -1; // can't find it
else
// search deeper
curNode = getNextChild(curNode, key);
} // end while
}
// -------------------------
// insert a DataItem
public void insert(long dValue) {
Node curNode = root;
DataItem tempItem = new DataItem(dValue);
while (true) {
if (curNode.isFull()) // if node full,
{
split(curNode); // split it
curNode = curNode.getParent(); // back up
// search once
curNode = getNextChild(curNode, dValue);
} // end if(node is full)
else if (curNode.isLeaf()) // if node is leaf,
break; // go insert
// node is not full, not a leaf; so go to lower level
else
curNode = getNextChild(curNode, dValue);
} // end while
curNode.insertItem(tempItem); // insert new DataItem
} // end insert()
// -------------------------
public void split(Node thisNode) // split the node
{
// assumes node is full
DataItem itemB, itemC;
Node parent, child2, child3;
int itemIndex;
itemC = thisNode.removeItem(); // remove items from
itemB = thisNode.removeItem(); // this node
child2 = thisNode.disconnectChild(2); // remove children
child3 = thisNode.disconnectChild(3); // from this node
Node newRight = new Node(); // make new node
if (thisNode == root) // if this is the root,
{
root = new Node(); // make new root
parent = root; // root is our parent
root.connectChild(0, thisNode); // connect to parent
} else
// this node not the root
parent = thisNode.getParent(); // get parent
// deal with parent
itemIndex = parent.insertItem(itemB); // item B to parent
int n = parent.getNumItems(); // total items?
for (int j = n - 1; j > itemIndex; j--) // move parent's
{ // connections
Node temp = parent.disconnectChild(j); // one child
parent.connectChild(j + 1, temp); // to the right
}
// connect newRight to parent
parent.connectChild(itemIndex + 1, newRight);
// deal with newRight
newRight.insertItem(itemC); // item C to newRight
newRight.connectChild(0, child2); // connect to 0 and 1
newRight.connectChild(1, child3); // on newRight
} // end split()
// -------------------------
// gets appropriate child of node during search for value
public Node getNextChild(Node theNode, long theValue) {
int j;
// assumes node is not empty, not full, not a leaf
int numItems = theNode.getNumItems();
for (j = 0; j < numItems; j++) // for each item in node
{ // are we less?
if (theValue < theNode.getItem(j).dData)
return theNode.getChild(j); // return left child
} // end for // we're greater, so
return theNode.getChild(j); // return right child
}
// -------------------------
public void displayTree() {
recDisplayTree(root, 0, 0);
}
// -------------------------
private void recDisplayTree(Node thisNode, int level, int childNumber) {
System.out.print("level=" + level + " child=" + childNumber + " ");
thisNode.displayNode(); // display this node
// call ourselves for each child of this node
int numItems = thisNode.getNumItems();
for (int j = 0; j < numItems + 1; j++) {
Node nextNode = thisNode.getChild(j);
if (nextNode != null)
recDisplayTree(nextNode, level + 1, j);
else
return;
}
} // end recDisplayTree()
// -------------------------
// ==============================================================
// 编程作业 10.1
// 这里没有考虑空树的情况，调用前确保树不为空
public long getMinValue() {
Node parent = root;
Node current = root;
while (current != null) {
parent = current;
current = current.getChild(0);
}
return parent.getItem(0).dData;
}
// ==============================================================
public void traverse(int traverseType) {
switch (traverseType) {
case 1:
System.out.print("\nPreorder traversal: ");
// preOrder(root);
break;
case 2:
System.out.print("\nInorder traversal: ");
inOrder(root);
break;
case 3:
System.out.print("\nPostorder traversal: ");
// postOrder(root);
break;
}
System.out.println();
}
// ==============================================================
// 编程作业 10.2
private void inOrder(Node root) {
if (root == null) {
return;
}
int i = 0;
for (; i < root.getNumItems(); i++) {
inOrder(root.getChild(i));
System.out.print(root.getItem(i).dData + " ");
}
if (i != 0) {
inOrder(root.getChild(i));
}
}
// ==============================================================
// 编程作业 10.3
public void sort(long[] array) {
this.root = new Node();
for (int i = 0; i < array.length; i++) {
this.insert(array[i]);
}
inOrderForSort(array, root, 0);
}
// ==============================================================
private int inOrderForSort(long[] array, Node root, int arrayIndex) {
if (root == null) {
return arrayIndex;
}
int i = 0;
for (; i < root.getNumItems(); i++) {
arrayIndex = inOrderForSort(array, root.getChild(i), arrayIndex);
array[arrayIndex++] = root.getItem(i).dData; // arrayIndex只在这里增加
}
if (i != 0) {
arrayIndex = inOrderForSort(array, root.getChild(i), arrayIndex);
}
return arrayIndex;
}
// ==============================================================
} // end class Tree234
// //////////////////////////////////////////////////////////////
public class Tree234App {
public static void main(String[] args) throws IOException {
long value;
Tree234 theTree = new Tree234();
theTree.insert(10);
theTree.insert(20);
theTree.insert(50);
theTree.insert(40);
theTree.insert(60);
theTree.insert(30);
theTree.insert(70);
// ========================================
// 编程作业 10.1
System.out.println(theTree.getMinValue());
// ========================================
// 编程作业 10.2
theTree.traverse(2);// 中序遍历
// ========================================
// 编程作业 10.3
long[] array = { 1, 2, 3, 4, 8, 7, 6, 5 };
theTree.sort(array);
for (long l : array) {
System.out.print(l + " ");
}
// ========================================
} // end main()
// --------------------------
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// --------------------------
public static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}
// -------------------------
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
// -------------------------
} // end class Tree234App
// //////////////////////////////////////////////////////////////
package chap10;
// tree234.java
// demonstrates 234 tree
// to run this program: C>java Tree234App
import java.io.*;
////////////////////////////////////////////////////////////////
class Node1 {
private static final int ORDER = 3;
private int numItems;
private Node1 parent;
private Node1 childArray[] = new Node1[ORDER];
private DataItem itemArray[] = new DataItem[ORDER - 1];
// -------------------------
// connect child to this node
public void connectChild(int childNum, Node1 child) {
childArray[childNum] = child;
if (child != null)
child.parent = this;
}
// -------------------------
// disconnect child from this node, return it
public Node1 disconnectChild(int childNum) {
Node1 tempNode = childArray[childNum];
childArray[childNum] = null;
return tempNode;
}
// -------------------------
public Node1 getChild(int childNum) {
return childArray[childNum];
}
// -------------------------
public Node1 getParent() {
return parent;
}
// -------------------------
public boolean isLeaf() {
return (childArray[0] == null) ? true : false;
}
// -------------------------
public int getNumItems() {
return numItems;
}
// -------------------------
public DataItem getItem(int index) // get DataItem at index
{
return itemArray[index];
}
// -------------------------
public boolean isFull() {
return (numItems == ORDER - 1) ? true : false;
}
// -------------------------
public int findItem(long key) // return index of
{ // item (within node)
for (int j = 0; j < ORDER - 1; j++) // if found,
{ // otherwise,
if (itemArray[j] == null) // return -1
break;
else if (itemArray[j].dData == key)
return j;
}
return -1;
} // end findItem
// -------------------------
public int insertItem(DataItem newItem) {
// assumes node is not full
numItems++; // will add new item
long newKey = newItem.dData; // key of new item
for (int j = ORDER - 2; j >= 0; j--) // start on right,
{ // examine items
if (itemArray[j] == null) // if item null,
continue; // go left one cell
else // not null,
{ // get its key
long itsKey = itemArray[j].dData;
if (newKey < itsKey) // if it's bigger
itemArray[j + 1] = itemArray[j]; // shift it right
else {
itemArray[j + 1] = newItem; // insert new item
return j + 1; // return index to
} // new item
} // end else (not null)
} // end for // shifted all items,
itemArray[0] = newItem; // insert new item
return 0;
} // end insertItem()
// -------------------------
public DataItem removeItem() // remove largest item
{
// assumes node not empty
DataItem temp = itemArray[numItems - 1]; // save item
itemArray[numItems - 1] = null; // disconnect it
numItems--; // one less item
return temp; // return item
}
// -------------------------
public void displayNode() // format "/24/56/74/"
{
for (int j = 0; j < numItems; j++)
itemArray[j].displayItem(); // "/56"
System.out.println("/"); // final "/"
}
// -------------------------
} // end class Node
// //////////////////////////////////////////////////////////////
class Tree23 {
private Node1 root = new Node1(); // make root node
// -------------------------
public int find(long key) {
Node1 curNode = root;
int childNumber;
while (true) {
if ((childNumber = curNode.findItem(key)) != -1)
return childNumber; // found it
else if (curNode.isLeaf())
return -1; // can't find it
else
// search deeper
curNode = getNextChild(curNode, key);
} // end while
}
// -------------------------
// insert a DataItem
public void insert(long dValue) {
Node1 curNode = root;
DataItem tempItem = new DataItem(dValue);
while (true) {
if (curNode.isLeaf()) // if node is leaf,
break; // go insert
// node is not full, not a leaf; so go to lower level
else
curNode = getNextChild(curNode, dValue);
} // end while
if (curNode.isFull()) {
// split(curNode, tempItem); //只能分裂叶节点
split1(curNode, tempItem, null); // 可以递归分裂
} else {
curNode.insertItem(tempItem); // insert new DataItem
}
} // end insert()
// -------------------------
// =============================================================
// 编程作业 10.4
// thisNode 当前要分裂的节点 ,只能为叶子这点
// newItem 要插入的数据项
public void split(Node1 thisNode, DataItem newItem) // split the node
{
// assumes node is full
DataItem itemB, itemC; // itemB保存中间数据项,itemC保存最大数据项
Node1 parent, child1, child2;
int itemIndex;
// 分裂当前节点
// 根据新数据项与当前节点中两个数据项的比较，分三种情况：
if (thisNode.getItem(0).dData > newItem.dData) { // 1.新数据项最小
itemC = thisNode.removeItem();
itemB = thisNode.removeItem();
thisNode.insertItem(newItem);
} else if (thisNode.getItem(1).dData < newItem.dData) {// 2.新数据项最大
itemC = newItem;
itemB = thisNode.removeItem();
} else {// 3.新数据项在中间
itemC = thisNode.removeItem();
itemB = newItem;
}
// 新节点
Node1 newRight = new Node1(); // make new node
newRight.insertItem(itemC); // item C to newRight
// 得到父节点
if (thisNode != root) {
parent = thisNode.getParent();
} else {
root = new Node1(); // make new root
parent = root; // root is our parent
root.connectChild(0, thisNode); // connect to parent
}
// 中间数据项插入到父节点
if (parent.isFull()) {
System.out.println("还未实现父节点分裂！！！");
} else {
itemIndex = parent.insertItem(itemB);
int n = parent.getNumItems(); // total items?
for (int j = n - 1; j > itemIndex; j--) // move parent's
{ // connections
Node1 temp = parent.disconnectChild(j); // one child
parent.connectChild(j + 1, temp); // to the right
}
// connect newRight to parent
parent.connectChild(itemIndex + 1, newRight);
}
} // end split()
// =============================================================
// 编程作业 10.5
// thisNode 当前要分裂的节点
// newItem 要插入的数据项
// newNode 上次分裂(子节点分裂)得到的新节点，如果是第一次分裂(叶节点分裂)，则为null
public void split1(Node1 thisNode, DataItem newItem, Node1 newNode) {
// assumes node is full
DataItem itemB, itemC; // itemB保存中间数据项,itemC保存最大数据项
Node1 parent, child1, child2, newRight;
int itemIndex;
// 分裂当前节点
// 根据新数据项与当前节点中两个数据项的比较，分三种情况：
if (thisNode.getItem(0).dData > newItem.dData) { // 1.新数据项最小
itemC = thisNode.removeItem();
itemB = thisNode.removeItem();
thisNode.insertItem(newItem);
child1 = thisNode.disconnectChild(1);
child2 = thisNode.disconnectChild(2);
thisNode.connectChild(1, newNode);
newRight = new Node1(); // make new node
newRight.insertItem(itemC); // item C to newRight
newRight.connectChild(0, child1);
newRight.connectChild(1, child2);
} else if (thisNode.getItem(1).dData < newItem.dData) { // 2.新数据项最大
itemC = newItem;
itemB = thisNode.removeItem();
child2 = thisNode.disconnectChild(2);
newRight = new Node1(); // make new node
newRight.insertItem(itemC); // item C to newRight
newRight.connectChild(0, child2);
newRight.connectChild(1, newNode);
} else { // 3.新数据项在中间
itemC = thisNode.removeItem();
itemB = newItem;
child2 = thisNode.disconnectChild(2);
newRight = new Node1(); // make new node
newRight.insertItem(itemC); // item C to newRight
newRight.connectChild(0, newNode);
newRight.connectChild(1, child2);
}
// 得到父节点
if (thisNode != root) { // 当前节点是非根节点
parent = thisNode.getParent();
} else {// 当前节点是根节点
root = new Node1(); // make new root
parent = root; // root is our parent
root.connectChild(0, thisNode); // connect to parent
}
// 中间数据项插入到父节点
if (parent.isFull()) { // 父节点是满，则递归分裂父节点
split1(parent, itemB, newRight);
} else { // 父节点不满，直接插入
itemIndex = parent.insertItem(itemB);
// 调整相应的子节点
if (itemIndex == 0) {// 插入到第一个
parent.connectChild(2, parent.disconnectChild(1));
parent.connectChild(1, newRight);
} else { // 插入到第二个
parent.connectChild(2, newRight);
}
}
} // end split()
// =============================================================
// -------------------------
// gets appropriate child of node during search for value
public Node1 getNextChild(Node1 theNode, long theValue) {
int j;
// assumes node is not empty, not full, not a leaf
int numItems = theNode.getNumItems();
for (j = 0; j < numItems; j++) // for each item in node
{ // are we less?
if (theValue < theNode.getItem(j).dData)
return theNode.getChild(j); // return left child
} // end for // we're greater, so
return theNode.getChild(j); // return right child
}
// -------------------------
public void displayTree() {
recDisplayTree(root, 0, 0);
}
// -------------------------
private void recDisplayTree(Node1 thisNode, int level, int childNumber) {
System.out.print("level=" + level + " child=" + childNumber + " ");
thisNode.displayNode(); // display this node
// call ourselves for each child of this node
int numItems = thisNode.getNumItems();
for (int j = 0; j < numItems + 1; j++) {
Node1 nextNode = thisNode.getChild(j);
if (nextNode != null)
recDisplayTree(nextNode, level + 1, j);
else
return;
}
} // end recDisplayTree()
// -------------------------\
} // end class Tree234
// //////////////////////////////////////////////////////////////
public class Tree23App {
public static void main(String[] args) throws IOException {
long value;
Tree23 theTree = new Tree23();
// ==================================================
// 编程作业 10.4
// theTree.insert(50);
// theTree.insert(40);
// theTree.insert(60);
// theTree.insert(30);
// theTree.insert(70);
// theTree.insert(80);
// theTree.insert(90);
// theTree.insert(65);
// // theTree.insert(20); //只能插入少于9个数据项
// ==================================================
// 编程作业 10.5
theTree.insert(50);
theTree.insert(40);
theTree.insert(60);
theTree.insert(30);
theTree.insert(70);
theTree.insert(80);
theTree.insert(90);
theTree.insert(65);
theTree.insert(100);
theTree.insert(85);
theTree.insert(95);
theTree.insert(86);
// ==================================================
while (true) {
System.out.print("Enter first letter of ");
System.out.print("show, insert, or find: ");
char choice = getChar();
switch (choice) {
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
int found = theTree.find(value);
if (found != -1)
System.out.println("Found " + value);
else
System.out.println("Could not find " + value);
break;
default:
System.out.print("Invalid entry\n");
} // end switch
} // end while
} // end main()
// --------------------------
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// --------------------------
public static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}
// -------------------------
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
// -------------------------
} // end class Tree234App
// //////////////////////////////////////////////////////////////