/ * The following is the source code of the binary sort tree implemented with C * /
#include
Typedef struct Treenode
{
Int key;
Struct Treenode * Left;
Struct Treenode * Right;
} TREENODE;
Class Bisosttree
{
PUBLIC:
BisostTree (Void);
Void desplaytree (void); // Shows this tree
Void InsertTree (int key); // Insert a value in the tree
deletetree (int key); // Delete a value in the tree
Treenode * searchtree (int key); // Find a value in the tree
~ Bisorttree ();
Private:
Treenode * buildtree (Treenode * head, int number); // Create a tree
Treenode * Search (Treenode * head, int key); // Find
Treenode * BisostTree :: searchParent (Treenode * p); / / Find a pointer to the father's node of the P
Treenode * Bisosttree :: SearchMinright (Treenode * head); / / Find the smallest node in the right tree
Void showtree (TREENODE * HEAD); // Display
Void DestroyTree (Treenode * HEAD); // Delete
Treenode * head;
}
/ ************** The following is to create a binary sort tree ************** /
Bisorttree :: bisorttree ()
{
Cout << "Create a two-fork sort tree, please enter all the numbers you want to build (with -1 as the end sign!): << Endl;
HEAD = NULL;
Int number;
CIN >> NUMBER;
While (Number! = - 1)
{
Head = buildtree (head, number);
CIN >> NUMBER;
}
}
Treenode * Bisorttree :: Buildtree (Treenode * Head, Int Number)
{
Treenode * P;
P = new treenode;
P-> key = Number;
P-> LEFT = P-> Right = NULL;
IF (head == null)
{
Return P;
}
Else
{
IF (P-> Key
Head-> left = buildtree (head-> left, number);
Else
Head-> right = buildtree (head-> right, number);
Return head;
}
}
/ ***************** The following is inserting a number in a two-fork sequence tree ******************* *************** /
Void BisostTree :: InsertTree (int key)
{
Head = buildtree (head, key);
}
/ ***************** The following is in a binary sort tree to find a number of ***************************** ****** /
Treenode * Bisosttree :: SearchTree (int key)
{
Return Search (Head, Key);
}
Treenode * Bisorttree :: Search (Treenode * Head, Int Key)
{
IF (head == null) Return NULL;
IF (head-> key == key)
Return head;
Else
{
IF (Key
Return Search (Head-> Left, Key);
Else
Return Search (Head-> Right, Key);
}
}
/ ************ The following is a given value in a binary sequence tree ********************** ********** /
Bisosttree :: deletetree (int key)
{
Treenode * P;
p = null;
P = Search (Head, Key);
IF (p == NULL)
{
Cout << "DON't Find The Key";
}
IF (p == HEAD)
{
HEAD = NULL;
}
Else
{
Treenode * Parent;
Parent = SearchParent (Head, P);
IF (P-> LEFT == Null && P-> Right == NULL) // Leaf node
{
IF (parent-> left == p)
{
Parent-> left = null;
}
Else
{
Parent-> Right = NULL;
}
}
ELSE // non-leaf node
{
IF (P-> Right == Null) // This node does not have the right child
{
IF (parent-> left == p)
{
Parent-> left = p-> left;
}
Else
{
Parent-> Right = P-> Left;
}
}
Else // This point has left and right children
{
Treenode * Rightminson, * secondparent; // SecondParent; father in the right node in the right child
Rightminson = SearchminRight (P-> Right);
SecondParent = SearchParent (P-> Right, Rightminson);
SecondParent-> Left = Rightminson-> Right;
If (p-> right == rightminson) // The father of the smallest node in the right tree is P
{
P-> Right = Rightmin-> Right;
}
P-> Key = Rightmin-> key;
}
}
}
}
Treenode * BisostTree :: searchParent (Treenode * p)
{
IF (head-> left == p || Head-> right == p || Head == P || Head == null)
Return head;
Else
{
IF (P-> Key
Return SearchParent (Head-> Left, P);
Else
Return SearchParent (Head-> Right, P);
}
}
Treenode * BisostTree :: SearchminRight (Treenode * Head) // Locate the smallest node in the right tree
{
IF (head-> left == null || head == null)
{
Return head;
}
Else
{
Return SearchminRight (Head-> Left);
}
/ ***************** The following is to show a binary sort tree *********************** **************** /
Void BisostTree :: DesplayTree (Void)
{
Showtree (Head);
Cout << Endl;
}
Void Bisosttree :: Showtree (Treenode * Head)
{
IF (Head! = null)
{
Showtree (Head-> Left);
Cout << Head-> key << '';
Showtree (Head-> Right);
}
}
/ ***************** The following is to delete a whole binary sort tree ********************** ************* /
Bisosttree :: ~ bisorttree ()
{
Cout << "has eliminated a tree !!!!" << Endl;
DESTROYTREE (HEAD);
}
Void BisostTree :: DestroyTree (Treenode * Head)
{
IF (Head! = null)
{
DestroyTree (head-> left);
DESTROYTREE (Head-> Right);
DELETE HEAD;
}
}
/ ******************** /
Void print ()
{
Cout << Endl << Endl << "The following is the basic operation of the binary sequence tree:" << Endl
<< "1. Show tree" << ENDL
<< "2. Insert a node" << Endl
<< "3. Looking for a node" << ENDL
<< "4. Delete a node" << ENDL;
}
void main ()
{
Bisostree Tree;
Int number;
INT chofhenumber;
Char flag;
While (1)
{
PRINT ();
Cout << "Please select the action you want to do (1 ~ 4) << ENDL;
CIN >> CHOCENUMBER;
Switch (Choicenumber)
{
Case 1:
Tree.DesplayTree (); Break;
Case 2:
Cout << "Please insert a number:" << Endl;
CIN >> NUMBER;
Tree.Inserttree (Number);
Tree.desplaytree ();
Break;
Case 3:
Cout << "Please insert you to find:" << Endl;
CIN >> NUMBER;
Tree.searchtree (Number) == NULL)
{
Cout << "No" << Endl;
}
Else
{
Cout << "Discovery" << Endl;
}
Break;
Case 4:
Cout << "Please enter the number you want to delete:" << Endl;
CIN >> NUMBER;
Tree.deleTree (Number);
Tree.desplaytree ();
Break;
DEFAULT: BREAK;
}
Cout << "Do you want to continue (Y / N)?" << endl; cin >> Flag;
IF (Flag == 'N' || flag == 'n')
Break;
}
}
