Def: A finite set constituted by one or more nodes
1. The tree has a specific node which is called Root
2. The other nodes is n (n>=0) mutually exclusive collection of T1、T2.......Tn.
These collections are a tree. It is called the subtree of the root.
The tree is shown in figure below:
fig.1
fig.2
This waste too much space to storage the link,even we didn't use them.Binary Tree
def: A finite set constructed by nodes. Binary Tree can be empty or it is constructed by the root , the left subtree , right subtree. The left subtree and right subtree are also binary tree .
What different between tree and binary tree?
1. Tree can be empty,but binary tree can not.
2. Tree degree is > = zero but binary tree degree is between zero to two.
3. Subtree of the tree have no order . Subtree of the binary tree have order .
Special Binary Tree
Skewed Binary Tree:
1. left skewed binary tree
fig.3
Tree node only have left child.2. right skewed binary tree
fig.4
Tree node only have right child.
Full Binary Tree:
def: If a full binary tree has a depth called k. Then a full binary tree have ((2^k)-1) number of node
fig.5
Complete Binary Tree:
def: If a complete binary tree tree has a depth called k.
1. number of node < = (2^k)-1
property: 1. The number of left child is 2 * i , if (2 * i) > node , then it have no left child.
2. The number of right child is (2 * i)+1 , if (2 * i) +1> node , then it have no right child.
3. The number of parent node is floor( i / 2 ) , if floor( i / 2 ) < 1 , then it have no
parent node.
fig.6
Binary tree data structure
Using linked list:
fig.7
if Binary Tree have n number of node. The link space is 2n.(totle)
And we really use n-1 space by link, so we waste 2n-(n-1)=n+1 (link space)
Advantage:
It is convenient for delete node and insert node.
Drawback:
It waste a half of space.
Every node can not find parent node.
Using array:
Change a binary tree to a full binary tree , and the node number will map to array.
Giving the depth of tree is k, the array size will be (2^k)-1.
For the case shown in fig. 7 , the mapping of the array:
fig.8
Advantage:It is easy to find parent node and child.
It is no necessary to store link.
Drawback:
It is not easy to delete and insert a node.
If the tree is a Skewed Binary Tree , then that is waste too much array space.
Binary Tree Traversal
def: Visit all node in a tree.
fig.9
1. Preorder : DLR
2. Inorder : LDR
3. Postorder : LRD
For the case shown in figure 10, we will have a binary tree is shown in below:
fig.10
The preorder is "ABDC"
The inorder is "DBAC"
The postorder is "DBCA"
Binary Search Tree
def: If binary search is not empty !
1.The key value of left subtree is less than key value of root.
2.The key value of right subtree is greater than key value of root.
3.Right subtree and left subtree are also binary search tree.
So a binary search is like this :
fig.11
Sort of Binary Search Tree
Using inorder if you want sort a binary search tree.
For this case , the result of inorder is " 2 5 6 7 9 14 " .
Search of Binary Search Tree
It is a binary search tree want search a key value called k.
1. If key value of root is equal k , then we found it!
2. If key value of root is less than k , then we go to the left subtree of root.
3. If key value of root is greater than k , then we go to the right subtree of root.
The average number of comparisons for a binary search tree is big-o ( n )
The optimal number of comparisons for a binary search tree is big-o ( log n )
Delete of Binary Search Tree
1.If the node that we want delete is a leaf , then just delete it and let the link of parent be null.
2.If the node that we want delete is not a leaf but it only have one child.
Then link the parent node and child node together.
3.If the node that we want delete have two child , then find the greatest key value of left subtree
or find the least key value of right subtree and then replace it.
Non-Recursive Binary Search tree implement in C++
///BST.h///
#ifndef BST_H
#define BST_H
#include <iostream>
class BST{
private:
int Node_Number;
int Top;
int PopCount;
int DeleteData;
struct TreeNode *STACK;
struct TreeNode *root;
struct TreeNode *ptr;
struct TreeNode *current;
struct TreeNode *pre;
struct TreeNode *clear;
public:
BST();
~BST();
void Add();
void Sort();
void Delete();
TreeNode* FindFather(int num);
TreeNode* SearchNumber(int num);
void Search();
void inorder(TreeNode *D);
void push(TreeNode *temp);
void pop();
void ClearMemory(TreeNode *D);
};
#endif
///BST.cpp///
#include "BST.h"
using namespace std;
struct TreeNode{
int IntData;
struct TreeNode *Llink;
struct TreeNode *Rlink;
};
BST::BST(){
root=NULL;
Node_Number=0;
Top=-1;
PopCount=0;
}
BST::~BST(){
current=root;
ClearMemory(current);
cout<<"The memory is released"<<endl;
system("Pause");
}
void BST::Add(){
Node_Number++;
ptr=new TreeNode;
ptr->Llink=NULL;
ptr->Rlink=NULL;
cout<<"Please Enter the Integer"<<endl;
cin>>ptr->IntData;
if(root==NULL){ //For now the tree is still empty so the new node will be root!
root=ptr;
}else{ //The tree is not empty!
if(SearchNumber(ptr->IntData)!=NULL){ //Binary Search tree can not have the same data!
cout<<"Error! You have the same Integer!!"<<endl;
return; //Jump to the menu!
}
current=root;
while(current!=NULL){
if(ptr->IntData<current->IntData){ //Compare two integer. If node of ptr is less than node of currnet then put
//the node of ptr to left subtree.
if(current->Llink==NULL){ //Consider the node is a leaf!
current->Llink=ptr;
ptr->Llink=NULL;
ptr->Rlink=NULL;
current=NULL;
}else{
current=current->Llink; //Move to the next left child
}
}else{ //If node of ptr is bigger than node of currnet then put the node of ptr to right subtree.
if(current->Rlink==NULL){ //Consider the node is a leaf!
current->Rlink=ptr;
ptr->Llink=NULL;
ptr->Rlink=NULL;
current=NULL;
}else{
current=current->Rlink; //Move to the next right child
}
}
}
}
}
void BST::Delete(){
if(root==NULL){
cout<<"The tree is empty!"<<endl;
}else{
Sort(); //show integer
}
cout<<"Which one do you want delete? :"<<endl;
cin>>DeleteData;
if(SearchNumber(DeleteData)==NULL){
cout<<"Error!! Can not find this Integer!!"<<endl;
return;
}else{
current=SearchNumber(DeleteData); //Find the integer
}
TreeNode *temp;
if(current==root&&Node_Number==1){ //Consider the delete integer is root node and it is only one node in tree!
clear=current;
root=NULL;
delete clear;
Node_Number--;
return;
}else if(current==root){ //Consider the delete integer is root node and it is not only one node in tree!
if(root->Llink==NULL){ //Consider it is no left subtree!
clear=root;
root=root->Rlink;
delete clear;
Node_Number--;
return;
}else if(root->Rlink==NULL){ //Consider it is no right subtree!
clear=root;
root=root->Llink;
delete clear;
Node_Number--;
return;
}else{ //If the root have left subtree and right subtree!
temp=current;
temp=temp->Llink; //Move to the left child! Beacuse I want to choose the biggest node of left subtree to replace the node of root!
if(temp->Rlink==NULL){ //In the left subtree. The biggest node always at right node! Now Consider if the left subtree have no right node!
temp->Rlink=root->Rlink;
clear=root;
root=temp;
delete clear;
Node_Number--;
return;
}else{
while(temp->Rlink!=NULL){ //Last right node is the bigest node in left subtree of root!
temp=temp->Rlink; //Keep move to the right node!
}
pre=FindFather(temp->IntData); //Find this node's parent
if(temp->Llink==NULL){ //Consider two case. if temp node have no leftchild then his parent doesn't need to link any node!
pre->Rlink=NULL;
}else{
pre->Rlink=temp->Llink; //The other case is if temp node have leftchild then his parent need to link leftchild!
}
temp->Llink=root->Llink; //Replace the delete node!
temp->Rlink=root->Rlink;
clear=root;
root=temp;
delete clear; //Delete
Node_Number--;
return;
}
}
}
if(current->Llink==NULL&¤t->Rlink==NULL){ //if the node we want to delete is a leaf
pre=FindFather(current->IntData); //Find parent of delete node
if(pre->IntData>current->IntData){ //After remove delete node. The parent node will link to NULL.
pre->Llink=NULL;
clear=current;
delete clear;
Node_Number--;
return;
}else{
pre->Rlink=NULL;
clear=current;
delete clear;
Node_Number--;
return;
}
}
pre=FindFather(DeleteData);
if(current->Llink==NULL){
if(((current->Rlink)->Llink==NULL)&&((current->Rlink)->Rlink==NULL)){ //if the node we want to delete is only have one child node
clear=current;
if(pre->IntData>current->IntData){ //parent node will link to the child of delete node
current=current->Rlink;
pre->Llink=current;
delete clear;
Node_Number--;
return;
}else{ //parent node will link to the child of delete node
current=current->Rlink;
pre->Rlink=current;
delete clear;
Node_Number--;
return;
}
}
}else if(current->Rlink==NULL){
if((current->Llink)->Llink==NULL&&(current->Llink)->Rlink==NULL){ //if the node we want to delete is only have one child node
clear=current;
if(pre->IntData>current->IntData){ //parent node will link to the child of delete node
current=current->Llink;
pre->Llink=current;
delete clear;
Node_Number--;
return;
}else{ //parent node will link to the child of delete node
current=current->Llink;
pre->Rlink=current;
delete clear;
Node_Number--;
return;
}
}
}
temp=current;
temp=temp->Llink;
if(temp->Rlink==NULL){
pre=FindFather(current->IntData);
temp->Rlink=current->Rlink;
if(temp->IntData<pre->IntData){
pre->Llink=temp;
}else{
pre->Rlink=temp;
}
clear=current;
delete clear;
Node_Number--;
}else{
while(temp->Rlink!=NULL){
temp=temp->Rlink;
}
pre=FindFather(temp->IntData);
if(temp->Llink==NULL){
pre->Rlink=NULL;
}else{
pre->Rlink=temp->Llink;
}
temp->Llink=current->Llink;
temp->Rlink=current->Rlink;
pre=FindFather(current->IntData);
if(temp->IntData<pre->IntData){
pre->Llink=temp;
}else{
pre->Rlink=temp;
}
clear=current;
delete clear;
Node_Number--;
}
}
void BST::Sort(){
if(root==NULL){
cout<<"The tree is empty!"<<endl;
return;
}
STACK=new TreeNode[Node_Number]; //Create a structure array as a stack!
PopCount=0;
current=root;
while(1){ // Non-Recursive of inorder .The order is follow this rule. parent,leftchild,rightchild
if(current!=NULL){
push(current);
current=current->Llink;
}else{
current=STACK[Top].Rlink;
pop();
PopCount++;
}
if(PopCount==Node_Number){
cout<<endl;
break;
}
}
delete []STACK;
}
void BST::Search(){
int num=0;
cout<<"Please Enter the Integer"<<endl;
cin>>num;
if(SearchNumber(num)!=NULL){
cout<<"That data does exist in tree!"<<endl;
}else{
cout<<"That data doesn't exist in tree!"<<endl;
}
}
TreeNode* BST::SearchNumber(int num){ //Search a number
TreeNode *temp;
temp=root;
while(temp!=NULL){
if(temp->IntData==num){
return temp;
}else if(temp->IntData<num){
temp=temp->Rlink;
}else{
temp=temp->Llink;
}
}
return temp;
}
TreeNode* BST::FindFather(int num){ //Search parent
TreeNode *Find;
Find=root;
while(Find!=NULL){
if(Find->Llink!=NULL){
if(Find->Llink->IntData==num){
return Find;
}
}
if(Find->Rlink!=NULL){
if(Find->Rlink->IntData==num){
return Find;
}
}
if(num<Find->IntData){
Find=Find->Llink;
}else{
Find=Find->Rlink;
}
}
}
void BST::push(TreeNode *temp){
if(Top==Node_Number-1){
//cout<<"堆疊已滿"<<endl;
}else{
Top++;
STACK[Top]=*temp;
}
}
void BST::pop(){
cout<<STACK[Top].IntData<<"\t";
Top--;
}
void BST::inorder(TreeNode *D){ //Recursive of inorder
if(D!=NULL){
inorder(D->Llink);
cout<<D->IntData<<endl;
inorder(D->Rlink);
}
}
void BST::ClearMemory(TreeNode *D){
if(D!=NULL){
ClearMemory(D->Llink);
ClearMemory(D->Rlink);
delete D;
}
}
///main///
#include <iostream>
#include "BST.h"
using namespace std;
int main()
{
char option;
BST bst;
while(1){
cout<<"======================"<<endl;
cout<<"1.Add Integer"<<endl;
cout<<"2.Delete Integer"<<endl;
cout<<"3.Search Integer"<<endl;
cout<<"4.Show the result of sort"<<endl;
cout<<"5.Quit"<<endl;
while(cin.get(option)&&option=='\n');
switch(option){
case '1':bst.Add();
break;
case '2':bst.Delete();
break;
case '3':bst.Search();
break;
case '4':bst.Sort();
break;
case '5':cout<<"Quit Now"<<endl;
return 0;
}
}
}
By Victor ; )
