import java.io.*;
import java.util.*;
import javax.swing.JOptionPane;
////////////////////////////////////////////////////////////////
class Node
{
public char iData; // data item (key)
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print("} ");
}
} // end class Node
////////////////////////////////////////////////////////////////
class Tree
{
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------
public Node find(char key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
// If (current.leftChild != '+' && current.rightChild != '+')
// if ( current.leftChild != '+') if(current.rightChild != '+')
//
//
public void insert(char id)
{
Node newNode = new Node();
Node plusNode = new Node();
// make new node
newNode.iData = id;
plusNode.iData = '+'; // insert data
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
if(parent != root);
{parent.rightChild= plusNode;}
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
if(parent != root);
{parent.leftChild = plusNode;}
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(char key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null&& current.rightChild==null)
{
if(current == root)
root = null;
else if(isLeftChild)
parent.leftChild = null;
else
parent.rightChild = null;
}
// if no right child, replace with left subtree
//put your code here
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if (isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
//put your code here
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild=current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with in order successor
//put your code here
{
Node successor = getSuccessor(current);
// if connect parent of current to successor instead
if(current == root)
root = successor;
else if (isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
}
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendants
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
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();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
/* public void Play()
{
Scanner keyboard = new Scanner(System.in);
int cont = 1;
while (cont ==1)
{
Node newNode = new Node();
System.out.println("Please enter a char ");
char input = keyboard.next().charAt(0);
newNode.iData = input;
int response = JOptionPane.showConfirmDialog(null, "Do you want to enter another? ");
if (response == JOptionPane.YES_OPTION)
{
}
else if (response == JOptionPane.NO_OPTION)
{
cont = 0;
}
}
}*/
public void fixRoot()
{
Node current = root;
if(current.iData != '+')
{
insert(current.iData);
}
current.iData = '+';
}
public void fixTree()
// Look at root of the binary tree
// If the root is a char besides '+', insert it in the tree again
// use same logic in order to rewrite the whole tree with transverse
{ Node current = root;
if (current.leftChild.iData != '+' && current.rightChild.iData != '+')
{
if ( current.leftChild.iData != '+')
{
if(current.iData != '+')
{
insert(current.iData);
}
current.iData = '+';
}
if(current.rightChild.iData != '+')
{
if(current.iData != '+')
{
insert(current.iData);
}
current.iData = '+';
}
}
}
public void transverseFix()
{
fixTree(root);
}
public void fixTree(Node current)
//Transverse through the tree, node by node
//At each location, check if leftChild or rightChild does not = '+'
{
if (current == null) return;
fixTree(current.leftChild);
if(current.iData != '+')
{
insert(current.iData);
current.iData = '+';
}
if (current.rightChild != null)
//{
// System.out.println(current.rightChild.iData);
// displayTree();
// }
// fixTree(current.rightChild);
}
// -------------------------------------------------------------
} // end class Tree
////////////////////////////////////////////////////////////////
class TreeApp
{
public static void main(String[] args) throws IOException
{
char value;
Tree theTree = new Tree();
int cont = 1;
Scanner keyboard = new Scanner(System.in);
do
{
System.out.println("Please enter a char ");
char input = keyboard.next().charAt(0);
theTree.insert(input);
System.out.println("Enter more?");
String input2 = keyboard.next();
if (input2.equalsIgnoreCase("n"))
{
cont = 2;
}
}while(cont == 1);
theTree.displayTree();
System.out.println("");
theTree.fixRoot();
theTree.displayTree();
System.out.println("");
// theTree.transverseFix();
theTree.displayTree();
//Testing without question
// theTree.insert('a');
// theTree.insert('z');
// theTree.insert('c');
// theTree.fixRoot();
// theTree.transverseFix();
/*while(true)
{
System.out.print("Enter first letter of show, ");
System.out.print("insert, find, delete, or traverse: ");
int choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getChar();
theTree.insert(value);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getChar();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print("\n");
}
else
System.out.print("Could not find ");
System.out.print(value + '\n');
break;
case 'd':
System.out.print("Enter value to delete: ");
value = getChar();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print("Deleted " + value + '\n');
else
System.out.print("Could not delete ");
System.out.print(value + '\n');
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getChar();
theTree.traverse(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 TreeApp
////////////////////////////////////////////////////////////////
public class AlphabatizeLink {
}
私が行った変更は、insert（）で行われ、下部の関数は、play（）で始まります。私が取得しようとしている最終結果は、リーフとしての「+」ではない各文字、および文字である文字であるか「+」である文字であるかに関係なく、2つの子を持つ各親です。
したがって、最初の部分では、ユーザーが入力を入力し、それらが文字としてツリーに配置されます。次に、ルートの修正メソッドは、ツリーのさらに下にルートを再挿入し、ルートを「+」にします。ツリーの残りの部分についても同じ考えを持っていました。ツリーを横切って、印刷する代わりに修正しましたが、メモリ不足エラーが発生しました。メインの//offtheTree.Transverse（）を外し、実際のメソッドのコード行を外すと、エラーが表示されます。