Нахождение границы бинарного дерева

Question

Нам дано двоичное дерево поиска;нам нужно выяснить его границу.

Итак, если бинарное дерево

           10
       /         \
     50           150
    /  \         /   \
  25    75     200    20
 / \           /      / \
15 35        120    155 250 

Оно должно распечатать 50 25 15 35 120 155 250 20 150 10.

Если бинарное дерево

               10
           /         \
         50           150
        /  \         /   
      25    75     200   
     / \   / \    
    15 35 65 30  

Это должно быть похоже на 50 25 15 35 65 30 200 150 10.

Как это можно сделать?Обобщает ли это бинарное дерево проблему еще сложнее?

Любая помощь по ссылкам также приветствуется.

PS: пожалуйста, обратите внимание, что шаблон начинается не с корня, а слева(в этом случае).Оно также может начинаться с права, но всегда заканчивается корнем.

Answer 1

То, что вы запрашиваете, - это модифицированный обход в глубину, когда значения узла печатаются / возвращаются только в том случае, если 1) узел является листовым узлом или 2) узел проходит по «внешнему пути» дерева, где «внешний путь» определяется как

Узел является частью «внешнего пути», если вы прибыли на узел, следуя всем левым (или правым) путям от корня, или если узел является правым (или левым) потомком родителя узел, который сам был частью «внешнего пути», но не имел левого (или правого) потомка.

Если вы знаете, как кодировать DFS, то модификация здесь может быть реализована путем проверки нескольких дополнительных условий во время обхода.

Answer 2

Вы можете указать два логических значения, чтобы указать, что печатать.

Для начала вызовите printBorder (root, true, true).Редактировать: не печатать корень в конце, но в начале, если это особый случай

Answer 3

printBorder(node *n){

   printLeft(n);   O(log n)
   printBottom(n); O(n)
   printRight(n);  O(log n)
}

printBottom(node *n)
{
  int h = treeHeight(n);
  printBottomHelper(n, 0);
}
printBottomHelper(n, h, max)
{
   if(h == max) {
    print n->data
  }
   printBottomHelper(n->left, h+1, max);
   printBottomHelper(n->right, h+1, max);
}
printLeft(node *n)
{
  while(n!= null){
   node *l = n->left;
   l!= null ? print l->data:1
   n =l;
  }
}

Answer 4

Я не уверен, имеет ли это значение, является ли это двоичным деревом или нет.Я думаю, что алгоритм обхода будет одинаковым в любом случае.

Начните с левого поддерева и выполните сначала модифицированную ширину обхода, которая печатает узел, только если это левый брат или ребро.это будет печатать левых братьев и сестер до тех пор, пока они не дойдут до краев, а затем распечатает листья.

Затем вы сначала изменяете глубину по правому дереву, которое печатает правого брата или лист.Это напечатает все правильные листья поддерева, и затем правильные родные братья.