Способы обхода дерева.В деревьях обход вершин возможен только с использованием рекурсии, поэтому и их логическая нумерация производится согласно последовательности их рекурсивного обхода. Рекурсивная функция в этом случае получает ссылку или указатель на счетчик вершин, который она увеличивает на 1 при обходе текущей вершины. В зависимости от того, кто нумеруется вперед предок или потомки, и в зависимости от направления просмотра потомков имеют место различные способы обхода и нумерации.
//---- Обход дерева с нумерацией вершин сверху вниз, слева направо (прямой обход)void ScanNum (tree *q, int &n ) {if (q==NULL) return;printf("n=%d val=%d\n",n++,q->val);for (int i=0; i< 4; i++) ScanNum(q->p[i],n);} Обход с нумерацией в обычном дереве используется для извлечения вершины по логическому номеру. При достижении вершины с заданным номером обход прекращается (аналогично алгоритму поиска первого подходящего). //---- Извлечение по логическому номеру с полным обходом дереваint GetNum (tree *q, int &n, int num ) {if (q==NULL) return -1;if ( n++ ==num) return q->val; // Номер текущей совпал с требуемым for (int i=0; i< 4; i++) { // Обход потомков, int vv=GetNum (q->p[i],n,num ); // пока не превышен номер if (n > num) return vv; }return -1; }Если каждая вершина дерева будет содержать дополнительный параметр количество вершин в связанном с ней поддереве, то извлечение по логическому номеру можно выполнить с помощью циклического алгоритма, либо линейной рекурсии, благодаря тому, что можно сразу же определить в каком поддереве находится интересующая нас вершина. Счетчики вершин можно корректировать в самом процессе добавления /удаления вершин.
//--- Извлечение по логическому номеру (счетчик вершин в поддереве)struct ctree{int nodes; // Счетчик вершин в поддеревеint val;ctree *p[4]; };int GetNum(ctree *q, int num, int n0){if (q==NULL) return 1; // n0 начальный номер в текущем поддеревеif (n0++==num) return q->val; // начальный номер совпал с требуемым for (int i=0; i< 4; i++){ if (q->p[i]==NULL) continue; int nc= q->p[i]->nodes; // число вершин у потомка if (n0+ nc > num) // выбран потомок return GetNum(q->p[i],num,n0); // с диапазоном номеров else // корректировать начальный номер n0+=nc; // для следующего потомка }}В двоичном дереве каждая вершина имеет не более двух потомков, обозначенных как левый ( left) и правый ( right). Кроме того, на данные, хранимые в вершинах дерева, вводится следующее правило упорядочения: значения вершин левого поддерева всегда меньше, а значения вершин правого поддерева - больше значения в текущей вершине.
struct btree {int val;btree *left,*right; };