Влево или вправо Вид дерева

Question

Каков эффективный код, обеспечивающий левый/правый вид дерева.

EX: -

       1 
          / \ 
    left view--->>   4  7     <<--right view 
          /\ /
          3 2 9 
           /
           8 

Левый взгляд на это дерево 1 4 ИС-3 8 и правого зрения - 1 7 9 8

Я попытался с порядком обхода уровня, но если у дерева есть некоторый недостающий ребенок, тогда мне трудно найти начальную точку (в случае просмотра слева) или конечную точку (в режиме просмотра справа) для уровня, просьба дать предложения

Answer 1

Вы правы, что , с обходным порядком типа

Queue<Node> queue = new ArrayDeque<Node>(); 
for (Node node = root; node != null; node = queue.poll()) { 
    if (node.leftChild != null) queue.add(node.leftChild); 
    if (node.rightChild != null) queue.add(node.rightChild); 
} 

трудно узнать, где заканчивается один уровень, и начинается следующее. Это можно решить, используя две очереди.

Queue<Node> currentLevel = new ArrayDeque<Node>(); 
if (root != null) currentLevel.add(root); 
while (true) { 
    Node node = currentLevel.poll(); 
    if (node == null) break; 
    /* node is the leftmost on its level */ 
    Queue<Node> nextLevel = new ArrayDeque<Node>(); 
    do { 
     if (node.leftChild != null) nextLevel.add(node.leftChild); 
     if (node.rightChild != null) nextLevel.add(node.rightChild); 
     node = currentLevel.poll(); 
    } while (node != null); 
    currentLevel = nextLevel; 
} 

Answer 2

Нетрудно получить левый (или правый) вид, используя ТОЛЬКО одну Очередь. После того, как вы запустили самый правый дочерний узел, вставьте «null» в очередь в качестве флага, чтобы отметить конец следующего (дочернего) уровня при выполнении обхода уровня.

class Node{ 
    Node left, right; 
    int value; 
    Node(int value){ 
     left=right=null; 
     this.value = value; 
    } 
} 
public class BinaryTree 
{ 
    Node root; 
    public void leftView(){ 
     //Using single queue. 
     boolean leftmost = true; 
     if(this.root == null) return; 
     Queue<Node> q = new LinkedList<>(); 
     q.add(this.root); 
     q.add(null); 
     while(q.isEmpty() == false){ 
      Node rear = q.poll(); 
      if(leftmost == true) { 
       if(rear == null) break; 
       System.out.print(rear.value + " "); 
       leftmost = false; 
      } 
      if(rear.left != null) q.add(rear.left); 
      if(rear.right != null) q.add(rear.right); 
      if(q.peek() == null) { 
       leftmost = true; 
       q.poll(); //remove it from rear 
       q.add(null); //add it at front. 
      } 
     } 
     //OUTPUT : 12 10 25 50 
    } 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     BinaryTree bt = new BinaryTree(); 
     bt.root = new Node(12); 
     bt.root.left = new Node(10); 
     bt.root.right = new Node(30); 
     bt.root.right.left = new Node(25); 
     bt.root.right.left.left = new Node(50); 
     bt.root.right.right = new Node(40); 
     //   12 
     //  / \ 
     //  10  30 
     //   / \ 
     //   25  40 
     //  /
     //  50 
     bt.leftView(); 
    } 
} 

Answer 3

Алгоритм печати Вид слева:

1. Возьмите глобальную переменную МАКСЛЕВЕЛ, чтобы следить за максимальным уровнем охватываемого до сих пор.
2. Теперь, когда мы получаем уровень выше maxLevel, мы печатаем значение этого узла.
3. Мы делаем это заранее, чтобы левый был напечатан перед правом, если он присутствует.

Вот окончательный код:

class BinaryTree { 

    class TreeNode { 
     int data; 
     TreeNode left; 
     TreeNode right; 

     public TreeNode(int data) { 
      this.data=data; 
     } 
    } 

    private static int maxLevel = -1; 

    public static leftView(TreeNode root) { 
     left_view(root, 0); 
    } 

    private static void left_view(BTNode root, int level) { 
     if (root == null) 
      return; 

     if (level > maxLevel) { 
      System.out.println(root.data); 
      maxLevel = level; 
     } 

     left_view(root.left, level + 1); 
     left_view(root.right, level + 1); 
    } 

Answer 4

пакет com.Trees.sumit;

импорт java.util.LinkedList; импорт java.util.Queue;

общественного класса LeftView {

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    TreeNode root = createBinaryTree(); 
    Queue<TreeNode> queue = new LinkedList<>(); 
    System.out.println("Left View"); 
    queue.add(root); 
    while (!queue.isEmpty()) { 

     System.out.println(queue.peek().data); 

     int queueSize = queue.size(); 

     while (queueSize > 0) { 

      TreeNode removedNode = queue.poll(); 


      if (removedNode.left != null) 
       queue.add(removedNode.left); 

      if (removedNode.right != null) 
       queue.add(removedNode.right); 



      queueSize--; 
     } 

    } 

} 

public static class TreeNode { 

    int data; 
    TreeNode left; 
    TreeNode right; 

    public TreeNode(int data) { 
     super(); 
     this.data = data; 
    } 

} 

private static TreeNode createBinaryTree() { 
    // TODO Auto-generated method stub 
    TreeNode rootNode = new TreeNode(40); 
    TreeNode root20 = new TreeNode(20); 
    TreeNode root10 = new TreeNode(10); 
    TreeNode root30 = new TreeNode(30); 
    TreeNode root50 = new TreeNode(50); 
    TreeNode root55 = new TreeNode(55); 
    TreeNode root57 = new TreeNode(57); 

    TreeNode root60 = new TreeNode(60); 
    TreeNode root70 = new TreeNode(70); 

    rootNode.left = root20; 
    rootNode.right = root60; 

    root50.right = root55; 
    root55.right = root57; 

    root20.left = root10; 
    root20.right = root30; 

    root60.left = root50; 
    root60.right = root70; 

    return rootNode; 
} 

}