如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树相距最远的两个节点之间的距离。
分析: 对任意一个节点,以该节点为根,假设这个根有k个孩子节点,那么相距最远的两个节点U和V之间的路径与这个根节点的关系有两种情况。
1.若路径经过根Root,则U和V是属于不同的子树的,且它们都是该子树中到根节点最远的节点,否则跟它们的距离最远相矛盾。
2.若路径不经过Root,那它们一定同属于根的左子树或右子树,并且它们也是该子树中相距最远的两个顶点。
因此,问题就可以转化为在子树上的解,从而能够利用动态规划来解决。上代码:
#include <stdio.h>
#include <stdlib.h>
struct NODE{
NODE* pLeft;
NODE* pRight;
int nMaxLeft; //左子树中的最大深度
int nMaxRight; //右子树中的最大深度
char chValue; //该节点的值
};
int nMaxLen = 0;
void FindMaxLen(NODE* pRoot) {
if(pRoot == NULL) {
return;
}
if(pRoot->pLeft == NULL) {
pRoot->nMaxLeft = 0;
}else {
FindMaxLen(pRoot->pLeft);
int nTempMax = 0;
if(pRoot->pLeft->nMaxLeft > pRoot->pLeft->nMaxRight) {
nTempMax = pRoot->pLeft->nMaxLeft;
}else {
nTempMax = pRoot->pLeft->nMaxRight;
}
//加上到根节点的距离
pRoot->nMaxLeft = nTempMax + 1;
}
if(pRoot->pRight == NULL) {
pRoot->nMaxRight = 0;
}else {
FindMaxLen(pRoot->pRight);
int nTempMax = 0;
if(pRoot->pRight->nMaxLeft > pRoot->pRight->nMaxRight) {
nTempMax = pRoot->pRight->nMaxLeft;
}else {
nTempMax = pRoot->pRight->nMaxRight;
}
pRoot->nMaxRight = nTempMax + 1; //加上到根节点的距离
}
if(pRoot->nMaxLeft + pRoot->nMaxRight > nMaxLen) //最长距离经过root
nMaxLen = pRoot->nMaxLeft + pRoot->nMaxRight;
}
void createBinaryTree(NODE** pRoot) { //建二叉树
char c;
scanf("%c",&c);
if(c == '#') {
(*pRoot) = NULL;
}
else {
(*pRoot) = (struct NODE*) malloc(sizeof(struct NODE));
(*pRoot)->chValue = c;
createBinaryTree(&((*pRoot)->pLeft));
createBinaryTree(&((*pRoot)->pRight));
}
}
void printBinaryTree(NODE* pRoot) { //打印二叉树
if(pRoot == NULL)
return;
printf("%c",pRoot->chValue);
printBinaryTree(pRoot->pLeft);
printBinaryTree(pRoot->pRight);
}
int main() {
struct NODE* root = NULL;
createBinaryTree(&root);
printBinaryTree(root);
FindMaxLen(root);
printf("\nThe max length is: %d\n",nMaxLen);
return 0;
}
分享到:
相关推荐
在计算机科学中,二叉树是一种非常重要的数据结构,而求二叉树节点的最大距离是二叉树中一个经典的问题。问题的定义是这样的:在二叉树中,计算任意两个节点之间的最大路径长度,路径长度是指路径上的边数。解决这个...
java啊 二叉树建立,用递归与非递归的方法求结点之和
后序遍历是二叉树遍历的三种基本方法之一,顺序为:左子树 -> 右子树 -> 根节点。在解决这个问题时,我们可以通过后序遍历收集路径信息。首先,我们需要定义一个辅助函数,用于进行后序遍历,并在遍历过程中记录路径...
在探讨“求二叉树最大宽度”的数据结构问题时,我们深入分析了如何通过特定算法找到一棵二叉树中每一层节点的最大数量,这一过程涉及到了数据结构与算法设计的关键概念和技术。 ### 一、二叉树的概念 二叉树是一种...
在本实验中,学习者将通过实际编程练习来加深对二叉树这一数据结构的理解,并熟练掌握其基本操作。具体目标包括: 1. **熟悉二叉树结点的结构和对二叉树的基本操作。** - 了解二叉树结点的基本组成元素。 - 掌握...
### 求二叉树中节点的最大距离:深入解析与算法设计 #### 问题背景与定义 在计算机科学中,二叉树是一种重要的数据结构,它由一系列节点组成,每个节点最多有两个子节点,通常被称作左子节点和右子节点。在本问题...
( 统计二叉树结点.cpp )
### 求二叉树叶子结点个数与中序遍历 在计算机科学领域,二叉树是一种常用的数据结构,广泛应用于各种算法设计中。本文档将详细介绍如何计算二叉树中的叶子结点数量以及如何进行中序遍历。 #### 一、二叉树的基本...
### 二叉树的遍历与求深度以及结点数 #### 一、二叉树的基本概念 在探讨二叉树的遍历方法及其深度与结点数的计算之前,我们首先简要回顾一下二叉树的基本定义。二叉树是一种特殊的树结构,其中每个节点最多有两个...
二叉树上结点的路径 二叉树是一种重要的数据结构,它在计算机科学和信息技术领域中具有广泛的应用。本文将对二叉树上结点的路径进行详细的介绍和分析。 一、什么是二叉树? 二叉树是一种特殊的树形结构,它的每个...
采用先序法建立一棵二叉树,设计输出某结点数据为x的双亲结点的数据的程序,二叉树的数据域类型为字符型, 扩展二叉树的叶子结点用‘#’表示,要求可以求一棵二叉树中多个结点的双亲。
在C++编程中,二叉树是一种非常重要的数据结构,它由节点构成,每个节点最多有两个子节点,通常称为左子节点和右子节点。在本主题中,我们将深入探讨如何实现一个C++的二叉树节点类,并讨论四种基本的二叉树遍历方法...
(1)二叉树的建立 (2)求出二叉树的高度 (3)求出二叉树结点个数 (4)先序遍历递归实现 (5)先序遍历非递归实现 (6)求出二叉树叶子结点个数
根据键盘输入的扩展二叉树的前序遍历序列建立相应的二叉树,并计算该二叉树的叶子结点个数
二叉树叶子结点个数计算 本文档讨论了二叉树叶子结点个数计算的问题,涵盖了二叉树的存储结构、递归算法设计、实现提示、源程序等方面。 一、存储结构 在计算二叉树叶子结点个数时,我们需要首先设计二叉树的存储...
根据给定的文件信息,我们可以深入探讨二叉树在计算机科学中的应用,特别是关于如何使用C++编程语言来实现对二叉树结构的节点数量进行统计。本篇将重点解析二叉树的基本概念、二叉树节点计数的算法原理以及代码实现...
能够按先序遍历的次序输入二叉树的各个结点,并能够输出中序遍历的序列号,以及指定的路径 和三个应用:求二叉树的深度 二叉树的叶子结点个数和将二叉树左右子树交换
在计算机科学中,二叉树是一种重要的数据结构,它由节点(或称为结点)组成,每个节点最多有两个子节点,通常分为左子节点和右子节点。在本实验中,我们将关注一种特殊类型的节点——叶子节点,也称为终端节点,它们...