Рубрики

Для заданного двоичного дерева выведите все пути от корня к листу.

Для приведенного ниже примера дерева все пути от корня к листу:
10 -> 8 -> 3
10 -> 8 -> 5
10 -> 2 -> 2

Алгоритм:
Используйте путь массива пути [], чтобы сохранить текущий путь от корня до листа. Переход от корня ко всем листьям сверху вниз. При обходе сохраняйте данные всех узлов в текущем пути в массиве path []. Когда мы дойдем до листового узла, выведите массив путей.

C ++

#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка
и указатель на правого ребенка * /

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * Прототипы для функций, необходимых в printPaths () * /

void printPathsRecur(node* node, int path[], int pathLen); 

void printArray(int ints[], int len); 

  
/ * Учитывая двоичное дерево, распечатать все его корень к листу
пути, по одному на строку. Для выполнения работы используется рекурсивный помощник. * /

void printPaths(node* node) 

    int path[1000]; 

    printPathsRecur(node, path, 0); 

  
/ * Рекурсивная вспомогательная функция - заданный узел,
и массив, содержащий путь от корня
узел до, но не включая этот узел,
распечатать все пути корневых листьев. * /

void printPathsRecur(node* node, int path[], int pathLen) 

    if (node == NULL) 

        return

      

    / * добавить этот узел к массиву путей * /

    path[pathLen] = node->data; 

    pathLen++; 

      

    / * это лист, поэтому выведите путь, который привёл сюда * /

    if (node->left == NULL && node->right == NULL) 

    

        printArray(path, pathLen); 

    

    else

    

        / * в противном случае попробуйте оба поддерева * /

        printPathsRecur(node->left, path, pathLen); 

        printPathsRecur(node->right, path, pathLen); 

    

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Утилита, которая печатает массив в строке. * /

void printArray(int ints[], int len) 

    int i; 

    for (i = 0; i < len; i++) 

    

        cout << ints[i] << " "

    

    cout<<endl; 

  
/ * утилита, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

node* newnode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

      

    return(Node); 

  
/ * Код водителя * /

int main() 

      

    / * Построенное двоичное дерево

                10

            / /

            8 2

        ///

        3 5 2

    * /

    node *root = newnode(10); 

    root->left = newnode(8); 

    root->right = newnode(2); 

    root->left->left = newnode(3); 

    root->left->right = newnode(5); 

    root->right->left = newnode(2); 

      

    printPaths(root); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include<stdio.h>
#include<stdlib.h>

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

   int data;

   struct node* left;

   struct node* right;

};

  

/ * Прототипы для функций, необходимых в printPaths () * / 

void printPathsRecur(struct node* node, int path[], int pathLen);

void printArray(int ints[], int len);

  
/ * Учитывая двоичное дерево, распечатать все его корень к листу

 пути, по одному на строку. Для выполнения работы используется рекурсивный помощник. * /

void printPaths(struct node* node) 

{

  int path[1000];

  printPathsRecur(node, path, 0);

}

  
/ * Рекурсивная вспомогательная функция - заданный узел и массив, содержащий

 путь от корневого узла до этого узла, но не включая его,

 распечатать все пути корневых листьев. * /

void printPathsRecur(struct node* node, int path[], int pathLen) 

{

  if (node==NULL) 

    return;

  

  / * добавить этот узел к массиву путей * /

  path[pathLen] = node->data;

  pathLen++;

  

  / * это лист, поэтому выведите путь, который привёл сюда * /

  if (node->left==NULL && node->right==NULL) 

  {

    printArray(path, pathLen);

  }

  else 

  {

    / * в противном случае попробуйте оба поддерева * /

    printPathsRecur(node->left, path, pathLen);

    printPathsRecur(node->right, path, pathLen);

  }

}

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Утилита, которая печатает массив в строке. * /

void printArray(int ints[], int len) 

{

  int i;

  for (i=0; i<len; i++) 

  {

    printf("%d ", ints[i]);

  }

  printf("\n");

}    

  
/ * утилита, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /   

struct node* newnode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

   

  return(node);

}

   
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

   

  / * Построенное двоичное дерево

            10

          / /

        8 2

      ///

    3 5 2

  * /

  struct node *root = newnode(10);

  root->left        = newnode(8);

  root->right       = newnode(2);

  root->left->left  = newnode(3);

  root->left->right = newnode(5);

  root->right->left = newnode(2);

   

  printPaths(root);

   

  getchar();

  return 0;

}

Джава

// Java-программа для печати всего пути к узлу

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

       

    / * Учитывая двоичное дерево, распечатать все его корень к листу

      пути, по одному на строку. Использует рекурсивный помощник, чтобы сделать

      работа.*/

    void printPaths(Node node) 

    {

        int path[] = new int[1000];

        printPathsRecur(node, path, 0);

    }

   

    / * Рекурсивная вспомогательная функция - заданный узел и массив

       содержащий путь от корневого узла до, но не

       включая этот узел, распечатайте все пути корневых листьев. * /

    void printPathsRecur(Node node, int path[], int pathLen) 

    {

        if (node == null)

            return;

   

        / * добавить этот узел к массиву путей * /

        path[pathLen] = node.data;

        pathLen++;

   

        / * это лист, поэтому выведите путь, который привёл сюда * /

        if (node.left == null && node.right == null)

            printArray(path, pathLen);

        else 

        {

            / * в противном случае попробуйте оба поддерева * /

            printPathsRecur(node.left, path, pathLen);

            printPathsRecur(node.right, path, pathLen);

        }

    }

   

    / * Служебная функция, которая печатает массив в строке. * /

    void printArray(int ints[], int len) 

    {

        int i;

        for (i = 0; i < len; i++) 

        {

            System.out.print(ints[i] + " ");

        }

        System.out.println("");

    }

   

    // программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.right = new Node(2);

        tree.root.left.left = new Node(3);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(2);

          

        / * Давайте проверим построенное дерево, напечатав обход Insorder * /

        tree.printPaths(tree.root);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

«»»
Программа Python для печати всего пути от корня до
лист в бинарном дереве
«»»

  
# узел двоичного дерева содержит поле данных,
# левый и правый указатель

class Node:

    # конструктор для создания узла дерева

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# функция для печати всего пути от корня
# листать в двоичном дереве

def printPaths(root):

    # список для хранения пути

    path = []

    printPathsRec(root, path, 0)

  
# Вспомогательная функция для печати пути из корня
# листать в двоичном дереве

def printPathsRec(root, path, pathLen):

      

    # Базовое условие - если двоичное дерево

    # пустой возврат

    if root is None:

        return

  

    # добавить данные текущего корня в

    # path_ar list

      

    # если длина списка gre

    if(len(path) > pathLen): 

        path[pathLen] = root.data

    else:

        path.append(root.data)

  

    # прирост pathLen на 1

    pathLen = pathLen + 1

  

    if root.left is None and root.right is None:

          

        # лист узла затем распечатать список

        printArray(path, pathLen)

    else:

        # попробуйте левое и правое поддерево

        printPathsRec(root.left, path, pathLen)

        printPathsRec(root.right, path, pathLen)

  
# Вспомогательная функция для печати списка, в котором
# путь от корня к листу сохраняется

def printArray(ints, len):

    for i in ints[0 : len]:

        print(i," ",end="")

    print()

  
# Программа драйвера для проверки вышеуказанной функции
«»»
Построенное двоичное дерево

            10

        / /

        8 2

    ///

    3 5 2

«»»

root = Node(10)

root.left = Node(8)

root.right = Node(2)

root.left.left = Node(3)

root.left.right = Node(5)

root.right.left = Node(2)

printPaths(root)

  
# Этот код предоставлен Shweta Singh.

C #

using System;

  
// C # программа для печати всего узла на конечный путь

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    / * Учитывая двоичное дерево, распечатать все его корень к листу

      пути, по одному на строку. Использует рекурсивный помощник, чтобы сделать

      работа.*/

    public virtual void printPaths(Node node)

    {

        int[] path = new int[1000];

        printPathsRecur(node, path, 0);

    }

  

    / * Рекурсивная вспомогательная функция - заданный узел и массив

       содержащий путь от корневого узла до, но не

       включая этот узел, распечатайте все пути корневых листьев. * /

    public virtual void printPathsRecur(Node node, int[] path, int pathLen)

    {

        if (node == null)

        {

            return;

        }

  

        / * добавить этот узел к массиву путей * /

        path[pathLen] = node.data;

        pathLen++;

  

        / * это лист, поэтому выведите путь, который привёл сюда * /

        if (node.left == null && node.right == null)

        {

            printArray(path, pathLen);

        }

        else

        {

            / * в противном случае попробуйте оба поддерева * /

            printPathsRecur(node.left, path, pathLen);

            printPathsRecur(node.right, path, pathLen);

        }

    }

  

    / * Служебная функция, которая печатает массив в строке. * /

    public virtual void printArray(int[] ints, int len)

    {

        int i;

        for (i = 0; i < len; i++)

        {

            Console.Write(ints[i] + " ");

        }

        Console.WriteLine("");

    }

  

    // программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.right = new Node(2);

        tree.root.left.left = new Node(3);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(2);

  

        / * Давайте проверим построенное дерево, напечатав обход Insorder * /

        tree.printPaths(tree.root);

    }

}

  
// Этот код предоставлен Shrikant13


Выход :

10 8 3 
10 8 5 
10 2 2 

Сложность времени: O (n 2 ) где n — количество узлов.

Ссылки:
http://cslibrary.stanford.edu/110/BinaryTrees.html

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенных выше кодах / алгоритмах, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Для заданного двоичного дерева выведите все пути от корня к листу.

0.00 (0%) 0 votes