你可以这样想：

a
    /   \
   b      c
  /  \   / \
 e    f g   h

现在，您要确定同一级别节点之间的水平距离。例如：f和g。下面是一个循序渐进的方法：
1.执行二叉树的层级顺序遍历，并将值存储在数组中。
1.这会产生一个数组，其中的元素作为节点值。
1.遍历数组元素。当遇到f（起始节点）时，将counter设置为0。
1.继续遍历数组并检查：
1.如果遇到g（结束节点），则停止遍历。
1.如果计数器已被设置，并且未遇到结束节点，则将计数器的值更新1。
1.最后，打印计数器的值。

Update：正如anand_v.singh所指出的，如果树的所有级别都没有被完全填充，那么它可能会产生错误的结果。

为了解决这个问题，需要确定一个名为tree_height的附加参数。假设树的高度为3，那么数组最多包含2tree_height-1个元素，所有元素都初始化为不等于任何树节点值的值。现在，您可以使用类似于二进制堆的数组表示法，将节点值放入数组中。然后按照上述步骤获得结果。

就内存而言，这可能不是最佳的解决方案。
因此，欢迎提出建议/改进。

• • 算法**-
• 使用广度优先搜索（级别顺序）方法遍历BT。
• 遍历时，将空格（不存在节点的位置）视为"-1"
• 在数组中插入BFS路径元素查找要查找的2个节点元素的索引。
• 使用索引计算距离。
• • 复杂性**-时间：时间复杂度O（N）时间复杂度O（N）
• • 假设**-BT中的每个节点都有唯一的值。

class Node {
  Node() {
    value = -1;
  }
  Node(int num) {
    value = num;
  }
  int value;
  Node left = null;
  Node right = null;
}

声明某些必需的DS

static Queue<Node> queue = new LinkedList<Node>();
static ArrayList<Integer> list = new ArrayList<Integer>();
static Set<Integer> set = new HashSet<Integer>();

然后三个函数

static void convertBTToArray() {
    if (set.isEmpty())
      return;
 
    Node node = queue.poll();
 
    if (node != null) {
      list.add(node.value);
 
      if (node.value != -1)
        set.remove(node.value);
 
      if (node.left != null) {
        queue.add(node.left);
        set.add(node.left.value);
      } else
        queue.add(new Node());
      if (node.right != null) {
        queue.add(node.right);
        set.add(node.right.value);
      } else
        queue.add(new Node());
 
      convertBTToArray();
 
    } else
      return;
  }
 
 
  static void init(Node root) {
    // traverse in BFS fashion (level order) and convert to Array.
    Node rootCopy = root;
    if (rootCopy != null) {
      queue.add(rootCopy);
      set.add(rootCopy.value);
      convertBTToArray();
    }
  }
 
    // get distance between start and end values.
  static int getHorizontalDistance(int startValue, int endValue) {
    int startIndex = -1, endIndex = -1;
    for (int i = 0; i < list.size(); i++) {
      if (startIndex == -1)
        startIndex = list.get(i) == startValue ? i : -1;
 
      if (list.get(i) == endValue) {
        endIndex = i;
        break;
      }
    }
 
    // check if both numbers are from same level else return -1
    if (Math.floor(Math.log(startIndex + 1) / Math.log(2)) >= 0
      && Math.floor(Math.log(endIndex + 1) / Math.log(2)) >= 0)
      return (endIndex - startIndex - 1);
    else
      return -1;
  }

最后主要方法

public static void main(String...s) {
    // create your tree and enter elements here

    // -1 indicates that distance cant be found and hence invalid input.
    System.out.println("Dist(7,1): "+getHorizontalDistance(7, 1));
    
  }

求'a'与'f'的水平距离（hd 1），即根和'd'与'f'的水平距离（hd2）。
取根的hd =0，然后用hd2-hd 1得到两个节点的水平距离B/w，hd 1在根的左边，为负，hd2在根的右边，为正。
计算节点水平距离的函数如下所示。

int HD(Node* root, Node* node, int hd=0){
    if(!root) return INT_MIN;
    if(root==node) return hd;
    return max(HD(root->left, node, hd-1), HD(root->right, node, hd+1));
}

现在

hd1 = HD(root, nodeA)
hd2 = HD(root, nodeD)

hd2-hd 1将给予4在您的情况下。

Here is the code:

/**
* 
* @author satish hawalppagol
*
*/


public class BinaryTreeTest
{
    public int findDistance(Node root, int n1, int n2) 
    {

    int leftNodeToRootNode = Pathlength(root, n1, "leftNodeToRootNode") - 2;
    int rightNodeToRootNode = Pathlength(root, n2,"rightNodeToRootNode") - 2;
    int lcaData = findLCA(root, n1, n2).data;   //LCA->Lowest Common Ancestor
    int lcaDistance = Pathlength(root, lcaData,"lcaDistance") - 1;
    return (leftNodeToRootNode + rightNodeToRootNode) - 2 * lcaDistance;

    }

    public int Pathlength(Node root, int n1,String callingFrom) 
    {

    if (root != null) 
    {

        int x = 0;

        if("rightNodeToRootNode" == callingFrom)
        {

            if(root.left ==null && root.right ==null)
            {
                //do nothing
            }
            else if(root.left ==null || root.right ==null)
            {
                System.out.println("counting the position where the node is not 
                present is : "   +   root.data);
            }
            if ((root.data == n1) || (x = Pathlength(root.left, 
               n1,"rightNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
               n1,"rightNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }
        if("rightNodeToRootNode" != callingFrom )
        {

            if ((root.data == n1) || (x = Pathlength(root.left, 
            n1,"leftNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
            n1,"leftNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }

        return 0;
    }
    return 0;
}

public Node findLCA(Node root, int n1, int n2) 
{

    if (root != null)
    {

        if (root.data == n1 || root.data == n2) 
        {
            return root;
        }
        Node left = findLCA(root.left, n1, n2);
        Node right = findLCA(root.right, n1, n2);

        if (left != null && right != null)
        {
            return root;
        }
        if (left != null) 
        {
            return left;
        }
        if (right != null)
        {
            return right;
        }
    }
    return null;
}

public static void main(String[] args) throws java.lang.Exception 
{

    Node root = new Node(5);
    root.left = new Node(2);
    root.right = new Node(3);
    /*root.left.right = new Node(12);*/
    root.left.left = new Node(7);
    root.left.left.left = new Node(9);
    /*root.left.left.right = new Node(17);*/

    root.right.right = new Node(1);
    /*root.right.right.left = new Node(4);*/
    root.right.right.right = new Node(6);

    BinaryTreeTest binaryTreeTest = new BinaryTreeTest();
    System.out.println("Distance between 9 and 6 is : " + 
    binaryTreeTest.findDistance(root,9, 6));
    }

}

class Node 
{
int data;
Node left;
Node right;

    public Node(int data) 
    {
    this.data = data;
    this.left = null;
    this.right = null;
    }
}

///////////input/////////   
//          5          //   
//        /    \       //   
//       2     3       //   
//      / \      \     //   
//     7          1    //   
//    /  \       /  \  // 
//   9               6 // 
///////////input/////////   

counting the position where the node is not present is : 2
counting the position where the node is not present is : 7
counting the position where the node is not present is : 3
counting the position where the node is not present is : 1
Distance between 9 and 6 is : 4