DANH SÁCH LIÊN KẾT ĐƠN

+ Cấu trúc:

Code:


struct Node
{
   int data;
   Node *next;
};

typedef struct Node* List;


+ Thêm 1 Node mới


* Khởi tạo:

Code:


List CreateNewNode(int data)
{
   List temp=new Node();
   if(temp==NULL)
   {
      cout<<"Khong du bo nho";
      exit(0);
   }
   temp->data=data;
   temp->next=NULL;
   return temp;
}


* Thêm vào đầu danh sách

Code:


void AddNewNodeAtFirst(List newnode, List  &pHead)
{
   if(pHead==NULL) //Neu danh sach rong thi gan pHead=newnode
      pHead=newnode;
   else
   {
      newnode->next=pHead;
      pHead=newnode;
   }
}


*Thêm vào cuối danh sách

Code:


void AddNewNodeAtLast(List newnode, List  &pHead)
{
   if(pHead==NULL) //Neu danh sach rong thi gan pHead=newnode
      pHead=newnode;
   else
   {
      List temp=pHead;
      while(temp->next!=NULL)  //Duyet het danh sach tim Node Cuoi Cung
         temp=temp->next;
      temp->next=newnode;
   }
}



* Thêm vào sau 1 node khác

Code:


void AddNewNodeAtAfter(List nodetimthay,List newnode,List pHead)
{
   while(pHead->next!=NULL)
      pHead=pHead->next;
   if(pHead->data==nodetimthay->data)  //Neu Node la node cuoi cung thi Add vao cuoi
      AddNewNodeAtLast(newnode,pHead);
   else
   {
      newnode->next=nodetimthay->next;
      nodetimthay->next=newnode;
   }
}


+ Xóa node

* Xóa 1 node đầu danh sách

Code:


void RemoveNodeAtFirst(List &pHead)
{
   if(pHead==NULL)
      cout<<"Danh Sach Rong";
   else
   {
      List temp=pHead;
      pHead=pHead->next;
      delete temp;
   }
}


* Xóa 1 node cuối danh sach

Code:


void RemoveNodeAtLast(List &pHead)
{
   if(pHead==NULL)
      cout<<"Danh Sach Rong";
   else
   {
      List temp=pHead;
      List Truoc;
      while(temp->next!=NULL)
      {
         Truoc=temp;
         temp=temp->next;
      }
      Truoc->next=NULL;  //Gan Phan Tu Truoc Cuoi Bang NULL
      delete temp; //Xoa Phan Tu Cuoi Di
   }
}


*Xóa 1 node bất ki

Code:


void RemoveNodeAny(List &pHead,int vitrixoa)
{
   List temp=pHead;
   List Truoc;
   while(temp!=NULL && temp->data!=vitrixoa)
   {
      Truoc=temp;
      temp=temp->next;
   }
   Truoc->next=Truoc->next->next;
   delete temp;
}


* Xóa toàn bộ danh sach

Code:


void RemoveAllList(List &pHead)
{
   if(pHead==NULL)
      cout<<"Danh sach rong";
   else
   {
      while(pHead!=NULL)
         RemoveNodeAtFirst(pHead);
      cout<<"Da Xoa Toan Bo Danh Sach";
   }
}


DANH SÁCH LIÊN KẾT ĐÔI

+ Cấu trúc

Code:


struct Node
{
   int data;
   Node* next;
   Node* pre;
};
typedef struct Node* list;


+ Thêm 1 node

* Tạo 1 node

Code:


list CreateNewNode(int data)
{
   list temp=new Node();
   if(temp==NULL)
   {
      cout<<"Khong du bo nho";
      exit(0);
   }
   temp->data=data;
   temp->next=NULL;
   temp->pre=NULL;
   return temp;
}


* thêm vào đầu danh sach

Code:


void AddNewNodeAtFirst(list newnode,list &pHead,list &pTail)
{
   if(pHead==NULL)
      pHead=pTail=newnode;
   else
   {
      newnode->next=pHead;
      pHead->pre=newnode;
      pHead=newnode;
   }
}



* Thêm vào cuối danh sach

Code:


void AddNewNodeAtLast(list newnode,list &pHead,list &pTail)
{
   if(pHead==NULL)
      pHead=pTail=newnode;
   else
   {
      pTail->next=newnode;
      newnode->pre=pTail;
      pTail=newnode;
   }
}


* Thêm vào sau 1 node khác

Code:


void AddNewNodeAfter(list &pHead,list &pTail,list newnode,list NodeTimThay)
{
   if(NodeTimThay==NULL)
   {
      cout<<"Khong tim thay, Ban co muon them node nay vao dau danh sach(Y/N)";
      char chon;
      chon=getch();
      if(chon=='Y' || chon=='y')
         AddNewNodeAtFirst(newnode,pHead,pTail);
   }
   else
   {
      if(NodeTimThay->next==NULL)
         AddNewNodeAtLast(newnode,pHead,pTail);
      else
      {
         newnode->next=NodeTimThay->next;
         NodeTimThay->next->pre=newnode;
         NodeTimThay->next=newnode;
         newnode->pre=NodeTimThay;
      }
   }
}


+ Xóa node

* Xóa đầu

Code:


void RemoveNodeAtFirst(list &pHead,list &pTail)
{
   if(pHead==NULL)
      cout<<"Danh Sach Rong";
   else
   {
      if(pHead==pTail)
      {
         delete pHead;
         delete pTail;
         pHead=pTail=NULL;
      }
      else
      {
         list temp=pHead;
         pHead=pHead->next;
         pHead->pre=NULL;
         delete temp;
      }
   }
}


* Xóa cuối

Code:


void RemoveNodeAtLast(list &pHead,list &pTail)
{
   if(pHead==NULL)
      cout<<"Danh Sach Rong";
   else
   {
      if(pHead==pTail)
      {
         delete pHead;
         delete pTail;
         pHead=pTail=NULL;
      }
      else
      {
         list temp=pTail;
         pTail=pTail->pre;
         pTail->next=NULL;
         delete temp;
      }
   }
}


* Xóa 1 node bất kì

Code:


void RemoveNodeAny(list &pTail,list &pHead,list NodeTimThay)
{
   if(NodeTimThay->data==pTail->data)
      RemoveNodeAtLast(pHead,pTail);
   else
   if(NodeTimThay->data==pHead->data)
      RemoveNodeAtFirst(pHead,pTail);
   else
   {
      list temp=NodeTimThay->pre;
      temp->next=NodeTimThay->next;
      delete NodeTimThay;
   }
}



CÂY NHỊ PHÂN TÌM KIẾM


+ Cấu trúc

Code:


struct Node
{
   int data;
   Node *Left;
   Node *Right;
};
// Gan Node* Bang Tree
typedef struct Node* Tree;


+ Thêm 1 node mới

Code:


Node* CreateNewNode(int data)
{
   Tree Temp=new Node();
   if(Temp==NULL)
      cout<<"Khong du bo nho";
   else
   {
      Temp->data=data;
      Temp->Left=NULL;
      Temp->Right=NULL;
      return Temp;
   }
}


Code:


void InsertNewNode(Tree &Root,Tree NewNode)
{
   if(Root==NULL)
      Root=NewNode;
   else
   {
      if(NewNode->data<Root->data)
         InsertNewNode(Root->Left,NewNode);
      else
         InsertNewNode(Root->Right,NewNode);
   }   
}


+ Hiện thị Cây

* Inorder

Code:


Tree Inorder(Tree Root)
{      
   if(Root==NULL)
      return 0;
   else
   {
      Inorder(Root->Left);
      cout<<Root->data<<"\t";
      Inorder(Root->Right);
   }
}


* Preorder

Code:


Tree Preorder(Tree Root)
{
   if(Root==NULL)
      return 0;
   else
   {
      cout<<Root->data<<"\t";
      Preorder(Root->Left);
      Preorder(Root->Right);
   }
}


* Postorder

Code:


Tree Postorder(Tree Root)
{
   if(Root==NULL)
      return 0;
   else
   {
      Postorder(Root->Left);
      Postorder(Root->Right);
      cout<<Root->data<<"\t";
   }
}



+ Tìm kiếm 1 node

Code:


Tree Search(Tree Root, int element)
{
   if(Root==NULL)
      return NULL;
   else
   {
      if(Root->data==element)
         return Root;
      else
      if(Root->data>element)
         return Search(Root->Left,element);
      else
         return Search(Root->Right,element);
   }   
}


+ Đếm số lượng node

Code:


int Count(Tree Root)
{
   if(Root==NULL)
      return 0;
   else
      return (1+Count(Root->Left)+Count(Root->Right));
}


+ Tổng node trong cây

Code:


int SumTree(Tree Root)
{
   if(Root==NULL)
      return 0;
   else
   {
      return (SumTree(Root->Left)+Root->data+SumTree(Root->Right));
   }
}


+ Đếm node chẵn

Code:


void CountNodeEven(Tree Root,int &count)
{
   if(Root!=NULL)
   {
      CountNodeEven(Root->Left,count);
      if((Root->data)%2==0)
         count++;
      CountNodeEven(Root->Right,count);
   }
}


+ Đếm node lẻ

Code:


void CountNodeOdd(Tree Root,int &count)
{
   if(Root!=NULL)
   {
      CountNodeOdd(Root->Left,count);
      if((Root->data)%2!=0)
         count++;
      CountNodeOdd(Root->Right,count);
   }
}


+ Chiều cao của cây

Code:


int HeightTree(Node *Root)
{
   if(Root==NULL)
   return 0;
   int HeightLeft=HeightTree(Root->Left);
   int HeightRight= HeightTree(Root->Right);
   return (HeightLeft>=HeightRight?HeightLeft:HeightRight)+1;
}


+ Đếm số lá trong cây

Code:


void CountLeaves(Tree Root,int &count)
{
   if(Root!=NULL)
   {
      if(Root->Left==NULL && Root->Right==NULL)   
         count++;
      CountLeaves(Root->Left,count);
      CountLeaves(Root->Right,count);   
   }
}