>>
Бинарные деревья. Обход в прямом порядке Наука Наука 

Бинарные деревья. Обход в прямом порядке

admin

Связные списки, стеки и очереди являются линейными структурами данных (это последовательности). Деревья представляют собой нелинейную двумерную структуру данных со специальными свойствами. Узлы дерева содержат две или более ссылок. В этом примере рассматриваются бинарные деревья, т.е. деревья, узлы которого содержат по две ссылки (одна или обе из которых могут быть NULL).
Корневой узел является первым узлом дерева. Каждая ссылка в корневом узле указывает на дочерний узел или узел-потомок. Левый узел-потомок является первым узлом в левом поддереве, а правый узел-потомок является первым узлом в правом поддереве. Узлы-потомки, принадлежащие одному какому-либо узлу, называются родственными узлами. Узел без узлов-потомков называется листом дерева или концевым узлом. Компьютерщики обычно рисуют деревья сверху-вниз, начиная с корневого узла, то есть противоположно тому, как растут деревья в природе.
В этом примере рассмотрим обход бинарного дерева в прямом порядке. Каждый узел посещается до того, как посещены его потомки.

Для корня дерева выполняются следующие шаги:

  • Посетить узел
  • Обойти левое поддерево
  • Обойти правое поддерево

Это может быть реализовано двумя способами

  • рекурсивно
  • итерационно (пошагово)

Шаги для итерационного решения:
Создать пустой стек и поместить в него корневой узел.
Выполните следующие действия, до тех по пока стек не пуст:
Возьмите узел из стека, и распечатайте его
Поместите правого потомка узла в стек
Поместите левого потомка узла в стек

Мы помещаем первым правого потомка, но он будет обработан после левого поддерева, так как стек организован по принципу Last In First Out (LIFO).

package java1;
 

  import java.util.Stack;  
  
public class Test {  
  
   
 public static class TreeNode  
 {  
  int data;  
  TreeNode left;  
  TreeNode right;  
  TreeNode(int data)  
  {  
   this.data=data;  
  }  
 }  
   
        // Recursive Solution  
 public void recursive(TreeNode root) {  
    if(root !=  null) {  
   //Visit the node-Printing the node data    
      System.out.printf("%d ",root.data);  
      recursive(root.left);  
      recursive(root.right);  
    }  
  }  
   
  // Iterative solution  
  public void Iter(TreeNode root) {  
     
         if(root == null)  
             return;  
    
         Stack<TreeNode> stack = new Stack<TreeNode>();  
         stack.push(root);  
    
         while(!stack.empty()){  
            
             TreeNode n = stack.pop();  
             System.out.printf("%d ",n.data);  
    
             
             if(n.right != null){  
                 stack.push(n.right);  
             }  
             if(n.left != null){  
                 stack.push(n.left);  
             }  
    
         }  
           
     }  
   
 public static void main(String[] args)  
 {  
  Test bi=new Test();  
  // Creating a binary tree  
  TreeNode rootNode=createTest();  
  System.out.println("Using Recursive solution:");  
    
  bi.recursive(rootNode);  
    
  System.out.println();  
  System.out.println("-------------------------");  
  System.out.println("Using Iterative solution:");  
    
  bi.Iter(rootNode);  
 }  
   
 public static TreeNode createTest()  
 {  
    
  TreeNode rootNode =new TreeNode(40);  
  TreeNode node20=new TreeNode(20);  
  TreeNode node10=new TreeNode(10);  
  TreeNode node30=new TreeNode(30);  
  TreeNode node60=new TreeNode(60);  
  TreeNode node50=new TreeNode(50);  
  TreeNode node70=new TreeNode(70);  
    
  rootNode.left=node20;  
  rootNode.right=node60;  
    
  node20.left=node10;  
  node20.right=node30;  
    
  node60.left=node50;  
  node60.right=node70;  
    
  return rootNode;  
 }  
}

Результат выполнения программы:

Using Recursive solution:
40 20 10 30 60 50 70 
-------------------------
Using Iterative solution:
40 20 10 30 60 50 70

 

Похожие записи