*** Двоично дърво:
Брой на наследниците на върховете - 0, 1 или 2;
Ляв и десен наследник.
-- Рекурсивно определение на двоично дърво
Крайно множество от елементи (възли), което е или празно, или се състои от корен (възел), свързан с две непресичащи се двоични дървета (поддървета) - ляво и дясно поддърво.
-- Реализация с масив
-- Реализация с указатели
Дърво за двоично търсене:
// tree: Introduction to binary trees
#include <iostream.h>

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.h>
#include <iomanip.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

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.h>
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 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;
 }
}