数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装研究
法律研究C++中的连续树
连续树定义为：从根节点到叶节点的任何路径上的节点值或权重，使得父节点与其所有直接子节点之间的绝对差值始终为1。
如果我们在根到叶的路径上选择任何节点，则
|节点权重 - 左子节点权重| = |左子节点权重 - 节点权重| = 1，对右子节点也成立
|节点权重 - 右子节点权重| = |右子节点权重 - 节点权重| = 1
图表
让我们通过示例来理解。
下面的树是连续的，因为父节点与其子节点之间的绝对差值始终为1。
下面的树不符合连续树的条件。
查找树是否连续的算法
如果根节点为空，则返回1
如果是叶节点，则返回1，因为树是连续的，这就是叶节点被访问的原因。
如果左子树为空，则检查当前节点与右子节点的连续性（计算权重的绝对差值），并递归地继续处理右子树。
如果右子树为空，则检查当前节点与左子节点的连续性（计算权重的绝对差值），并递归地继续处理左子树。
否则，计算左子节点和右子节点权重的绝对差值，并递归地继续处理左子树和右子树。
伪代码
// Function to check tree is continuous or not
struct btreeNode{
int data;
btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
// if node is NULL return 1, exit condition
if (root == NULL)
return 1;
//if leaf node is reached then tree must be continous during this path
if (root->left == NULL && root->right == NULL)
return 1;
// if no left child
if (root->left == NULL)
return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
// if no right child
if (root->right == NULL)
return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
// calculate absoute difference
return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
isContinuous(root->left) && isContinuous(root->right);
}
更新于：2020年8月3日
浏览量：156
广告