Java在二叉树中查找最大距离的节点
在此程序中，我们需要找出在二叉树中最大距离的节点。二叉树。根据我们的方法，树的所有节点之间的所有距离将保持在可变距离内。通过使用变量MaxDistance可以保留具有最大值的距离。最初，MaxDistance初始化为distance的值。如果发现任何大于MaxDistance的值，请覆盖MaxDistance的值。
重复此过程，直到找到树的两个节点之间的最大可能距离。该过程的算法在下面给出。
算法
定义Node类，它具有三个属性，即: 左和右数据。在这里，左代表节点的左子节点，右代表节点的右子节点。
创建节点后，数据将传递到该节点的data属性，并且左右都将设置为null。
定义另一个具有两个属性root和treeArray的类。 Root 表示树的根节点，并将其初始化为null。 treeArray 将存储二叉树的数组表示形式。
nodesAtMaxDistance()将找出以最大距离出现的节点:
它将计算二叉树中所有节点之间的距离并将其存储在可变距离中。
MaxDistance跟踪节点之间的最大可能距离。如果maxDistance小于distance，则distance的值将存储在maxDistance中。清除数组以摆脱以前存储的值。距离最大的节点将存储在数组arr中。
如果在maxDistance处有一对以上的节点，则将它们存储在数组arr中。
a.computeSize()将计算树中存在的节点数。
b。 convertBTtoArray()将通过遍历二进制树并将元素添加到treeArray来将二叉树转换为其数组表示形式。
c。 getDistance()将计算给定节点到根的距离。
d。 LowestCommonAncestor()将找出节点n1和n2的最低公共祖先。
如果任何一个节点都等于根节点，则将root作为最小的共同祖先返回。
否则，在左子树和右子树中搜索节点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 )
