public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
Finding a Node 377
while(current.iData != key) // while no match,
{
if(key <>
current = current.leftChild;
else
current = current.rightChild; // or go right?
if(current == null) // if no child,
return null; // didn’t find it
}
return current; // found it
}
-=====================
Inserting in a tree
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
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 = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
380 CHAPTER 8 Binary Trees
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
Quick sort
function quicksort(array) var list less, greater if length(array) ≤ 1 return array select and remove a pivot value pivot from array for each x in array if x <>then append x to less else if x > pivot then append x to greater return concatenate(quicksort(less), pivot, quicksort(greater))
Shell sort
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)
Quick sort
As you can see, there are three basic steps:
1. Partition the array or subarray into left (smaller keys) and right (larger keys)
groups.
Quicksort 333
2. Call ourselves to sort the left group.
3. Call ourselves again to sort the right group.
No comments:
Post a Comment