struct Node { char data; Node *next;};
Node *top;

bool insert(Node *pt, char c)  // insert after *pt
{
 if (pt == NULL) return false;
 Node *node=new Node;
 if (node == NULL) return false;
 node -> data = c;
 node -> next = pt -> next;
 pt -> next = node;
 return true;
}

bool erase(Node *pt)     // erase pt->next
{
 if ((pt == NULL) || (pt->next==NULL)) return false;
 Node *node=pt->next;
 pt->next=node->next;
 delete node;
 return true;
}

void print()
{
 Node *pt=top;
 while (pt!=NULL)
 {
  cout << pt->data;
  pt=pt->next;
 }
 cout << "\n";
}

void create()
{
 char ch;
 Node *pt=NULL, *ptold=NULL;
 top=NULL;
 while (cin >> ch)
 {
  pt=new Node;
//  if (pt==NULL) break;
  pt->data = ch;
  pt->next = NULL;
  if (top==NULL) top = pt;
  else ptold->next = pt;
  ptold = pt;
 }
}

int main()
{
 create();        print();
 Node *pt=top; pt=pt->next;
 insert(pt, 'A'); print();
 erase(pt);       print();
 return 0;
}

  Опашка
#include <iostream>
using namespace std;

struct Node { char data; Node *next;};
Node *top, *end;

bool append(char c) // insert after last
{
 if (end==NULL) return false;
 Node *node=new Node;
 if (node == NULL) return false;
 node -> data = c;
 node -> next = NULL;
 end -> next = node;
 end = node;
 return true;
}

bool erase()       // erase first
{
 if (top==NULL) return false;
 Node *node=top;
 top=top->next;
 delete node;
 return true;
}

void print()
{
 Node *pt=top;
 while (pt!=NULL)
 {
  cout << pt->data;
  pt=pt->next;
 }
 cout << "\n";
}

void create()
{
 char ch;
 Node *pt=NULL, *ptold=NULL;
 top=NULL;
 while (cin >> ch)
 {
  pt=new Node;
//  if (pt==NULL) break;
  pt->data = ch;
  pt->next = NULL;
  if (top==NULL) top = pt;
  else ptold->next = pt;
  ptold = pt;
 }
 end = pt;
}

int main()
{
 create();    print();
 append('A'); print();
 erase();     print();
 return 0;
}

  Двоични дървета
*** Определение и свойства на дърво.
- Ацикличен насочен граф, в който всички върхове без 1 имат по 1 предшественик, а 1 връх (корен) няма предшественици.
- Единствен път до корена, ниво - брой на върховете по пътя до корена
- Ниво на върха - брой на върховете в пътя до корена
- Корен - ниво 0
- Листа - върхове без наследници
- Поддърво определено от връх - върхът и всичките му наследници, техните наследници и т.н.
- Рекурсивна същност на дърветата като структури от данни

*** Двоично дърво:
Брой на наследниците на върховете - 0, 1 или 2;
Ляв и десен наследник.
-- Рекурсивно определение на двоично дърво
Крайно множество от елементи (възли), което е или празно, или се състои от корен (възел), свързан с две непресичащи се двоични дървета (поддървета) - ляво и дясно поддърво.
-- Реализация с масив
-- Реализация с указатели
Дърво за двоично търсене:

#include <iostream>
using namespace std;

struct node {int info; node *pLeft, *pRight;};

class tree {
public:
   tree();
   void print()const{pr(root);}
private:
   node *root;
   void AddNode(int x, node* &p);
   void pr(const node *p)const;
};
tree::tree()
{  root = NULL;
   int x;
   while (cin >> x, !cin.fail()) AddNode(x, root);
}
void tree::AddNode(int x, node* &p)
{  if (p == NULL)
   {  p = new node;
      p->info = x;
      p->pLeft = p->pRight = NULL;
   }
   else AddNode(x, x < p->info ? p->pLeft : p->pRight);
}
void tree::pr(const node *p)const
{  if (p)
   {  pr(p->pLeft);
      cout << p->info << " ";
      pr(p->pRight);
   }
}
int main()
{  cout << "Enter some integers to be placed in a binary tree,\n"
        << "followed by /:\n";
   tree t;
   cout << "Tree contents (in ascending order):\n";
   t.print();
   cout << endl;
   return 0;
}
***  Обхождане на структура от данни двоично дърво
Обхождане на двоично дърво - линейно нареждане на възлите на дървото
* корен, ляв, десен (низходящо, preorder,  клд)
* ляв, корен, десен (смесено,     inorder,    лкд)
* ляв, десен, корен (възходящо, postorder, лдк)
Пример:
Аритметични изрази и двоични дървета
Листата са имена на променливи и константи, другите възли са аритметични операции
(a+b/c)*(d-e*f)
1) preorder (клд) - *+a/bc-d*ef
2) inorder  (лкд)  - a+b/c*d-e*f
3) postorder(лдк) - abc/+def*-*

Претърсване на дърво за двоично търсене:
/* bintree:
   This program builds and searches a binary search
   tree and prints its contents. The program produces
   a frequency distribution of words read from a textfile.
   We can also search the tree for a given word to inquire
   how often that word occurs.
*/
#include <fstream>
#include <iomanip>
#include <ctype.h>
#include <string>
using namespace std;

struct node {char *pWord; int count; node *pLeft, *pRight;};

class tree {
public:
   tree(ifstream &input);
   ~tree(){DelTree(root);}
   void print()const{pr(root);}
   node *search()const;
   int ReadWord(istream &input);
private:
   node *root;
   enum {buflen = 50};
   char buf[buflen];
   void AddNode(node* &p);
   void DelTree(node* &p);
   void pr(const node *root)const;
};

int tree::ReadWord(istream &input)
/* This function reads a word from the stream 'input'.
   It skips any leading nonalphabetic characters.
   Then the longest possible string of letters (no longer
   than buflen - 1) is read, converted to upper case and
   placed in 'buf'. Return value: success (1) or failure (0).
*/
{  char ch;
   int i;
   do
   {  input >> ch;
      if (input.fail()) return 0;
   }  while (!isalpha(ch));
   for (i=0; i<buflen-1; )
   {  buf[i++] = toupper(ch);
      input.get(ch);
      if (input.fail() || !isalpha(ch)) break;
   }
   buf[i] = '\0';
   return 1;
}
tree::tree(ifstream &input)
{  root = NULL;
   while (ReadWord(input)) AddNode(root);
}
void tree::DelTree(node* &p)
{  if (p)
   {  DelTree(p->pLeft); DelTree(p->pRight);
      delete[] p->pWord; delete p; p = NULL;
   }
}
void tree::AddNode(node* &p) // Add word in buf to tree
{  if (p == NULL)
   {  p = new node;
      p->pWord = new char[strlen(buf) + 1];
      strcpy(p->pWord, buf); p->count = 1;
      p->pLeft = p->pRight = NULL;
   }  else
   {  int code = strcmp(buf, p->pWord);
      if (code) AddNode(code < 0 ? p->pLeft : p->pRight);
      else p->count++;
   }
}
void tree::pr(const node *p)const
{  if (p)
   {  pr(p->pLeft);
      cout << setw(5) << p->count << " "
           << p->pWord << endl;
      pr(p->pRight);
   }
}
node *tree::search()const
{  node *p = root;
   for (;;)
   {  if (p == NULL) return NULL;
      int code = strcmp(buf, p->pWord);
      if (code == 0) return p;
      p = (code < 0 ? p->pLeft : p->pRight);
   }
}
int main()
{  ifstream input;
   node *ptr;
   const int NameLen=50;
   char FileName[NameLen];
   cout << "Input file: ";
   cin >> setw(NameLen) >> FileName;
   input.open(FileName, ios::in);
   if (input.fail())
   {  cout << "Cannot open input file.\n"; exit(1);   }

   tree t(input);
   cout << "Frequency distribution:\n";
   t.print();
   for (;;)
   {  cout << "\nEnter a word, or type Ctrl+Z (or Ctrl+D)"
              " to stop: ";
      if (t.ReadWord(cin) == 0) break;
// The word read by ReadWord has been placed in the buf
// class member. We now search the tree for this word:
      ptr = t.search();
      cout << "Number of occurrences: "
           << (ptr ? ptr->count : 0) << endl;
   }
   return 0;
}

Кодиране на Хъфман
*** Алгоритъм на Хъфман:
 1. Всички букви - листа на дървото с тегла броя на срещанията на буквата в текста
 2. Всички други възли на дървото имат тегла 0
 3. В началото разглеждаме всички листа като отделни дървета
 4. Намираме две дървета с най-малки претеглени дължини
 5. Построяваме ново дърво, като създаваме нов възел (корен) с наследници - двете поддървета
 6. Пресмятаме претеглената дължина на новото дърво (сума от претеглените дължини на двете поддървета)
 7. Отиваме на 4., ако имаме поне 2 дървета

*** Построяване на оптимално двоично дърво по алгоритъма на Хъфман и пример за следния текст:
програмиране и структури от данни

#include <iostream>
using namespace std;

struct Huf {
char id;
int wh;
Huf *left, *right; };

struct List { List *next; Huf *tree; };

List *head;

void CreateList();
void WriteList();
void DelList(List *l);
void AddList(Huf *h);
Huf *FindDels();
void CreateTree();
void rlrootTree(Huf *h);

void main()
{
 CreateList();
 WriteList();
 CreateTree();
 rlrootTree(head->tree);
}
void CreateList()
{
 const int n=13;
 char ch[n]={'Ї','°','®','Ј',' ','¬','Ё','­','±','І','і','Є','¤'};
 int   w[n]={ 1,  5,  2,  1,  3,  1,  4,  3,  1,  2,  2,  1,  1};
 List *l; Huf *h;
 head=0;
 for (int i=0; i<n; i++)
 {
  h=new Huf;
  h->id=ch[i]; h->wh=w[i];
  h->left=0; h->right=0;
  l=new List;
  l->tree=h;
  l->next=head; head=l;
 }
}
void WriteList()
{
 List *l;
 l=head;
 while  (l)
 {
  cout << (l->tree)->id << "  " << (l->tree)->wh << endl;
  l=l->next;
 }
}
void DelList(List *l)
{
 List *lp, *lc;
 if (l==head) {head=l->next; delete l;}
 else
 {
  lp=head; lc=lp->next;
  while (lc!=l)
  {
   lp=lc; lc=lc->next;
  }
  lp->next=lc->next; delete lc;
 }
}
void AddList(Huf *h)
{
 List *l;
 l=new List;
 l->tree=h;
 l->next=head;
 head=l;
}
Huf *FindDels()
{
 List *l, *sm;
 Huf *h;
 l=head; sm=l;
 while (l)
 {
  if ((l->tree)->wh < (sm->tree)->wh) sm=l;
  l=l->next;
 }
 h=sm->tree;
 DelList(sm);
 return h;
}
void CreateTree()
{
 Huf *h, *h1, *h2;
 while (head->next)
 {
  h1=FindDels();
  h2=FindDels();
  h=new Huf;
  h->id=' '; h->wh=(h1->wh)+(h2->wh);
  h->left=h1; h->right=h2;
  AddList(h);
 }
}
void rlrootTree(Huf *h)
{
 if (h)
 {
  rlrootTree(h->right);
  rlrootTree(h->left);
  cout << h->id << " : " << h->wh << endl;
 }
}