《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&gt;java Tree234Appimport 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 nodepublic void connectChild(int childNum, Node child) {childArray[childNum] = child;if (child != null)child.parent = this;}// -------------------------// disconnect child from this node, return itpublic 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 &lt; ORDER - 1; j++)         // if found,{                                 // otherwise,if (itemArray[j] == null)          // return -1break;else if (itemArray[j].dData == key)return j;}return -1;}  // end findItem// -------------------------public int insertItem(DataItem newItem) {// assumes node is not fullnumItems++;                          // will add new itemlong newKey = newItem.dData;         // key of new itemfor (int j = ORDER - 2; j &gt;= 0; j--)        // start on right,{                                 // examine itemsif (itemArray[j] == null)          // if item null,continue;                      // go left one cellelse                              // not null,{                              // get its keylong itsKey = itemArray[j].dData;if (newKey &lt; itsKey)            // if it's biggeritemArray[j + 1] = itemArray[j]; // shift it rightelse {itemArray[j + 1] = newItem;   // insert new itemreturn j + 1;                 // return index to}                           // new item}  // end else (not null)}  // end for // shifted all items,itemArray[0] = newItem;              // insert new itemreturn 0;}  // end insertItem()// -------------------------public DataItem removeItem()        // remove largest item{// assumes node not emptyDataItem temp = itemArray[numItems - 1];  // save itemitemArray[numItems - 1] = null;           // disconnect itnumItems--;                             // one less itemreturn temp;                            // return item}// -------------------------public void displayNode()           // format "/24/56/74/"{for (int j = 0; j &lt; 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 itelse if (curNode.isLeaf())return -1;                        // can't find itelse// search deepercurNode = getNextChild(curNode, key);}  // end while}// -------------------------// insert a DataItempublic void insert(long dValue) {Node curNode = root;DataItem tempItem = new DataItem(dValue);while (true) {if (curNode.isFull())               // if node full,{split(curNode);                   // split itcurNode = curNode.getParent();    // back up// search oncecurNode = 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 levelelsecurNode = getNextChild(curNode, dValue);}  // end whilecurNode.insertItem(tempItem);       // insert new DataItem}  // end insert()// -------------------------public void split(Node thisNode)     // split the node{// assumes node is fullDataItem itemB, itemC;Node parent, child2, child3;int itemIndex;itemC = thisNode.removeItem();    // remove items fromitemB = thisNode.removeItem();    // this nodechild2 = thisNode.disconnectChild(2); // remove childrenchild3 = thisNode.disconnectChild(3); // from this nodeNode newRight = new Node();       // make new nodeif (thisNode == root)                // if this is the root,{root = new Node();                // make new rootparent = root;                    // root is our parentroot.connectChild(0, thisNode);   // connect to parent} else// this node not the rootparent = thisNode.getParent();    // get parent// deal with parentitemIndex = parent.insertItem(itemB); // item B to parentint n = parent.getNumItems();         // total items?for (int j = n - 1; j &gt; itemIndex; j--)          // move parent's{                                      // connectionsNode temp = parent.disconnectChild(j); // one childparent.connectChild(j + 1, temp);        // to the right}// connect newRight to parentparent.connectChild(itemIndex + 1, newRight);// deal with newRightnewRight.insertItem(itemC);       // item C to newRightnewRight.connectChild(0, child2); // connect to 0 and 1newRight.connectChild(1, child3); // on newRight}  // end split()// -------------------------// gets appropriate child of node during search for valuepublic Node getNextChild(Node theNode, long theValue) {int j;// assumes node is not empty, not full, not a leafint numItems = theNode.getNumItems();for (j = 0; j &lt; numItems; j++)          // for each item in node{                               // are we less?if (theValue &lt; theNode.getItem(j).dData)return theNode.getChild(j);  // return left child}  // end for // we're greater, soreturn 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 nodeint numItems = thisNode.getNumItems();for (int j = 0; j &lt; numItems + 1; j++) {Node nextNode = thisNode.getChild(j);if (nextNode != null)recDisplayTree(nextNode, level + 1, j);elsereturn;}}  // 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.2private void inOrder(Node root) {if (root == null) {return;}int i = 0;for (; i &lt; root.getNumItems(); i++) {inOrder(root.getChild(i));System.out.print(root.getItem(i).dData + " ");}if (i != 0) {inOrder(root.getChild(i));}}// ==============================================================// 编程作业 10.3public void sort(long[] array) {this.root = new Node();for (int i = 0; i &lt; 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 &lt; 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.1System.out.println(theTree.getMinValue());// ========================================// 编程作业 10.2theTree.traverse(2);// 中序遍历// ========================================// 编程作业 10.3long[] 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&gt;java Tree234Appimport 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 nodepublic void connectChild(int childNum, Node1 child) {childArray[childNum] = child;if (child != null)child.parent = this;}// -------------------------// disconnect child from this node, return itpublic 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 &lt; ORDER - 1; j++)         // if found,{                                 // otherwise,if (itemArray[j] == null)          // return -1break;else if (itemArray[j].dData == key)return j;}return -1;}  // end findItem// -------------------------public int insertItem(DataItem newItem) {// assumes node is not fullnumItems++;                          // will add new itemlong newKey = newItem.dData;         // key of new itemfor (int j = ORDER - 2; j &gt;= 0; j--)        // start on right,{                                 // examine itemsif (itemArray[j] == null)          // if item null,continue;                      // go left one cellelse                              // not null,{                              // get its keylong itsKey = itemArray[j].dData;if (newKey &lt; itsKey)            // if it's biggeritemArray[j + 1] = itemArray[j]; // shift it rightelse {itemArray[j + 1] = newItem;   // insert new itemreturn j + 1;                 // return index to}                           // new item}  // end else (not null)}  // end for // shifted all items,itemArray[0] = newItem;              // insert new itemreturn 0;}  // end insertItem()// -------------------------public DataItem removeItem()        // remove largest item{// assumes node not emptyDataItem temp = itemArray[numItems - 1];  // save itemitemArray[numItems - 1] = null;           // disconnect itnumItems--;                             // one less itemreturn temp;                            // return item}// -------------------------public void displayNode()           // format "/24/56/74/"{for (int j = 0; j &lt; 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 itelse if (curNode.isLeaf())return -1;                        // can't find itelse// search deepercurNode = getNextChild(curNode, key);}  // end while}// -------------------------// insert a DataItempublic 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 levelelsecurNode = getNextChild(curNode, dValue);}  // end whileif (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 fullDataItem itemB, itemC; // itemB保存中间数据项,itemC保存最大数据项Node1 parent, child1, child2;int itemIndex;// 分裂当前节点// 根据新数据项与当前节点中两个数据项的比较，分三种情况：if (thisNode.getItem(0).dData &gt; newItem.dData) { // 1.新数据项最小itemC = thisNode.removeItem();itemB = thisNode.removeItem();thisNode.insertItem(newItem);} else if (thisNode.getItem(1).dData &lt; newItem.dData) {// 2.新数据项最大itemC = newItem;itemB = thisNode.removeItem();} else {// 3.新数据项在中间itemC = thisNode.removeItem();itemB = newItem;}// 新节点Node1 newRight = new Node1();       // make new nodenewRight.insertItem(itemC);       // item C to newRight// 得到父节点if (thisNode != root) {parent = thisNode.getParent();} else {root = new Node1();                // make new rootparent = root;                    // root is our parentroot.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 &gt; itemIndex; j--)          // move parent's{                                      // connectionsNode1 temp = parent.disconnectChild(j); // one childparent.connectChild(j + 1, temp);        // to the right}// connect newRight to parentparent.connectChild(itemIndex + 1, newRight);}}  // end split()// =============================================================// 编程作业 10.5// thisNode 当前要分裂的节点// newItem 要插入的数据项// newNode 上次分裂(子节点分裂)得到的新节点，如果是第一次分裂(叶节点分裂)，则为nullpublic void split1(Node1 thisNode, DataItem newItem, Node1 newNode) {// assumes node is fullDataItem itemB, itemC; // itemB保存中间数据项,itemC保存最大数据项Node1 parent, child1, child2, newRight;int itemIndex;// 分裂当前节点// 根据新数据项与当前节点中两个数据项的比较，分三种情况：if (thisNode.getItem(0).dData &gt; 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 nodenewRight.insertItem(itemC);       // item C to newRightnewRight.connectChild(0, child1);newRight.connectChild(1, child2);} else if (thisNode.getItem(1).dData &lt; newItem.dData) { // 2.新数据项最大itemC = newItem;itemB = thisNode.removeItem();child2 = thisNode.disconnectChild(2);newRight = new Node1();       // make new nodenewRight.insertItem(itemC);       // item C to newRightnewRight.connectChild(0, child2);newRight.connectChild(1, newNode);} else { // 3.新数据项在中间itemC = thisNode.removeItem();itemB = newItem;child2 = thisNode.disconnectChild(2);newRight = new Node1();       // make new nodenewRight.insertItem(itemC);       // item C to newRightnewRight.connectChild(0, newNode);newRight.connectChild(1, child2);}// 得到父节点if (thisNode != root) { // 当前节点是非根节点parent = thisNode.getParent();} else {// 当前节点是根节点root = new Node1();                // make new rootparent = root;                    // root is our parentroot.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 valuepublic Node1 getNextChild(Node1 theNode, long theValue) {int j;// assumes node is not empty, not full, not a leafint numItems = theNode.getNumItems();for (j = 0; j &lt; numItems; j++)          // for each item in node{                               // are we less?if (theValue &lt; theNode.getItem(j).dData)return theNode.getChild(j);  // return left child}  // end for // we're greater, soreturn 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 nodeint numItems = thisNode.getNumItems();for (int j = 0; j &lt; numItems + 1; j++) {Node1 nextNode = thisNode.getChild(j);if (nextNode != null)recDisplayTree(nextNode, level + 1, j);elsereturn;}}  // 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.5theTree.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);elseSystem.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// //////////////////////////////////////////////////////////////

《Java数据结构跟算法》第二版 Robert

热点推荐