查找二叉树中最大距离节点的 Java 程序

17 Mar 2025 | 5 分钟阅读

在这个程序中，我们需要找出二叉树中距离最远的节点。根据我们的方法，树中所有节点之间的距离将保存在变量 distance 中。最大距离将使用变量 MaxDistance 进行保存。最初，MaxDistance 用 distance 的值初始化。如果发现任何值大于 MaxDistance，则覆盖 MaxDistance 的值。

重复此过程，直到我们找到树中两个节点之间可能的最大距离。该过程的算法如下。

Java program to find the nodes which are at the maximum distance in a Binary Tree

算法

定义 Node 类，该类包含三个属性：data、left 和 right。这里，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，数据将传递到节点的 data 属性，left 和 right 都将设置为 null。
定义另一个具有两个属性 root 和 treeArray 的类。
- Root 表示树的根节点，并将其初始化为 null。
- treeArray 将存储二叉树的数组表示。
nodesAtMaxDistance() 将找出距离最远的节点

它将计算二叉树中所有节点之间的距离并将其存储在变量 distance 中。
MaxDistance 跟踪节点之间可能的最大距离。如果 maxDistance 小于 distance，则 distance 的值将存储在 maxDistance 中。清除数组以删除以前存储的值。距离最远的节点将存储在数组 arr 中。
如果有多对节点处于最大距离，则将它们存储在数组 arr 中。

a. calculateSize() 将计算树中存在的节点数。

b. convertBTtoArray() 将通过遍历树并将元素添加到 treeArray 将二叉树转换为其数组表示。

c. getDistance() 将计算给定节点与根的距离。

d. LowestCommonAncestor() 将找出节点 n1 和 n2 的最低公共祖先。

如果任何节点等于根节点，则返回根作为最低公共祖先。
否则，在左子树和右子树中搜索节点 n1 和 n2。
如果找到一个节点，使得 n1 是该节点的左子节点，n2 是该节点的右子节点，反之亦然。返回该节点作为最低公共祖先。

a. FindDistance() 将计算两个节点之间的距离。

首先，它计算每个节点与根节点的距离。
从这个根节点中减去 2 * 最低公共祖先的距离

程序

import java.util.ArrayList;

public class MaxDistance {

    //Represent a node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;

        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
            }
          }

    //Represent the root of binary tree
    public Node root;

    int[] treeArray;
    int index = 0;

    public MaxDistance(){
        root = null;
    }

    //calculateSize() will calculate size of tree
    public int calculateSize(Node node)
    {
        int size = 0;
        if (node == null)
         return 0;
        else {
            size = calculateSize (node.left) + calculateSize (node.right) + 1;
            return size;
        }
    }

    //convertBTtoArray() will convert binary tree to its array representation
    public void convertBTtoArray(Node node) {
        //Check whether tree is empty
        if(root == null){
            System.out.println("Tree is empty");
            return;
        }
        else {
            if(node.left != null)
                convertBTtoArray(node.left);
            //Adds nodes of binary tree to treeArray
            treeArray[index] = node.data;
            index++;
            if(node.right != null)
                convertBTtoArray(node.right);
            }
    }

    //getDistance() will find distance between root and a specific node
    public int getDistance(Node temp, int n1) {
        if (temp != null) {
            int x = 0;
            if ((temp.data == n1) || (x = getDistance(temp.left, n1)) > 0
                    || (x = getDistance(temp.right, n1)) > 0) {
                //x will store the count of number of edges between temp and node n1
                return x + 1;
            }
            return 0;
        }
        return 0;
    }

    //lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
    public Node lowestCommonAncestor(Node temp, int node1, int node2) {
        if (temp != null) {
            //If root is equal to either of node node1 or node2, return root
            if (temp.data == node1 || temp.data == node2) {
                return temp;
            }

            //Traverse through left and right subtree
            Node left = lowestCommonAncestor(temp.left, node1, node2);
            Node right = lowestCommonAncestor(temp.right, node1, node2);

            //If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
            //Then, return node temp  as lowest common ancestor
            if (left != null && right != null) {
                return temp;
            }

            //If nodes node1 and node2 are in left subtree
            if (left != null) {
                return left;
            }
            //If nodes node1 and node2 are in right subtree
            if (right != null) {
                return right;
            }
        }
        return null;
    }

    //findDistance() will find distance between two given nodes
    public int findDistance(int node1, int node2) {
        //Calculates distance of first node from root
        int d1 = getDistance(root, node1) - 1;
        //Calculates distance of second node from root
        int d2 = getDistance(root, node2) - 1;

        //Calculates lowest common ancestor of both the nodes
        Node ancestor = lowestCommonAncestor(root, node1, node2);

        //If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
        int d3 = getDistance(root, ancestor.data) - 1;
        return (d1 + d2) - 2 * d3;
    }

    //nodesAtMaxDistance() will display the nodes which are at maximum distance
    public void nodesAtMaxDistance(Node node) {
        int maxDistance = 0, distance = 0;
        ArrayList<Integer> arr = new ArrayList<>();

        //Initialize treeArray
        int treeSize = calculateSize(node);
        treeArray = new int[treeSize];

        //Convert binary tree to its array representation
        convertBTtoArray(node);

        //Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
        for(int i = 0; i < treeArray.length; i++) {
            for(int j = i; j < treeArray.length; j++) {
                distance = findDistance(treeArray[i], treeArray[j]);
                //If distance is greater than maxDistance then, maxDistance will hold the value of distance
                if(distance > maxDistance) {
                    maxDistance = distance;
                    arr.clear();
                    //Add nodes at position i and j to treeArray
                    arr.add(treeArray[i]);
                    arr.add(treeArray[j]);
                }
                //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
                else if(distance == maxDistance) {
                    arr.add(treeArray[i]);
                    arr.add(treeArray[j]);
                }
            }
        }
        //Display all pair of nodes which are at maximum distance
        System.out.println("Nodes which are at maximum distance: ");
        for(int i = 0; i < arr.size(); i = i + 2) {
            System.out.println("( " + arr.get(i) + "," + arr.get(i+1) + " )");
        }
    }

    public static void main(String[] args) {

        MaxDistance bt = new MaxDistance();
        //Add nodes to the binary tree
        bt.root = new Node(1);
        bt.root.left = new Node(2);
        bt.root.right = new Node(3);
        bt.root.left.left = new Node(4);
        bt.root.left.right = new Node(5);
        bt.root.right.left = new Node(6);
        bt.root.right.right = new Node(7);
        bt.root.right.right.right = new Node(8);
        bt.root.right.right.right.left = new Node(9);

        //Finds out all the pair of nodes which are at maximum distance
        bt.nodesAtMaxDistance(bt.root);
      }
}

输出

Nodes which are at maximum distance: 
( 4, 9 )
( 5, 9 )

下一个主题Java 程序

查找二叉树中最大距离节点的 Java 程序

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

查找二叉树中最大距离节点的 Java 程序

算法

程序

相关帖子

Java 中检查给定数组是否为镜像逆

Java 将小写字母转换为大写字母，反之亦然的程序

Java 查找二叉树中最大元素的程序

Java 中用链表表示的数字相加

查找数组中第二大数字的 Java 程序

如何在 Java 中将对象转换为字符串

如何在 Java 中将八进制转换为十进制

Java Program to Find Square Root of a Number Without sqrt Method

Java 在循环链表开头插入新节点的程序

Mystery Number in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器