Рубрики

Итерационный метод определения высоты двоичного дерева

Есть два соглашения для определения высоты двоичного дерева
1) Количество узлов на самом длинном пути от корня до самого глубокого узла.
2) Количество ребер на самом длинном пути от корня до самого глубокого узла.

В этом посте первое соглашение сопровождается. Например, высота нижнего дерева равна 3.

Пример дерева

Рекурсивный метод определения высоты двоичного дерева обсуждается здесь . Как найти высоту без рекурсии? Мы можем использовать обход уровня, чтобы найти высоту без рекурсии. Идея состоит в том, чтобы пройти уровень за уровнем. Всякий раз, когда переходите к уровню, увеличивайте высоту на 1 (высота инициализируется как 0). Подсчитайте количество узлов на каждом уровне, прекратите прохождение, когда количество узлов на следующем уровне равно 0.
Ниже приведен подробный алгоритм поиска уровня порядка с помощью очереди.

Create a queue.
Push root into the queue.
height = 0
Loop
    nodeCount = size of queue
        
        // If the number of nodes at this level is 0, return height
    if nodeCount is 0
        return Height;
    else
        increase Height

        // Remove nodes of this level and add nodes of 
        // next level
    while (nodeCount > 0)
        pop node from front
        push its children to queue
        decrease nodeCount
       // At this point, queue has nodes of next level

Ниже приведена реализация вышеуказанного алгоритма.

C ++

/ * Программа для определения высоты дерева итерационным методом * /
#include <iostream>
#include <queue>

using namespace std;

  
// Узел двоичного дерева

struct node

{

    struct node *left;

    int data;

    struct node *right;

};

  
// Итерационный метод для определения высоты двоичного дерева

int treeHeight(node *root)

{

    // Базовый вариант

    if (root == NULL)

        return 0;

  

    // Создаем пустую очередь для прохождения уровня заказа

    queue<node *> q;

  

    // ставим в очередь Root и инициализируем высоту

    q.push(root);

    int height = 0;

  

    while (1)

    {

        // nodeCount (размер очереди) указывает количество узлов

        // на текущем уровне.

        int nodeCount = q.size();

        if (nodeCount == 0)

            return height;

  

        height++;

  

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

        // узлы следующего уровня

        while (nodeCount > 0)

        {

            node *node = q.front();

            q.pop();

            if (node->left != NULL)

                q.push(node->left);

            if (node->right != NULL)

                q.push(node->right);

            nodeCount--;

        }

    }

}

  
// Сервисная функция для создания нового узла дерева

node* newNode(int data)

{

    node *temp = new node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;

}

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

int main()

{

    // Давайте создадим двоичное дерево, показанное на диаграмме выше

    node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

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

  

    cout << "Height of tree is " << treeHeight(root);

    return 0;

}

Джава

// Итеративная Java-программа для определения высоты бинарного дерева

   

import java.util.LinkedList;

import java.util.Queue;

   
// Узел двоичного дерева

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Итерационный метод для определения высоты бинарного дерева

    int treeHeight(Node node) 

    {

        // Базовый вариант

        if (node == null)

            return 0;

   

        // Создаем пустую очередь для прохождения уровня заказа

        Queue<Node> q = new LinkedList();

   

        // ставим в очередь Root и инициализируем высоту

        q.add(node);

        int height = 0;

   

        while (1 == 1

        {

            // nodeCount (размер очереди) указывает количество узлов

            // на текущем уровне.

            int nodeCount = q.size();

            if (nodeCount == 0)

                return height;

            height++;

   

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

            // узлы следующего уровня

            while (nodeCount > 0

            {

                Node newnode = q.peek();

                q.remove();

                if (newnode.left != null)

                    q.add(newnode.left);

                if (newnode.right != null)

                    q.add(newnode.right);

                nodeCount--;

            }

        }

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

          

        // Давайте создадим двоичное дерево, показанное на диаграмме выше

        tree.root = new Node(1);

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

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

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

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

        System.out.println("Height of tree is " + tree.treeHeight(tree.root));

    }

}

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

питон

# Программа для определения высоты дерева методом итерации

  
# Узел двоичного дерева

class Node:

      

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Итерационный метод для определения высоты двоичного дерева

def treeHeight(root):

      

    # Базовый вариант

    if root is None:

        return 0

      

    # Создать пустую очередь для прохождения порядка уровней

    q = []

      

    # Поставить в очередь Root и инициализировать высоту

    q.append(root)

    height = 0 

  

    while(True):

          

        # nodeCount (размер очереди) указывает количество узлов

        # на текущем уровне

        nodeCount = len(q)

        if nodeCount == 0 :

            return height 

      

        height += 1 

  

        # Удаление всех узлов текущего уровня и постановка в очередь

        # все узлы следующего уровня

        while(nodeCount > 0):

            node = q[0]

            q.pop(0)

            if node.left is not None:

                q.append(node.left)

            if node.right is not None:

                q.append(node.right)

  

            nodeCount -= 1

  

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

  

print "Height of tree is", treeHeight(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// Итеративная программа на C # для
// найти высоту бинарного дерева

using System;

using System.Collections.Generic; 

  
// Узел двоичного дерева

class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        left = right;

    }

}

  

public class BinaryTree 

{

    Node root;

  

    // Итерационный метод для поиска

    // высота бинарного дерева

    int treeHeight(Node node) 

    {

        // Базовый вариант

        if (node == null)

            return 0;

  

        // Создать пустую очередь

        // для уровня заказа tarversal

        Queue<Node> q = new Queue<Node>();

  

        // ставим в очередь Root и инициализируем высоту

        q.Enqueue(node);

        int height = 0;

  

        while (1 == 1) 

        {

            // nodeCount (размер очереди) указывает

            // количество узлов на текущем уровне.

            int nodeCount = q.Count;

            if (nodeCount == 0)

                return height;

            height++;

  

            // Удаление всех узлов текущего

            // выравниваем и ставим все в очередь

            // узлы следующего уровня

            while (nodeCount > 0) 

            {

                Node newnode = q.Peek();

                q.Dequeue();

                if (newnode.left != null)

                    q.Enqueue(newnode.left);

                if (newnode.right != null)

                    q.Enqueue(newnode.right);

                nodeCount--;

            }

        }

    }

  

    // Код драйвера

    public static void Main(String []args) 

    {

        BinaryTree tree = new BinaryTree();

          

        // Давайте создадим бинарный файл

        // дерево показано на диаграмме выше

        tree.root = new Node(1);

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

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

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

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

        Console.WriteLine("Height of tree is "

                        tree.treeHeight(tree.root));

    }

}

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


Выход:

Height of tree is 3

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

Эта статья предоставлена Рахулом Кумаром . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Итерационный метод определения высоты двоичного дерева

0.00 (0%) 0 votes