Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.
Итак… язык Java, класс узла имеет следующий вид:
public class Node {
Node left;
Node right;
Node parent;
String value;
public Node(Node p, String v){
parent=p;
value=v;
}
…
}
Примечание: Указатель на родителя parent – как правило не имеет большого смысла, однако, как следует из заголовка и будет показано, может быть полезен в ряде случаев.
Обход деревьев – последовательная обработка (просмотр, изменение и т.п.) всех узлов дерева, при котором каждый узел обрабатывается строго один раз. При этом получается линейная расстановка узлов дерева.
В зависимости от траекторий выделяют два типа обхода:
— горизонтальный (в ширину); и
— вертикальный (в глубину).
Горизонтальный обход подразумевает обход дерева по уровням (level-ordered) – вначале обрабатываются все узлы текущего уровня, после чего осуществляется переход на нижний уровень.
При вертикальном обходе порядок обработки текущего узла и узлов его правого и левого поддеревьев варьирует и по этому признаку выделяют три варианта вертикального обхода:
— прямой (префиксный, pre-ordered): вершина – левое поддерево – правое поддерево;
— обратный (инфиксный, in-ordered): левое поддерево – вершина – правое поддерево; и
— концевой (постфиксный, post-ordered): левое поддерево – правое поддерево – вершина.
Сам обход во всех случаях в принципе один и тот же, различается порядок обработки. Для представления в каком порядке будет проходить обработка узлов дерева удобно следовать по «контуру обхода». При прямом обходе узел будет обработан в точке слева от узла, при обратном снизу от узла и при концевом, соответственно, справа от узла.
Рекурсия
Все три варианта вертикального обхода элементарно реализуются рекурсивными функциями.
void recPreOrder(){
treatment();
if (left!=null) left.recPreOrder();
if (right!=null) right.recPreOrder();
}
void recInOrder(){
if (left!=null) left.recInOrder();
treatment();
if (right!=null) right.recInOrder();
}
void recPostOrder(){
if (left!=null) left.recPostOrder();
if (right!=null) right.recPostOrder();
treatment();
}
Рекурсия крайне удобна не только при обходе, но также при построении дерева, поиска в дереве, а также балансировки. Однако рекурсией нельзя осуществить горизонтальный обход дерева. В этом случае, а так же при обеспокоенности перегрузкой программного стека, следует применять итерационный подход.
Контейнеры
В случае использования итераций необходимо хранить сведенья о посещенных, но не обработанных узлах. Используются контейнеры типа стек (для вертикального обхода) и очередь (для горизонтального обхода).
Горизонтальный обход:
обрабатываем первый в очереди узел, при наличии дочерних узлов заносим их в конец очереди. Переходим к следующей итерации.
static void contLevelOrder(Node top){
Queue queue=new LinkedList<> ();
do{
top.treatment();
if (top.left!=null) queue.add(top.left);
if (top.right!=null) queue.add(top.right);
if (!queue.isEmpty()) top=queue.poll();
}while (!queue.isEmpty());
}
Вертикальный прямой обход:
обрабатываем текущий узел, при наличии правого поддерева добавляем его в стек для последующей обработки. Переходим к узлу левого поддерева. Если левого узла нет, переходим к верхнему узлу из стека.
static void contPreOrder(Node top){
Stack stack = new Stack<> ();
while (top!=null || !stack.empty()){
if (!stack.empty()){
top=stack.pop();
}
while (top!=null){
top.treatment();
if (top.right!=null) stack.push(top.right);
top=top.left;
}
}
}
Вертикальный обратный обход:
из текущего узла «спускаемся» до самого нижнего левого узла, добавляя в стек все посещенные узлы. Обрабатываем верхний узел из стека. Если в текущем узле имеется правое поддерево, начинаем следующую итерацию с правого узла. Если правого узла нет, пропускаем шаг со спуском и переходим к обработке следующего узла из стека.
static void contInOrder(Node top){
Stack stack = new Stack<> ();
while (top!=null || !stack.empty()){
if (!stack.empty()){
top=stack.pop();
top.treatment();
if (top.right!=null) top=top.right;
else top=null;
}
while (top!=null){
stack.push(top);
top=top.left;
}
}
}
Вертикальный концевой обход:
Здесь ситуация усложняется – в отличие от обратного обхода, помимо порядка спуска нужно знать обработано ли уже правое поддерево. Одним из вариантов решения является внесение в каждый экземпляр узла флага, который бы хранил соответствующую информацию (не рассматривается). Другим подходом является «кодирование» непосредственно в очередности стека — при спуске, если у очередного узла позже нужно будет обработать еще правое поддерево, в стек вносится последовательность «родитель, правый узел, родитель». Таким образом, при обработке узлов из стека мы сможем определить, нужно ли нам обрабатывать правое поддерево.
static void contPostOrder(Node top){
Stack stack = new Stack<> ();
while (top!=null || !stack.empty()){
if (!stack.empty()){
top=stack.pop();
if (!stack.empty() && top.right==stack.lastElement()){
top=stack.pop();
}else{
top.treatment();
top=null;
}
}
while (top!=null){
stack.push(top);
if (top.right!=null){
stack.push(top.right);
stack.push(top);
}
top=top.left;
}
}
}
Об указателе на родителя
Наличие в экземпляре класса указателя на родителя приносит определенные хлопоты при построении и балансировки деревьев. Однако, возможность из произвольного узла дерева «дойти» до любого из его узлов может придтись весьма кстати. Все, за чем нужно следить при «подъеме» на верхний уровень – пришли ли от правого потомка или от левого.
Так, с использованием родительских указателей будет выглядеть код вертикального концевого обхода.
static void parentPostOrder(Node top){
boolean fromright=false;
Node shuttle=top, holder;
while(true){
while (fromright){
shuttle.treatment();
if (shuttle==top) return;
holder=shuttle;
shuttle=shuttle.parent;
fromright=shuttle.right==holder;
if (!fromright && shuttle.right!=null) shuttle=shuttle.right;
else fromright=true;
}
while (shuttle.left!=null) shuttle=shuttle.left;
if (shuttle.right!=null) shuttle=shuttle.right;
else fromright=true;
}
}
Другой класс задач, которые позволяет решить родительский указатель, как уже было упомянуто — перемещение внутри дерева.
Так, что бы перейти на n-ый по счету узел от текущего узла, без «ориентации в дереве» пришлось бы обходить дерево с самого начала, до известного узла, а потом еще n-узлов. С использованием же родительского указателя при обратном обходе дерева перемещение на steps узлов от текущего узла (start) будет иметь следующий вид.
public static Node walkTheTree(Node start, int steps){
boolean fromright=true;
Node shuttle=start, holder;
if (shuttle.right!=null){
shuttle=shuttle.right;
while (shuttle.left!=null) shuttle=shuttle.left;
fromright=false;
}
int counter=0;
do{
while (true){
if (!fromright && ++counter==steps) return shuttle;
if (!fromright && shuttle.right!=null){
shuttle=shuttle.right;
break;
}
holder=shuttle;
shuttle=shuttle.parent;
fromright=(holder==shuttle.right);
}
while (shuttle.left!=null) shuttle=shuttle.left;
}while (true);
}
Примечание: В общем случае также требуется предотвратить возможность попытки выхода за пределы дерева (подняться выше корневого узла).
Автор: alezhe
