首页 > 代码库 > 编程之美---求二叉树中节点的最大距离

编程之美---求二叉树中节点的最大距离

2024-08-09 11:35:20   219人阅读

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

解法：用递归的方法

 1 // 数据结构定义 2 struct NODE 3 { 4     NODE* pLeft;        // 左子树 5     NODE* pRight;       // 右子树 6     int nMaxLeft;       // 左子树中的最长距离 7     int nMaxRight;      // 右子树中的最长距离 8     char chValue;       // 该节点的值 9 };10  11 int nMaxLen = 0;12  13 // 寻找树中最长的两段距离14 void FindMaxLen(NODE* pRoot)15 {16     // 遍历到叶子节点，返回17     if(pRoot == NULL)18     {19         return;20     }21  22     // 如果左子树为空，那么该节点的左边最长距离为023     if(pRoot -> pLeft == NULL)24     {25         pRoot -> nMaxLeft = 0; 26     }27  28     // 如果右子树为空，那么该节点的右边最长距离为029     if(pRoot -> pRight == NULL)30     {31         pRoot -> nMaxRight = 0;32     }33  34     // 如果左子树不为空，递归寻找左子树最长距离35     if(pRoot -> pLeft != NULL)36     {37         FindMaxLen(pRoot -> pLeft);38     }39  40     // 如果右子树不为空，递归寻找右子树最长距离41     if(pRoot -> pRight != NULL)42     {43         FindMaxLen(pRoot -> pRight);44     }45  46     // 计算左子树最长节点距离47     if(pRoot -> pLeft != NULL)48     {49         int nTempMax = 0;50         if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)51         {52             nTempMax = pRoot -> pLeft -> nMaxLeft;53         }54         else55         {56             nTempMax = pRoot -> pLeft -> nMaxRight;57         }58         pRoot -> nMaxLeft = nTempMax + 1;59     }60  61     // 计算右子树最长节点距离62     if(pRoot -> pRight != NULL)63     {64         int nTempMax = 0;65         if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)66         {67             nTempMax = pRoot -> pRight -> nMaxLeft;68         }69         else70         {71             nTempMax = pRoot -> pRight -> nMaxRight;72         }73         pRoot -> nMaxRight = nTempMax + 1;74     }75  76     // 更新最长距离77     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)78     {79         nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;80     }81 }

 

编程之美---求二叉树中节点的最大距离


联系
我们