<--------------- Shin sort
starts from here ----------------->
Program reads key strings, stores them
into Shin tree, and
performs preorder traversal to print
every node value out.
Preorder after key #1,
"KIM" is inserted.
K I M
-----------------------------------------------------------------
Preorder after key #2,
"KING" is inserted.
K I M N G
-----------------------------------------------------------------
Preorder after key #3,
"LION" is inserted.
K I M N G L I O N
-----------------------------------------------------------------
Preorder after key #4,
"KIND" is inserted.
K I M N D G L I O N
-----------------------------------------------------------------
Preorder after key #5,
"JADE" is inserted.
J A D E K I M N D G L I O N
-----------------------------------------------------------------
Preorder after key #6,
"KIN" is inserted.
J A D E K I M N:1 D G L I O N
-----------------------------------------------------------------
Preorder after key #7, "KENT" is
inserted.
J A D E K E N T I M N:1 D G L
I O N
-----------------------------------------------------------------
Preorder after key #8,
"KILE" is inserted.
J A D E K E N T I L E M N:1 D
G L I O N
-----------------------------------------------------------------
Preorder after key #9,
"QUEEN" is inserted.
J A D E K E N T I L E M N:1 D
G L I O N Q U E E N
-----------------------------------------------------------------
----------------<Input
List for the 9 Keys>----------------
KIM; KING; LION; KIND; JADE; KIN; KENT;
KILE; QUEEN;
________________________________________________________________
Preorder traversal after 9
keys are inserted into the tree.
J A D E K E N T I L E M N:1 D
G L I O N Q U E E N
________________________________________________________________
Inorder traversal after 9
keys are inserted into the tree.
E D A J T N E E L M D G N:1 I
K N O I L N E E U Q
________________________________________________________________
Postorder traversal after 9
keys are inserted into the tree.
E D A T N E G D N:1 M L I E N
O I N E E U Q L K J
________________________________________________________________
<----------- Printing Shin
tree starts from here ----------->
Traversing the tree in preorder, it will
print out keys and
show how stack is changed. It will push a node character
into the stack and pop one from the
stack. The following
shows how a key character is inserted
into and deleted from
the stack. A key will be printed out whenever
collected
stack items make a full key.
'J' pushed --> 'A' pushed
--> 'D' pushed --> 'E' pushed -->
The stored key,
"JADE", is printed out here.
'E' popped --> 'D' popped
--> 'A' popped --> 'J' popped -->
'K' pushed --> 'E' pushed
--> 'N' pushed --> 'T' pushed -->
The stored key, "KENT", is
printed out here.
'T' popped --> 'N' popped
--> 'E' popped --> 'I' pushed -->
'L' pushed --> 'E' pushed
-->
The stored key,
"KILE", is printed out here.
'E' popped --> 'L' popped
--> 'M' pushed -->
The stored key,
"KIM", is printed out here.
'M' popped --> 'N' pushed
-->
The stored key,
"KIN", is printed out here.
'D' pushed -->
The stored key,
"KIND", is printed out here.
'D' popped --> 'G' pushed
-->
The stored key, "KING",
is printed out here.
'G' popped --> 'N' popped
--> 'I' popped --> 'K' popped -->
'L' pushed --> 'I' pushed
--> 'O' pushed --> 'N' pushed -->
The stored key,
"LION", is printed out here.
'N' popped --> 'O' popped
--> 'I' popped --> 'L' popped -->
'Q' pushed --> 'U' pushed
--> 'E' pushed --> 'E' pushed -->
'N' pushed -->
The stored key,
"QUEEN", is printed out here.
'N' popped --> 'E' popped
--> 'E' popped --> 'U' popped -->
'Q' popped -->
----------------<Input
List for the 9 Keys>----------------
KIM; KING; LION; KIND; JADE; KIN; KENT;
KILE; QUEEN;
----------------<Sorted
List for the 9 Keys>----------------
JADE; KENT; KILE; KIM; KIN; KIND; KING;
LION; QUEEN;
<--------------- Shin
search starts from here ---------------->
The following output will show what keys
are looked for and
how characters in a key are searched one
after another in the
tree. The search result, found or not found,
will be printed
after all.
1. Search the Key: LIONS Size: 5
Character of the Node:
L Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
O Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 0
The key, "LIONS",
is not found.
2. Search the Key: KIND Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 1
Character of the Node:
D Counter Value of the
Node: 0
The key,
"KIND", is found in the Shin tree.
3. Search the Key: K Size: 1
Character of the Node:
K Counter Value of the
Node: 0
The key,
"K", is not found.
4. Search the Key: KINS Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 1
The key,
"KINS", is not found.
5. Search the Key: KIM Size: 3
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
M Counter Value of the
Node: 0
The key,
"KIM", is found in the Shin tree.
6. Search the Key: KANG Size: 4
Character of the Node:
K Counter Value of the
Node: 0
The key,
"KANG", is not found.
7. Search the Key: JA Size: 2
Character of the Node:
J Counter Value of the
Node: 0
Character of the Node:
A Counter Value of the
Node: 0
The key,
"JA", is not found.
8. Search the Key: KIN Size: 3
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 1
The key,
"KIN", is found in the Shin tree.
9. Search the Key: KENNY Size: 5
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
E Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 0
The key,
"KENNY", is not found.
<--------- Delete key in
Shin Tree starts from here --------->
The following output will show what keys
are to be deleted
from the Shin tree. After a deletion, a
preorder traversal
will be called to show that the key is
deleted and the tree
remains all right without the deleted
key.
1. Search the Key: LION Size: 4
Character of the Node:
L Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
O Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 0
The key,
"LION", is found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J 2:K 3:L* 4:I* 5:O* 6:N*
J A D E K E N
T I L E M N:1 D G L I
2. Search the Key: QUEEN Size: 5
The key,
"QUEEN", is not found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J 2:K 3:L
J A D E K E N T I L E M N:1 D
G L I
3. Search the Key: KIM Size: 3
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
M Counter Value of the
Node: 0
The key,
"KIM", is found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J 2:K* 3:E 4:I* 5:L 6:M*
J A
D E K E N T I L N:1 D G M N:1
D G L I
4. Search the Key: KENT Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
E Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 0
Character of the Node:
T Counter Value of the
Node: 0
The key, "KENT", is
found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J 2:K* 3:E* 4:N* 5:T*
J A D E K E I L N:1 D G M
N:1 D G I L N:1 D G M N:1 D G
5. Search the Key: KILE Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
L Counter Value of the
Node: 0
The key,
"KILE", is not found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J 2:K* 3:E 4:I* 5:L* 6:N
J A D E K E I L N:1 D G M N:1
D
G I L N:1 D G M N:1 D G
6. Search the Key: KIN Size: 3
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 1
The key,
"KIN", is found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J 2:K* 3:E 4:I* 5:L 6:M
7:N*
J A D E K E I L N:1 D G M N:1
D G I L N:1
D G M N:1 D G
7. Search the Key: JADE Size: 4
Character of the Node:
J Counter Value of the
Node: 0
Character of the Node:
A Counter Value of the
Node: 0
Character of the Node:
D Counter Value of the
Node: 0
Character of the Node:
E Counter Value of the
Node: 0
The key,
"JADE", is found for deletion in the Shin tree.
Print node values to a key to
be deleted:
1:J* 2:A* 3:D* 4:E*
J K E I L N:1 D G M N:1 D G I
L N:1 D G M N:1
D G
________________________________________________________________
Preorder traversal:
J K E I L N:1 D G M N:1 D G I
L N:1 D G M N:1 D G
________________________________________________________________
Inorder traversal:
J E D G N:1 L M D G N:1 I K D
G N:1 L M D G N:1 I
________________________________________________________________
Postorder traversal:
G D N:1 G D N:1 M L I E G D
N:1 G D N:1 M L I K J
________________________________________________________________
