Как найти максимальную ширину

Как найти максимальную ширину

Given a binary tree, the task is to find the maximum width of the given tree. The width of a tree is the maximum of the widths of all levels. Before solving the problem first let us understand what we have to do. Binary trees are one of the most common types of trees in computer science. They are also called “balanced” trees because all of their nodes have an equal number of children. In this case, we will focus on finding the maximum value of W, which is the width of a binary tree. For example, given a binary tree with root node A, which has two children B and C, where B has two children D and E and C has one child F, the maximum width is 3.
The maximum width of a binary tree is the number of nodes in the tree that have no children. In other words, it is the minimum number of nodes in a tree that can be traversed before you need to make a choice on which node to visit next. 

Example: 

Input:
             1
          /  
       2      3
    /        
 4     5       8 
              /    
           6        7
Output:  3
Explanation: For the above tree, 
width of level 1 is 1, 
width of level 2 is 2, 
width of level 3 is 3 
width of level 4 is 2. 
So the maximum width of the tree is 3.

Maximum Width using Level Order Traversal:

To get the width of each level we can use the level order traversal. The maximum among the width of all levels is the required answer.

Level Order Traversal without queue:

This method mainly involves two functions:

  • One is to count nodes at a given level (getWidth), and 
  • The other is to get the maximum width of the tree(getMaxWidth). getMaxWidth() makes use of getWidth() to get the width of all levels starting from root.

Given below are the pseudo codes for the mentioned functions.

getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
    width =   getWidth(tree, i);
    if(width > maxWdth) 
        maxWdth  = width
return maxWidth

getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;  
else if level greater than 1, then
    return getWidth(tree->left, level-1) + 
                getWidth(tree->right, level-1);

Below is the implementation of the above idea:

C++

#include <bits/stdc++.h>

using namespace std;

class node {

public:

    int data;

    node* left;

    node* right;

    node (int d){

      this->data = d;

      this->left = this->right = NULL;

    }

};

int getWidth(node* root, int level);

int height(node* node);

int getMaxWidth(node* root)

{

    int maxWidth = 0;

    int width;

    int h = height(root);

    int i;

    for (i = 1; i <= h; i++) {

        width = getWidth(root, i);

        if (width > maxWidth)

            maxWidth = width;

    }

    return maxWidth;

}

int getWidth(node* root, int level)

{

    if (root == NULL)

        return 0;

    if (level == 1)

        return 1;

    else if (level > 1)

        return getWidth(root->left, level - 1)

               + getWidth(root->right, level - 1);

}

int height(node* node)

{

    if (node == NULL)

        return 0;

    else {

        int lHeight = height(node->left);

        int rHeight = height(node->right);

        return (lHeight > rHeight) ? (lHeight + 1)

                                   : (rHeight + 1);

    }

}

int main()

{

    node* root = new node(1);

    root->left = new node(2);

    root->right = new node(3);

    root->left->left = new node(4);

    root->left->right = new node(5);

    root->right->right = new node(8);

    root->right->right->left = new node(6);

    root->right->right->right = new node(7);

    cout << "Maximum width is " << getMaxWidth(root)

         << endl;

    return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

struct node {

    int data;

    struct node* left;

    struct node* right;

};

int getWidth(struct node* root, int level);

int height(struct node* node);

struct node* newNode(int data);

int getMaxWidth(struct node* root)

{

    int maxWidth = 0;

    int width;

    int h = height(root);

    int i;

    for (i = 1; i <= h; i++) {

        width = getWidth(root, i);

        if (width > maxWidth)

            maxWidth = width;

    }

    return maxWidth;

}

int getWidth(struct node* root, int level)

{

    if (root == NULL)

        return 0;

    if (level == 1)

        return 1;

    else if (level > 1)

        return getWidth(root->left, level - 1)

               + getWidth(root->right, level - 1);

}

int height(struct node* node)

{

    if (node == NULL)

        return 0;

    else {

        int lHeight = height(node->left);

        int rHeight = height(node->right);

        return (lHeight > rHeight) ? (lHeight + 1)

                                   : (rHeight + 1);

    }

}

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()

{

    struct node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

    root->right->right = newNode(8);

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

    root->right->right->right = newNode(7);

    printf("Maximum width is %d n", getMaxWidth(root));

    getchar();

    return 0;

}

Java

class Node {

    int data;

    Node left, right;

    Node(int item)

    {

        data = item;

        left = right = null;

    }

}

class BinaryTree {

    Node root;

    int getMaxWidth(Node node)

    {

        int maxWidth = 0;

        int width;

        int h = height(node);

        int i;

        for (i = 1; i <= h; i++) {

            width = getWidth(node, i);

            if (width > maxWidth)

                maxWidth = width;

        }

        return maxWidth;

    }

    int getWidth(Node node, int level)

    {

        if (node == null)

            return 0;

        if (level == 1)

            return 1;

        else if (level > 1)

            return getWidth(node.left, level - 1)

                + getWidth(node.right, level - 1);

        return 0;

    }

    int height(Node node)

    {

        if (node == null)

            return 0;

        else {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1)

                                       : (rHeight + 1);

        }

    }

    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);

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

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

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

        System.out.println("Maximum width is "

                           + tree.getMaxWidth(tree.root));

    }

}

Python3

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def getMaxWidth(root):

    maxWidth = 0

    h = height(root)

    for i in range(1, h+1):

        width = getWidth(root, i)

        if (width > maxWidth):

            maxWidth = width

    return maxWidth

def getWidth(root, level):

    if root is None:

        return 0

    if level == 1:

        return 1

    elif level > 1:

        return (getWidth(root.left, level-1) +

                getWidth(root.right, level-1))

def height(node):

    if node is None:

        return 0

    else:

        lHeight = height(node.left)

        rHeight = height(node.right)

        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

root.right.right.left = Node(6)

root.right.right.right = Node(7)

print ("Maximum width is %d" % (getMaxWidth(root)))

C#

using System;

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 int getMaxWidth(Node node)

    {

        int maxWidth = 0;

        int width;

        int h = height(node);

        int i;

        for (i = 1; i <= h; i++) {

            width = getWidth(node, i);

            if (width > maxWidth) {

                maxWidth = width;

            }

        }

        return maxWidth;

    }

    public virtual int getWidth(Node node, int level)

    {

        if (node == null) {

            return 0;

        }

        if (level == 1) {

            return 1;

        }

        else if (level > 1) {

            return getWidth(node.left, level - 1)

                + getWidth(node.right, level - 1);

        }

        return 0;

    }

    public virtual int height(Node node)

    {

        if (node == null) {

            return 0;

        }

        else {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1)

                                       : (rHeight + 1);

        }

    }

    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);

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

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

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

        Console.WriteLine("Maximum width is "

                          + tree.getMaxWidth(tree.root));

    }

}

Javascript

<script>

class Node {

    constructor(val) {

        this.data = val;

        this.left = null;

        this.right = null;

    }

}

    var root;

    function getMaxWidth(node)

    {

        var maxWidth = 0;

        var width;

        var h = height(node);

        var i;

        for (i = 1; i <= h; i++) {

            width = getWidth(node, i);

            if (width > maxWidth)

                maxWidth = width;

        }

        return maxWidth;

    }

    function getWidth(node , level)

    {

        if (node == null)

            return 0;

        if (level == 1)

            return 1;

        else if (level > 1)

            return getWidth(node.left, level - 1)

                + getWidth(node.right, level - 1);

        return 0;

    }

    function height(node)

    {

        if (node == null)

            return 0;

        else {

            var lHeight = height(node.left);

            var rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1)

                                       : (rHeight + 1);

        }

    }

        root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

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

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

        root.right.right = new Node(8);

        root.right.right.left = new Node(6);

        root.right.right.right = new Node(7);

        document.write("Maximum width is "

                           + getMaxWidth(root));

</script>

Time Complexity: O(N2) in the worst case.
Auxiliary Space: O(1)

We can use Queue based level order traversal to optimize the time complexity of this method. The Queue based level order traversal will take O(N) time in worst case. Thanks to Nitish, DivyaC and tech.login.id2 for suggesting this optimization. 

Level Order Traversal using Queue

When a queue is used, we can count all the nodes in a level in constant time. This reduces the complexity to be a linear one. 

In this method do the following:

  • Store all the child nodes at the current level in the queue. 
    • Count the total number of nodes after the level order traversal for a particular level is completed. 
    • Since the queue now contains all the nodes of the next level, we can easily find out the total number of nodes in the next level by finding the size of the queue. 
  • Follow the same procedure for the successive levels. 
  • Store and update the maximum number of nodes found at each level.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

    Node(int d)

    {

        this->data = d;

        this->left = this->right = NULL;

    }

};

int maxWidth(struct Node* root)

{

    if (root == NULL)

        return 0;

    int result = 0;

    queue<Node*> q;

    q.push(root);

    while (!q.empty()) {

        int count = q.size();

        result = max(count, result);

        while (count--) {

            Node* temp = q.front();

            q.pop();

            if (temp->left != NULL)

                q.push(temp->left);

            if (temp->right != NULL)

                q.push(temp->right);

        }

    }

    return result;

}

int main()

{

    struct Node* root = new Node(1);

    root->left = new Node(2);

    root->right = new Node(3);

    root->left->left = new Node(4);

    root->left->right = new Node(5);

    root->right->right = new Node(8);

    root->right->right->left = new Node(6);

    root->right->right->right = new Node(7);

    cout << "Maximum width is " << maxWidth(root) << endl;

    return 0;

}

Java

import java.util.LinkedList;

import java.util.Queue;

public class maxwidthusingqueue

{

    static class node

    {

        int data;

        node left, right;

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

    }

    static int maxwidth(node root)

    {

        if (root == null)

            return 0;

        int maxwidth = 0;

        Queue<node> q = new LinkedList<>();

        q.add(root);

        while (!q.isEmpty())

        {

            int count = q.size();

            maxwidth = Math.max(maxwidth, count);

            while (count-- > 0) {

                node temp = q.remove();

                if (temp.left != null)

                {

                    q.add(temp.left);

                }

                if (temp.right != null)

                {

                    q.add(temp.right);

                }

            }

        }

        return maxwidth;

    }

    public static void main(String[] args)

    {

        node root = new node(1);

        root.left = new node(2);

        root.right = new node(3);

        root.left.left = new node(4);

        root.left.right = new node(5);

        root.right.right = new node(8);

        root.right.right.left = new node(6);

        root.right.right.right = new node(7);

        System.out.println("Maximum width = "

                           + maxwidth(root));

    }

}

Python3

from _collections import deque

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def getMaxWidth(root):

    if root is None:

        return 0

    q = deque()

    maxWidth = 0

    q.append(root)

    while q:

        count = len(q)

        maxWidth = max(count, maxWidth)

        while (count is not 0):

            count = count-1

            temp = q.popleft()

            if temp.left is not None:

                q.append(temp.left)

            if temp.right is not None:

                q.append(temp.right)

    return maxWidth

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

root.right.right.left = Node(6)

root.right.right.right = Node(7)

print ("Maximum width is %d" % (getMaxWidth(root)))

C#

using System;

using System.Collections.Generic;

public class maxwidthusingqueue

{

    public class node

    {

        public int data;

        public node left, right;

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

    }

    static int maxwidth(node root)

    {

        if (root == null)

            return 0;

        int maxwidth = 0;

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

        q.Enqueue(root);

        while (q.Count != 0)

        {

            int count = q.Count;

            maxwidth = Math.Max(maxwidth, count);

            while (count-- > 0) {

                node temp = q.Dequeue();

                if (temp.left != null)

                {

                    q.Enqueue(temp.left);

                }

                if (temp.right != null)

                {

                    q.Enqueue(temp.right);

                }

            }

        }

        return maxwidth;

    }

    public static void Main(String[] args)

    {

        node root = new node(1);

        root.left = new node(2);

        root.right = new node(3);

        root.left.left = new node(4);

        root.left.right = new node(5);

        root.right.right = new node(8);

        root.right.right.left = new node(6);

        root.right.right.right = new node(7);

        Console.WriteLine("Maximum width = "

                          + maxwidth(root));

    }

}

Javascript

<script>

    class node

    {

        constructor(data) {

           this.left = null;

           this.right = null;

           this.data = data;

        }

    }

    function maxwidth(root)

    {

        if (root == null)

            return 0;

        let maxwidth = 0;

        let q = [];

        q.push(root);

        while (q.length > 0)

        {

            let count = q.length;

            maxwidth = Math.max(maxwidth, count);

            while (count-- > 0) {

                let temp = q.shift();

                if (temp.left != null)

                {

                    q.push(temp.left);

                }

                if (temp.right != null)

                {

                    q.push(temp.right);

                }

            }

        }

        return maxwidth;

    }

    let root = new node(1);

    root.left = new node(2);

    root.right = new node(3);

    root.left.left = new node(4);

    root.left.right = new node(5);

    root.right.right = new node(8);

    root.right.right.left = new node(6);

    root.right.right.right = new node(7);

    document.write("Maximum width is "

                       + maxwidth(root));

</script>

Time Complexity: O(N) where N is the total number of nodes in the tree. Every node of the tree is processed once and hence the complexity is O(N).
Auxiliary Space: O(w) where w is the maximum width of the tree. 

Maximum width Using Preorder Traversal:

The idea behind this approach is to find the level of a node and increment the count of nodes for that level. The number of nodes present at a certain level is the width of that level.

For traversal we can here use the preorder traversal.

Follow the steps mentioned below to implement the approach:

  • Create a temporary array count[] of size equal to the height of the tree. 
  • Initialize all values in count[] as 0. 
  • Traverse the tree using preorder traversal and fill the entries in count[] so that 
    • The count[] array contains the count of nodes at each level of the Binary Tree.
  • The level with the maximum number of nodes has the maximum width.
  • Return the value of that level. 

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

class node {

public:

    int data;

    node* left;

    node* right;

    node(int d)

    {

        this->data = d;

        this->left = this->right = NULL;

    }

};

int height(node* node);

int getMax(int arr[], int n);

void getMaxWidthRecur(node* root, int count[], int level);

int getMaxWidth(node* root)

{

    int width;

    int h = height(root);

    int* count = new int[h];

    int level = 0;

    getMaxWidthRecur(root, count, level);

    return getMax(count, h);

}

void getMaxWidthRecur(node* root,

                      int count[], int level)

{

    if (root) {

        count[level]++;

        getMaxWidthRecur(root->left, count, level + 1);

        getMaxWidthRecur(root->right, count, level + 1);

    }

}

int height(node* node)

{

    if (node == NULL)

        return 0;

    else {

        int lHeight = height(node->left);

        int rHeight = height(node->right);

        return (lHeight > rHeight) ? (lHeight + 1)

                                   : (rHeight + 1);

    }

}

int getMax(int arr[], int n)

{

    int max = arr[0];

    int i;

    for (i = 0; i < n; i++) {

        if (arr[i] > max)

            max = arr[i];

    }

    return max;

}

int main()

{

    node* root = new node(1);

    root->left = new node(2);

    root->right = new node(3);

    root->left->left = new node(4);

    root->left->right = new node(5);

    root->right->right = new node(8);

    root->right->right->left = new node(6);

    root->right->right->right = new node(7);

    cout << "Maximum width is " << getMaxWidth(root)

         << endl;

    return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

struct node {

    int data;

    struct node* left;

    struct node* right;

};

int height(struct node* node);

struct node* newNode(int data);

int getMax(int arr[], int n);

void getMaxWidthRecur(struct node* root, int count[],

                      int level);

int getMaxWidth(struct node* root)

{

    int width;

    int h = height(root);

    int* count = (int*)calloc(sizeof(int), h);

    int level = 0;

    getMaxWidthRecur(root, count, level);

    return getMax(count, h);

}

void getMaxWidthRecur(struct node* root, int count[],

                      int level)

{

    if (root) {

        count[level]++;

        getMaxWidthRecur(root->left, count, level + 1);

        getMaxWidthRecur(root->right, count, level + 1);

    }

}

int height(struct node* node)

{

    if (node == NULL)

        return 0;

    else {

        int lHeight = height(node->left);

        int rHeight = height(node->right);

        return (lHeight > rHeight) ? (lHeight + 1)

                                   : (rHeight + 1);

    }

}

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 getMax(int arr[], int n)

{

    int max = arr[0];

    int i;

    for (i = 0; i < n; i++) {

        if (arr[i] > max)

            max = arr[i];

    }

    return max;

}

int main()

{

    struct node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

    root->right->right = newNode(8);

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

    root->right->right->right = newNode(7);

    printf("Maximum width is %d n", getMaxWidth(root));

    getchar();

    return 0;

}

Java

class Node {

    int data;

    Node left, right;

    Node(int item)

    {

        data = item;

        left = right = null;

    }

}

class BinaryTree {

    Node root;

    int getMaxWidth(Node node)

    {

        int width;

        int h = height(node);

        int count[] = new int[10];

        int level = 0;

        getMaxWidthRecur(node, count, level);

        return getMax(count, h);

    }

    void getMaxWidthRecur(Node node, int count[], int level)

    {

        if (node != null) {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

    int height(Node node)

    {

        if (node == null)

            return 0;

        else {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1)

                                       : (rHeight + 1);

        }

    }

    int getMax(int arr[], int n)

    {

        int max = arr[0];

        int i;

        for (i = 0; i < n; i++) {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

    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);

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

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

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

        System.out.println("Maximum width is "

                           + tree.getMaxWidth(tree.root));

    }

}

Python3

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def getMaxWidth(root):

    h = height(root)

    count = [0] * h

    level = 0

    getMaxWidthRecur(root, count, level)

    return getMax(count, h)

def getMaxWidthRecur(root, count, level):

    if root is not None:

        count[level] += 1

        getMaxWidthRecur(root.left, count, level+1)

        getMaxWidthRecur(root.right, count, level+1)

def height(node):

    if node is None:

        return 0

    else:

        lHeight = height(node.left)

        rHeight = height(node.right)

        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)

def getMax(count, n):

    max = count[0]

    for i in range(1, n):

        if (count[i] > max):

            max = count[i]

    return max

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

root.right.right.left = Node(6)

root.right.right.right = Node(7)

print ("Maximum width is %d" % (getMaxWidth(root)))

C#

using System;

public class Node

{

    public int data;

    public Node left, right;

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

public class BinaryTree

{

    Node root;

    int getMaxWidth(Node node)

    {

        int width;

        int h = height(node);

        int[] count = new int[10];

        int level = 0;

        getMaxWidthRecur(node, count, level);

        return getMax(count, h);

    }

    void getMaxWidthRecur(Node node, int[] count, int level)

    {

        if (node != null)

        {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

    int height(Node node)

    {

        if (node == null)

            return 0;

        else

        {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1)

                                       : (rHeight + 1);

        }

    }

    int getMax(int[] arr, int n)

    {

        int max = arr[0];

        int i;

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

    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);

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

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

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

        Console.WriteLine("Maximum width is "

                          + tree.getMaxWidth(tree.root));

    }

}

Javascript

<script>

class Node {

    constructor(val) {

        this.data = val;

        this.left = null;

        this.right = null;

    }

}

var root;

    function getMaxWidth(node)

    {

        var width;

        var h = height(node);

        var count = Array(10).fill(0);

        var level = 0;

        getMaxWidthRecur(node, count, level);

        return getMax(count, h);

    }

    function getMaxWidthRecur(node , count , level)

    {

        if (node != null) {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

    function height(node)

    {

        if (node == null)

            return 0;

        else {

            var lHeight = height(node.left);

            var rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1)

                                       : (rHeight + 1);

        }

    }

    function getMax(arr , n)

    {

        var max = arr[0];

        var i;

        for (i = 0; i < n; i++) {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

        root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

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

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

        root.right.right = new Node(8);

        root.right.right.left = new Node(6);

        root.right.right.right = new Node(7);

        document.write("Maximum width is "

                           + getMaxWidth(root));

</script>

Time Complexity: O(N)
Auxiliary Space: O(h) where h is the height of the tree.

Thanks to Raja and jagdish for suggesting this method.
Please write comments if you find the above code/algorithm incorrect, or find better ways to solve the same problem.

Last Updated :
30 Dec, 2022

Like Article

Save Article

Источник

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

Например, максимальное количество узлов на любом уровне бинарного дерева ниже равно 4.

 
Maximum width of Binary Tree

Потренируйтесь в этой проблеме

1. Итеративный подход

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

Это показано ниже на C++, Java и Python:

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

#include <iostream>

#include <list>

using namespace std;

// Структура данных для хранения узла бинарного дерева

struct Node

{

    int key;

    Node *left, *right;

    Node(int key)

    {

        this->key = key;

        this->left = this->right = nullptr;

    }

};

// Функция для нахождения максимальной ширины бинарного дерева с использованием порядка уровней

// обход заданного бинарного дерева

void findMaxWidth(Node* root)

{

    // возвращаем, если дерево пусто

    if (root == nullptr) {

        return;

    }

    // создаем пустую queue и ставим в queue корневой узел

    list<Node*> queue;

    queue.push_back(root);

    // указатель для хранения текущего узла

    Node* curr = nullptr;

    // сохраняет максимальную ширину

    int max = 0;

    // цикл до тех пор, пока queue не станет пустой

    while (!queue.empty())

    {

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

        // Это равно ширине текущего уровня.

        int width = queue.size();

        // обновить максимальную ширину, если общее количество узлов на текущем уровне

        // больше, чем максимальная ширина, найденная до сих пор

        if (max < width) {

            max = width;

        }

        // обрабатываем каждый узел текущего уровня и ставим их в queue

        // непустые левый и правый потомки

        while (width—)

        {

            curr = queue.front();

            queue.pop_front();

            if (curr->left) {

                queue.push_back(curr->left);

            }

            if (curr->right) {

                queue.push_back(curr->right);

            }

        }

    }

    cout << “The Maximum width is “ << max;

}

int main()

{

    Node* root = new Node(15);

    root->left = new Node(10);

    root->right = new Node(20);

    root->left->left = new Node(8);

    root->left->right = new Node(12);

    root->right->left = new Node(16);

    root->right->right = new Node(25);

    findMaxWidth(root);

    return 0;

}

Скачать  Выполнить код

результат:

The maximum width is 4

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

import java.util.ArrayDeque;

import java.util.Queue;

// Класс для хранения узла бинарного дерева

class Node

{

    int key;

    Node left = null, right = null;

    Node(int key) {

        this.key = key;

    }

}

class Main

{

    // Функция для нахождения максимальной ширины бинарного дерева с использованием порядка уровней

    // обход заданного бинарного дерева

    public static void findMaxWidth(Node root)

    {

        // возвращаем, если дерево пусто

        if (root == null) {

            return;

        }

        // создаем пустую queue и ставим в queue корневой узел

        Queue<Node> queue = new ArrayDeque<>();

        queue.add(root);

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

        Node curr = null;

        // сохраняет максимальную ширину

        int max = 0;

        // цикл до тех пор, пока queue не станет пустой

        while (!queue.isEmpty())

        {

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

            // Это равно ширине текущего уровня.

            int width = queue.size();

            // обновить максимальную ширину, если общее количество узлов на текущем уровне

            // больше, чем максимальная ширина, найденная до сих пор

            if (max < width) {

                max = width;

            }

            // обрабатываем каждый узел текущего уровня и ставим их в queue

            // непустые левый и правый потомки

            while (width— > 0)

            {

                curr = queue.poll();

                if (curr.left != null) {

                    queue.add(curr.left);

                }

                if (curr.right != null) {

                    queue.add(curr.right);

                }

            }

        }

        System.out.println(“The maximum width is “ + max);

    }

    public static void main(String[] args)

    {

        Node root = new Node(15);

        root.left = new Node(10);

        root.right = new Node(20);

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

        root.left.right = new Node(12);

        root.right.left = new Node(16);

        root.right.right = new Node(25);

        findMaxWidth(root);

    }

}

Скачать  Выполнить код

результат:

The maximum width is 4

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

from collections import deque

# Класс для хранения узла бинарного дерева.

class Node:

    def __init__(self, key=None, left=None, right=None):

        self.key = key

        self.left = left

        self.right = right

# Функция для нахождения максимальной ширины бинарного дерева с использованием порядка уровней

# обход заданного бинарного дерева

def findMaxWidth(root):

    # возвращается, если дерево пусто

    if not root:

        return

    # создает пустую queue и ставит в queue корневой узел

    queue = deque()

    queue.append(root)

    # хранит максимальную ширину

    max = 0

    # Цикл # до тех пор, пока queue не станет пустой

    while queue:

        # вычисляет общее количество узлов на текущем уровне.

        # Равно ширине текущего уровня.

        width = len(queue)

        # обновляет максимальную ширину, если общее количество узлов на текущем уровне

        # больше, чем максимальная ширина, найденная до сих пор

        if max < width:

            max = width

        # обрабатывает каждый узел текущего уровня и ставит их в queue.

        # непустые левый и правый потомки

        while width > 0:

            width = width – 1

            curr = queue.popleft()

            if curr.left:

                queue.append(curr.left)

            if curr.right:

                queue.append(curr.right)

    print(‘The maximum width is’, max)

if __name__ == ‘__main__’:

    root = Node(15)

    root.left = Node(10)

    root.right = Node(20)

    root.left.left = Node(8)

    root.left.right = Node(12)

    root.right.left = Node(16)

    root.right.right = Node(25)

    findMaxWidth(root)

Скачать  Выполнить код

результат:

The maximum width is 4

Временная сложность приведенного выше решения равна O(n), куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(n) для queue.

2. Рекурсивный подход

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

Обратите внимание, что мы также можем пройти по дереву в в целях или же мода на заказ. Реализацию можно увидеть ниже на C++, Java и Python:

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

#include <iostream>

#include <unordered_map>

using namespace std;

// Структура данных для хранения узла бинарного дерева

struct Node

{

    int key;

    Node *left, *right;

    Node(int key)

    {

        this->key = key;

        this->left = this->right = nullptr;

    }

};

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

// на каждом уровне

void preorder(Node* root, int level, auto &map)

{

    // базовый случай: пустое дерево

    if (root == nullptr) {

        return;

    }

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

    map[level]++;

    // повторяем для левого и правого поддерева, повышая уровень на 1

    preorder(root->left, level + 1, map);

    preorder(root->right, level + 1, map);

}

// Рекурсивная функция для нахождения максимальной ширины бинарного дерева

void findMaxWidth(Node* root)

{

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

    if (root == nullptr) {

        return;

    }

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

    unordered_map<int, int> map;

    // обход дерева и заполнение карты

    preorder(root, 1, map);

    // сохраняет максимальную ширину

    int result = 0;

    // перебираем карту и обновляем максимальную ширину

    for (auto it: map) {

        result = max(result, it.second);

    }

    cout << “The Maximum width is “ << result;

}

int main()

{

    Node* root = new Node(15);

    root->left = new Node(10);

    root->right = new Node(20);

    root->left->left = new Node(8);

    root->left->right = new Node(12);

    root->right->left = new Node(16);

    root->right->right = new Node(25);

    findMaxWidth(root);

    return 0;

}

Скачать  Выполнить код

результат:

The maximum width is 4

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

import java.util.Comparator;

import java.util.HashMap;

import java.util.Map;

// Класс для хранения узла бинарного дерева

class Node

{

    int key;

    Node left = null, right = null;

    Node(int key) {

        this.key = key;

    }

}

class Main

{

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

    // на каждом уровне

    public static void preorder(Node root, int level, Map<Integer, Integer> map)

    {

        // базовый случай: пустое дерево

        if (root == null) {

            return;

        }

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

        map.put(level, map.getOrDefault(level, 0) + 1);

        // повторяем для левого и правого поддерева, повышая уровень на 1

        preorder(root.left, level + 1, map);

        preorder(root.right, level + 1, map);

    }

    // Рекурсивная функция для нахождения максимальной ширины бинарного дерева

    public static void findMaxWidth(Node root)

    {

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

        if (root == null) {

            return;

        }

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

        Map<Integer, Integer> map = new HashMap<>();

        // обход дерева и заполнение карты

        preorder(root, 1, map);

        // перебираем карту и находим максимальную ширину

        int maxWidth = map.values().stream().max(Comparator.naturalOrder()).get();

        System.out.println(“The maximum width is “ + maxWidth);

    }

    public static void main(String[] args)

    {

        Node root = new Node(15);

        root.left = new Node(10);

        root.right = new Node(20);

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

        root.left.right = new Node(12);

        root.right.left = new Node(16);

        root.right.right = new Node(25);

        findMaxWidth(root);

    }

}

Скачать  Выполнить код

результат:

The maximum width is 4

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

# Класс для хранения узла бинарного дерева.

class Node:

    def __init__(self, key=None, left=None, right=None):

        self.key = key

        self.left = left

        self.right = right

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

# на каждом уровне

def preorder(root, level, dict):

    # Базовый случай: пустое дерево

    if not root:

        return

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

    dict[level] = dict.get(level, 0) + 1

    # повторяется для левого и правого поддерева, повышая уровень на 1

    preorder(root.left, level + 1, dict)

    preorder(root.right, level + 1, dict)

# Рекурсивная функция для нахождения максимальной ширины бинарного дерева

def findMaxWidth(root):

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

    if not root:

        return 0

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

    dict = {}

    # пройтись по дереву и заполнить словарь

    preorder(root, 1, dict)

    # перебирает словарь и находит максимальную ширину

    print(‘The maximum width is’, max(dict.values()))

if __name__ == ‘__main__’:

    root = Node(15)

    root.left = Node(10)

    root.right = Node(20)

    root.left.left = Node(8)

    root.left.right = Node(12)

    root.right.left = Node(16)

    root.right.right = Node(25)

    findMaxWidth(root)

Скачать  Выполнить код

результат:

The maximum width is 4

Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n размер бинарного дерева.

Источник

Название Описание:
Для двоичного дерева напишите функцию, чтобы получить максимальную ширину дерева. Ширина дерева – это максимальная ширина во всех слоях. Это двоичное дерево имеет ту же структуру, что и полное двоичное дерево, но некоторые узлы пусты.
Ширина каждого слоя определяется как длина между двумя конечными точками (крайний левый и крайний правый непустые узлы слоя, а также нулевые узлы между двумя концами также включаются в длину. ).
Пример 1:

Пример 3:

Идеи решения проблем:
Если нужно найти максимальную ширину каждого непустого узла в дереве, это очень просто, но здесь нам нужно подсчитать пустые узлы в середине, чтобы мы могли ‘ t используйте обход последовательности слоев, чтобы найти его. Конкретная проблема решена Идея заключается в следующем:
  Предполагая, что полное двоичное дерево представлено как последовательность массива, а позиция корневого узла равна 1, тогда индексы любых левых и правых дочерних узлов узла i равны 2 * i и 2 * i + 1. Используйте вектор, чтобы сохранить левую конечную точку каждого слоя. Легко узнать, что элементов вектора столько же, сколько и в двоичном дереве. Затем вы можете записать индекс каждого узла и его уровень в процессе dfs, если level> vector.size () Это означает, что текущий узел является крайним левым узлом нового слоя, добавьте его к вектору, в противном случае текущий узел не является крайним левым узлом определенного слоя, мы должны судить индекс текущего узла минус крайний левый узел соответствующего слоя в векторе. Будет ли ширина индекса узла больше максимальной ширины и обновить

Код:

class Solution {
public:
    unsigned int maxWidth = 0;
    
    int widthOfBinaryTree(TreeNode* root) {
        vector<unsigned int> left;
        dfs(root, 1, 1, left);
        return maxWidth;
    }

private:
    void dfs(TreeNode* root, unsigned int level, unsigned int index, vector<unsigned int>& left)
    {
        if (root == nullptr)
            return;
        
        if (level > left.size())    // Здесь должен быть крайний левый непустой узел
            left.push_back(index);
        
        maxWidth = max(maxWidth, index - left[level-1] + 1);
        
        dfs(root->left, level+1, index*2, left);
        dfs(root->right, level+1, index*2+1, left);
    }
};
Источник
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
 
#define rantakt 40
#define maxkeys 100
 
void shakesrt(int* a, int n) //procedure shakersort;
{
int j,k,l,r, x;
    l = 1; r = k = n-1;
   while( l <= r )
   {
   for( j = r; j >= l; j-- )
    if ( a[j-1] > a[j] )
   {
   x = a[j-1]; a[j-1] = a[j];
    a[j] = x; k = j;
    }
  l = k+1;
   for( j = l; j <= r; j++ )
    if( a[j-1] > a[j] )
  {
    x = a[j-1]; a[j-1] = a[j];
    a[j] = x; k = j;
    }
  r = k-1;
}
}
 
 
void Random_Shuffle (int* a, int n) // перемешивание
{
  int x1, x2, buffer;
  for (int i=0; i<rantakt; i++) {
      x1=rand()%n;
      x2=rand()%n; // случайные индексы
         buffer=a[x1];
         a[x1]=a[x2];
         a[x2]=buffer; // меняем местами
   }
 
  }
 
 
 
  int BinSearch (int* a, int n, int key) {
     int n0 = 0;
     for (;;) {
                int m = ( n + n0 )/2;
               if ( key < a[m] ) n=m-1;
               else if ( key > a[m] ) n0=m+1;
               else return m; // если найден
 
               if ( n0 > n ) return -1; // если не найден
  }
  }
 
 
 
  bool isnumber (const char* num) { // это число?
    while (*num) {
      if (!((*num>='0' && *num<='9') || *num=='-')) return false;
         num++;
      }
 
      return true;
  }
 
 
 
 
int main()
{
int keys[maxkeys], key;
char text[maxkeys][256];
int p;
 int n=0;
  srand (unsigned(NULL));
    FILE* fkeys = fopen ("keys.txt", "r+");
    FILE* ftext = fopen ("stih.txt", "r+");
    FILE* fnewtext = fopen ("newstih.txt", "w+"); // после сортировки записываем
    if (!fkeys || !ftext) {
       fprintf (stderr, "files not opened");
       getch();
       return -1;
    }
 
     while (!feof(fkeys)) {
       fscanf(fkeys, "%d", &keys[n]) ; // читаем ключи
       n++;
       }
 
       for (int i=0; i<n; i++)
         fgets (text[i], 256, ftext); // читаем строки
 
          puts ("Poem in the beginning:n");
 
       for (int i=0; i<n; i++)
         printf(text[keys[i]]);
 
 
       Random_Shuffle (keys, n); // мешаем ключи
 
         puts ("nnnPoem after Shuffling:n");
         for (int i=0; i<n; i++)
         printf(text[keys[i]]);
 
         printf("nnKeys after shuffle:n");
          for (int i=0; i<n; i++)
          printf("%dt", keys[i]);
 
          shakesrt (keys, n); // сортируем ключи
 
           printf("nKeys after sorting:n");
          for (int i=0; i<n; i++) {
          printf("%dt", keys[i]);
          fputs (text[keys[i]], fnewtext); // пишем в файл
          }
 
          while (1) {
          char number[6];
          printf ("nInsert key for binary search (-1 for exit): ");
          scanf("%s", &number);
 
           if (isnumber (number)) {
            key=atoi (number); // перевод строки в число
 
           if (key==-1) break;
 
          p=BinSearch (keys, n, key); // результат поиска
 
          if (p==-1) printf("Key Not found");
          else printf ("%s", text[p]); // вывод строки по ключу
          }
           else printf ("Incorrect key");
          }
 
          fclose(fkeys);
          fclose(ftext);
          fclose (fnewtext);
          return 0;
 
 
}
Источник

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

Давайте рассмотрим приведенное ниже дерево примеров.

         1
        /  
       2    3
     /       
    4    5     8 
              /  
             6    7

Для приведенного выше дерева,
ширина уровня 1 равна 1,
ширина уровня 2 равна 2,
ширина уровня 3 — 3
Ширина уровня 4 равна 2.

Таким образом, максимальная ширина дерева составляет 3.

Метод 1 (Использование уровня обхода порядка)
Этот метод в основном включает две функции. Одним из них является подсчет узлов на заданном уровне (getWidth), а другим — получение максимальной ширины дерева (getMaxWidth). getMaxWidth () использует getWidth (), чтобы получить ширину всех уровней, начиная с корня.

/*Function to print level order traversal of tree*/
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
  width =   getWidth(tree, i);
  if(width > maxWdth) 
      maxWdth  = width
return maxWidth

/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;  
else if level greater than 1, then
    return getWidth(tree->left, level-1) + 
    getWidth(tree->right, level-1);

C ++

#include <bits/stdc++.h>

using namespace std;

class node 

{ 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

int getWidth(node* root, int level); 

int height(node* node); 

node* newNode(int data); 

int getMaxWidth(node* root) 

{ 

    int maxWidth = 0; 

    int width; 

    int h = height(root); 

    int i; 

    for(i = 1; i <= h; i++) 

    { 

        width = getWidth(root, i); 

        if(width > maxWidth) 

        maxWidth = width; 

    } 

    return maxWidth; 

} 

int getWidth(node* root, int level) 

{ 

    if(root == NULL) 

        return 0; 

    if(level == 1) 

        return 1; 

    else if (level > 1) 

        return getWidth(root->left, level - 1) + 

                getWidth(root->right, level - 1); 

} 

int height(node* node) 

{ 

    if (node == NULL) 

        return 0; 

    else

    { 

        int lHeight = height(node->left); 

        int rHeight = height(node->right); 

        return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1); 

    } 

} 

node* newNode(int data) 

{ 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    return(Node); 

} 

int main() 

{ 

    node *root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

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

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

    root->right->right = newNode(8); 

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

    root->right->right->right = newNode(7);     

    cout<<"Maximum width is "<< getMaxWidth(root)<<endl; 

    return 0; 

} 

С

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

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

int getWidth(struct node* root, int level);

int height(struct node* node);

struct node* newNode(int data);

int getMaxWidth(struct node* root)

{

  int maxWidth = 0;   

  int width;

  int h = height(root);

  int i;

  for(i=1; i<=h; i++)

  {

    width = getWidth(root, i);

    if(width > maxWidth)

      maxWidth = width;

  }     

  return maxWidth;

}

int getWidth(struct node* root, int level)

{

  if(root == NULL)

    return 0;

  if(level == 1)

    return 1;

  else if (level > 1)

    return getWidth(root->left, level-1) + 

             getWidth(root->right, level-1);

}

int height(struct node* node)

{

   if (node==NULL)

     return 0;

   else

   {

     int lHeight = height(node->left);

     int rHeight = height(node->right);

     return (lHeight > rHeight)? (lHeight+1): (rHeight+1);

   }

}

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()

{

  struct node *root = newNode(1);

  root->left        = newNode(2);

  root->right       = newNode(3);

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

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

  root->right->right = newNode(8);    

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

  root->right->right->right  = newNode(7);      

  printf("Maximum width is %d n", getMaxWidth(root));  

  getchar();

  return 0;

}

Джава

class Node 

{

    int data;

    Node left, right;

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

class BinaryTree 

{

    Node root;

    int getMaxWidth(Node node) 

    {

        int maxWidth = 0;

        int width;

        int h = height(node);

        int i;

        for (i = 1; i <= h; i++) 

        {

            width = getWidth(node, i);

            if (width > maxWidth)

                maxWidth = width;

        }

        return maxWidth;

    }

    int getWidth(Node node, int level) 

    {

        if (node == null)

            return 0;

        if (level == 1)

            return 1;

        else if (level > 1)

            return getWidth(node.left, level - 1)

                    + getWidth(node.right, level - 1);

        return 0;

    }

    int height(Node node) 

    {

        if (node == null)

            return 0;

        else

        {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);

        }

    }

    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);

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

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

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

        System.out.println("Maximum width is " + tree.getMaxWidth(tree.root));

    }

}

питон

class Node:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

def getMaxWidth(root):

    maxWidth = 0

    h = height(root)

    for i in range(1,h+1):

        width = getWidth(root, i)

        if (width > maxWidth):

            maxWidth = width

    return maxWidth

def getWidth(root,level):

    if root is None:

        return 0

    if level == 1:

        return 1

    elif level > 1:

        return (getWidth(root.left,level-1) + 

                getWidth(root.right,level-1))

def height(node):

    if node is None:

        return 0

    else:

        lHeight = height(node.left)

        rHeight = height(node.right)

        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

root.right.right.left = Node(6)

root.right.right.right = Node(7) 

print "Maximum width is %d" %(getMaxWidth(root))

C #

using System;

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 int getMaxWidth(Node node)

    {

        int maxWidth = 0;

        int width;

        int h = height(node);

        int i;

        for (i = 1; i <= h; i++)

        {

            width = getWidth(node, i);

            if (width > maxWidth)

            {

                maxWidth = width;

            }

        }

        return maxWidth;

    }

    public virtual int getWidth(Node node, int level)

    {

        if (node == null)

        {

            return 0;

        }

        if (level == 1)

        {

            return 1;

        }

        else if (level > 1)

        {

            return getWidth(node.left, level - 1) 

                  + getWidth(node.right, level - 1);

        }

        return 0;

    }

    public virtual int height(Node node)

    {

        if (node == null)

        {

            return 0;

        }

        else

        {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);

        }

    }

    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);

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

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

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

        Console.WriteLine("Maximum width is " + tree.getMaxWidth(tree.root));

    }

}

Выход:

Maximum width is 3

Сложность времени: O (n ^ 2) в худшем случае.

Мы можем использовать основанный на очереди обход порядка для оптимизации временной сложности этого метода. Обход порядка очереди на основе очередей займет в худшем случае время O (n). Благодаря Nitish , DivyaC и tech.login.id2 для предлагая эту оптимизацию. Смотрите их комментарии для реализации с использованием обхода на основе очереди.

Метод 2 (Использование уровня обхода порядка с очередью)
В этом методе мы сохраняем все дочерние узлы на текущем уровне в очереди, а затем подсчитываем общее количество узлов после завершения обхода порядка уровня для определенного уровня. Поскольку очередь теперь содержит все узлы следующего уровня, мы можем легко узнать общее количество узлов на следующем уровне, найдя размер очереди. Затем мы следуем той же процедуре для последовательных уровней. Мы храним и обновляем максимальное количество найденных узлов на каждом уровне.

C ++

#include<bits/stdc++.h>

using namespace std ;

struct Node

{

    int data ;

    struct Node * left ;

    struct Node * right ;

};

int maxWidth(struct Node * root)

{

    if (root == NULL)

        return 0;

    int result = 0;

    queue<Node*> q;

    q.push(root);

    while (!q.empty())

    {

        int count = q.size() ;

        result = max(count, result);

        while (count--)

        {

            Node *temp = q.front();

            q.pop();

            if (temp->left != NULL)

                q.push(temp->left);

            if (temp->right != NULL)

                q.push(temp->right);

        }

    }

    return result;

}

struct Node * newNode(int data)

{

    struct Node * node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

int main()

{

    struct Node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(3);

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

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

    root->right->right = newNode(8);

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

    root->right->right->right  = newNode(7);

    cout << "Maximum width is "

         << maxWidth(root) << endl;

    return 0;

}

Джава

import java.util.LinkedList;

import java.util.Queue;

public class maxwidthusingqueue 

{

    static class node 

    {

        int data;

        node left, right;

        public node(int data) 

        {

            this.data = data;

        }

    }

    static int maxwidth(node root) 

    {

        if (root == null)

            return 0;

        int maxwidth = 0;

        Queue<node> q = new LinkedList<>();

        q.add(root);

        while (!q.isEmpty()) 

        {

            int count = q.size();

            maxwidth = Math.max(maxwidth, count);

            while (count-- > 0) 

            {

                node temp = q.remove();

                if (temp.left != null) 

                {

                    q.add(temp.left);

                }

                if (temp.right != null) 

                {

                    q.add(temp.right);

                }

            }

        }

        return maxwidth;

    }

    public static void main(String[] args) 

    {

        node root = new node(1);

        root.left = new node(2);

        root.right = new node(3);

        root.left.left = new node(4);

        root.left.right = new node(5);

        root.right.right = new node(8);

        root.right.right.left = new node(6);

        root.right.right.right = new node(7);

        System.out.println("Maximum width = " + maxwidth(root));

    }

}

питон

class Node:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

def getMaxWidth(root):

    if root is None:

        return 0

    q = []

    maxWidth = 0

    q.insert(0,root)

    while (q != []):

        count = len(q)

        maxWidth = max(count,maxWidth)

        while (count is not 0):

            count = count-1

            temp = q[-1]  

            q.pop() ;

            if temp.left is not None:

                q.insert(0,temp.left)

            if temp.right is not None:

                q.insert(0,temp.right)

    return maxWidth

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

root.right.right.left = Node(6)

root.right.right.right = Node(7) 

print "Maximum width is %d" %(getMaxWidth(root))

C #

using System;

using System.Collections.Generic; 

public class maxwidthusingqueue 

{ 

    public class node 

    { 

        public int data; 

        public node left, right; 

        public node(int data) 

        { 

            this.data = data; 

        } 

    } 

    static int maxwidth(node root) 

    { 

        if (root == null) 

            return 0; 

        int maxwidth = 0; 

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

        q.Enqueue(root); 

        while (q.Count!=0) 

        { 

            int count = q.Count; 

            maxwidth = Math.Max(maxwidth, count); 

            while (count-- > 0) 

            { 

                node temp = q.Dequeue(); 

                if (temp.left != null) 

                { 

                    q.Enqueue(temp.left); 

                } 

                if (temp.right != null) 

                { 

                    q.Enqueue(temp.right); 

                } 

            } 

        } 

        return maxwidth; 

    } 

    public static void Main(String[] args) 

    { 

        node root = new node(1); 

        root.left = new node(2); 

        root.right = new node(3); 

        root.left.left = new node(4); 

        root.left.right = new node(5); 

        root.right.right = new node(8); 

        root.right.right.left = new node(6); 

        root.right.right.right = new node(7); 

        Console.WriteLine("Maximum width = " + maxwidth(root)); 

    } 

} 

Выход:

Maximum width is 3

Метод 3 (с использованием обхода предзаказа)
В этом методе мы создаем временный массив count [] размером, равным высоте дерева. Мы инициализируем все значения в count как 0. Мы проходим по дереву с помощью обхода предварительного заказа и заполняем записи в count так, чтобы массив count содержал количество узлов на каждом уровне в Binary Tree.

C ++

#include <bits/stdc++.h>

using namespace std;

class node 

{ 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

int height(node* node); 

node* newNode(int data); 

int getMax(int arr[], int n); 

void getMaxWidthRecur(node *root, int count[], int level); 

int getMaxWidth(node* root) 

{ 

    int width; 

    int h = height(root); 

    int *count = new int[h];

    int level = 0; 

    getMaxWidthRecur(root, count, level); 

    return getMax(count, h); 

} 

void getMaxWidthRecur(node *root, int count[], int level) 

{ 

    if(root) 

    { 

        count[level]++; 

        getMaxWidthRecur(root->left, count, level + 1); 

        getMaxWidthRecur(root->right, count, level + 1); 

    } 

} 

int height(node* node) 

{ 

    if (node==NULL) 

        return 0; 

    else

    { 

        int lHeight = height(node->left); 

        int rHeight = height(node->right); 

        return (lHeight > rHeight)? (lHeight+1): (rHeight+1); 

    } 

} 

node* newNode(int data) 

{ 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    return(Node); 

} 

int getMax(int arr[], int n) 

{ 

    int max = arr[0]; 

    int i; 

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

    { 

        if (arr[i] > max) 

            max = arr[i]; 

    } 

    return max; 

} 

int main() 

{ 

    node *root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

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

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

    root->right->right = newNode(8); 

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

    root->right->right->right = newNode(7); 

    cout << "Maximum width is " << getMaxWidth(root) << endl; 

    return 0; 

} 

С

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

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

int height(struct node* node);

struct node* newNode(int data);

int getMax(int arr[], int n);

void getMaxWidthRecur(struct node *root, int count[], int level);

int getMaxWidth(struct node* root)

{

  int width;

  int h = height(root);

  int *count = (int *)calloc(sizeof(int), h);

  int level = 0;

  getMaxWidthRecur(root, count, level);

  return getMax(count, h);

}

void getMaxWidthRecur(struct node *root, int count[], int level)

{

  if(root)

  {

    count[level]++;

    getMaxWidthRecur(root->left, count, level+1);

    getMaxWidthRecur(root->right, count, level+1);

  }

}

int height(struct node* node)

{

   if (node==NULL)

     return 0;

   else

   {

     int lHeight = height(node->left);

     int rHeight = height(node->right);

     return (lHeight > rHeight)? (lHeight+1): (rHeight+1);

   }

}

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 getMax(int arr[], int n)

{

   int max = arr[0];

   int i;

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

   {

       if (arr[i] > max)

          max = arr[i];

   }

   return max;

}

int main()

{

  struct node *root = newNode(1);

  root->left        = newNode(2);

  root->right       = newNode(3);

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

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

  root->right->right = newNode(8);

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

  root->right->right->right  = newNode(7);

  printf("Maximum width is %d n", getMaxWidth(root));

  getchar();

  return 0;

}

Джава

class Node 

{

    int data;

    Node left, right;

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

class BinaryTree 

{

    Node root;

    int getMaxWidth(Node node) 

    {

        int width;

        int h = height(node);

        int count[] = new int[10];

        int level = 0;

        getMaxWidthRecur(node, count, level);

        return getMax(count, h);

    }

    void getMaxWidthRecur(Node node, int count[], int level) 

    {

        if (node != null) 

        {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

    int height(Node node) 

    {

        if (node == null) 

            return 0;

        else 

        {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);

        }

    }

    int getMax(int arr[], int n) 

    {

        int max = arr[0];

        int i;

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

    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);

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

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

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

        System.out.println("Maximum width is " + 

                           tree.getMaxWidth(tree.root));

    }

}

питон

class Node:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

def getMaxWidth(root):

    h = height(root)

    count = [0] * h

    level = 0

    getMaxWidthRecur(root, count, level)

    return getMax(count,h)

def getMaxWidthRecur(root, count, level):

    if root is not None:

        count[level] += 1

        getMaxWidthRecur(root.left, count, level+1)

        getMaxWidthRecur(root.right, count, level+1)

def height(node):

    if node is None:

        return 0

    else:

        lHeight = height(node.left)

        rHeight = height(node.right)

        return (lHeight+1) if (lHeight > rHeight) else (rHeight+1)

def getMax(count, n):

    max = count[0]

    for i in range (1,n):

        if (count[i] > max):

            max = count[i]

    return max

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(8)

root.right.right.left = Node(6)

root.right.right.right = Node(7) 

print "Maximum width is %d" %(getMaxWidth(root))

C #

using System;

public class Node 

{

    public int data;

    public Node left, right;

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

public class BinaryTree 

{

    Node root;

    int getMaxWidth(Node node) 

    {

        int width;

        int h = height(node);

        int []count = new int[10];

        int level = 0;

        getMaxWidthRecur(node, count, level);

        return getMax(count, h);

    }

    void getMaxWidthRecur(Node node, int []count, int level) 

    {

        if (node != null) 

        {

            count[level]++;

            getMaxWidthRecur(node.left, count, level + 1);

            getMaxWidthRecur(node.right, count, level + 1);

        }

    }

    int height(Node node) 

    {

        if (node == null) 

            return 0;

        else

        {

            int lHeight = height(node.left);

            int rHeight = height(node.right);

            return (lHeight > rHeight) ? 

                    (lHeight + 1) : (rHeight + 1);

        }

    }

    int getMax(int []arr, int n) 

    {

        int max = arr[0];

        int i;

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

    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);

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

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

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

        Console.WriteLine("Maximum width is " + 

                        tree.getMaxWidth(tree.root));

    }

}

Выход:

Maximum width is 3

Спасибо Радже и Джагдишу за предложение этого метода.

Сложность времени: O (n)

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

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

  • Вертикальная ширина бинарного дерева | Комплект 1
  • Вертикальная ширина бинарного дерева | Набор 2
  • Максимальная сумма поддерева в двоичном дереве, так что поддерево также является BST
  • Максимальная сумма пути в двоичном дереве
  • Максимальная спиральная сумма в двоичном дереве
  • Сумма узлов на максимальной глубине двоичного дерева
  • Максимальная сумма узлов в двоичном дереве, так что нет двух соседних
  • Найти максимальную сумму уровня в бинарном дереве
  • Сумма узлов на максимальной глубине двоичного дерева | Набор 2
  • Получить максимальный левый узел в двоичном дереве
  • Максимальная сумма родительских детей в двоичном дереве
  • Найти максимум (или минимум) в двоичном дереве
  • Найти максимум среди всех правильных узлов в двоичном дереве
  • Найти максимальную вертикальную сумму в двоичном дереве
  • Найти максимальную сумму уровня в двоичном дереве с помощью рекурсии

Максимальная ширина бинарного дерева

0.00 (0%) 0 votes

Источник

Добавить комментарий