15. Дървета

  Двоични дървета.
*** Определение и свойства на дърво.
- Ацикличен насочен граф, в който всички върхове без 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, node* &);
   void pr(const node *) 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 &);
   ~tree() { DelTree(root); }
   void print() const { pr(root); }
   node *search() const;
   int ReadWord(istream &);
private:
   node *root;
   enum { buflen = 50 };
   char buf[buflen];
   void AddNode(node* &);
   void DelTree(node* &);
   void pr(const node *)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 *);
void AddList(Huf *);
Huf *FindDels();
void CreateTree();
void rlrootTree(Huf *);

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 = 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 = new List;
 l->tree = h;
 l->next = head;
 head = l;
}

Huf *FindDels()
{
 List *l = head, *sm = head;
 Huf *h;
 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;
 }
}