当前位置：首页 > news >正文

【数据结构】_二叉树部分特征统计

news 2025/6/23 13:39:56

1. 二叉树结点总个数

思路1：全局或全局静态变量计数

思路2：分治思路

2. 二叉树叶子结点个数

3. 二叉树高度

4. 二叉树第k层的结点个数

5. 查找二叉树值为x的结点

本文中的测试二叉树结构如下：

1. 二叉树结点总个数

思路1：全局或全局静态变量计数

创建全局整型变量或全局静态整型变量size对非空结点个数进行累加来计算结点总个数。如：

int size = 0;
// 二叉树结点总个数
int TreeSize(BTNode* root) {if (root == NULL) return 0;elsesize++;TreeSize(root->left);TreeSize(root->right);return size;
}
int main() {BTNode* root = CreateBinaryTree();printf("BinaryTreeNodesSize: ");printf("%d", TreeSize(root));printf("\nBinaryTreeNodesSize: ");printf("%d", TreeSize(root));printf("\nBinaryTreeNodesSize: ");printf("%d", TreeSize(root));return 0;
}

该思路不可行，全局变量与全局静态变量在程序生命周期中仅初始化一次，第一次调用结点计算函数结果正确，后续会由于静态变量不重新初始化而导致结果累积：

如果要通过全局变量或全局静态变量实现二叉树结点个数统计，则需在每次调用前将其置零：

int main() {BTNode* root = CreateBinaryTree();size = 0;printf("\nBinaryTreeNodesSize: ");printf("%d", TreeSize(root));size = 0;printf("\nBinaryTreeNodesSize: ");printf("%d", TreeSize(root));size = 0;printf("\nBinaryTreeNodesSize: ");printf("%d", TreeSize(root));return 0;
}

运行结果如下：

但这种做法显然处理得不够简洁，需要另寻他法。

思路2：分治思路

若树为空，则结点个数为0；

若树不为空，则结点个数=左子树结点数+右子树结点数+1；

// 二叉树结点总个数
int TreeSize(BTNode* root) {return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

运行结果如下：

注：创建局部整型变量size对非空结点个数进行累加来计算结点总个数的思路是不可行的，因为递归调用中每次调用会创建新的栈帧，这样计算是错误的。

2. 二叉树叶子结点个数

与二叉树结点总个数计算思路类似，此处仅展示分治思路实现叶子结点个数计算。

若树为空，则叶子结点个数为0；

若树非空，则叶子结点个数=左子树叶子结点个数+右子树叶子结点个数；

// 二叉树叶子结点个数
int TreeLeafSize(BTNode* root) {if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int main() {BTNode* root = CreateBinaryTree();printf("\nBinaryTreeLeafNodesSize: ");printf("%d", TreeLeafSize(root));return 0;
}

3. 二叉树高度

同样采用分治思想：

若树为空，则二叉树高度为0；

若树非空，则二叉树高度为左子树与右子树中较高的那个子树的高度+1；

// 二叉树高度
int TreeHeight(BTNode* root) {if (root == NULL)return 0;int LeftTreeHeight = TreeHeight(root->left);int RightTreeHeight = TreeHeight(root->right);return LeftTreeHeight > RightTreeHeight ? LeftTreeHeight + 1 : RightTreeHeight + 1;
}
int main() {BTNode* root = CreateBinaryTree();printf("\nBinaryTreeHeight: ");printf("%d", TreeHeight(root));return 0;
}

注意：

1. 此处创建两个临时变量LeftTreeHeight和RightTreeHeight用于保存当前结点左子树和右子树的高度，没有采用两个临时变量的写法如下：

int TreeHeight(BTNode* root) {if (root == NULL)return 0;return TreeHeight(root->left) > TreeHeight(root->right) ? 
TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

这种写法存在一定问题：在比较左右子树高度时，重复调用了两次递归函数（三目操作符比较一次，返回再计算一次）。每个节点的左右子树高度被重复计算，导致时间复杂度呈指数级增长，在树节点较多时会导致性能急剧下降，甚至栈溢出。

2. 也可包含math.h头文件后，使用fmax函数进行处理：

int TreeHeight(BTNode* root) {if (root == NULL)return 0;int LeftTreeHeight = TreeHeight(root->left);int RightTreeHeight = TreeHeight(root->right);return fmax(LeftTreeHeight, RightTreeHeight) + 1;
}

4. 二叉树第k层的结点个数

同样采用分治思想：

若二叉树为空，则返回0（无论k为何值该层结点数都为0）；

在二叉树非空的情况下，若k==1，则返回1（说明当前结点就在第k层）；

在二叉树非空的情况下，若k>1，则返回左子树第k-1层结点的个数+右子树k-1层结点的个数；

// 二叉树第K层结点个数
int TreeKLevelNode(BTNode* root,int k) {if (root == NULL)return 0;if (k == 1)return 1;return TreeKLevelNode(root->left, k-1) + TreeKLevelNode(root->right, k-1);
}
int main() {BTNode* root = CreateBinaryTree();printf("\nBinaryTree3LevelNodesSize: ");printf("%d", TreeKLevelNode(root, 3));return 0;
}

5. 查找二叉树值为x的结点

使用前序进行遍历（先根结点后子结点），分治思想：

如果二叉树为空，则返回NULL；

如果二叉树非空，先判当前根结点的值，与给定查找值x相等则返回当前根结点；

若当前根结点值给定查找值x不等，则依次查找当前根结点的左右子结点。

（若有多个结点的值都为x，返回第一个结点）

// 查找二叉树值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x) {if (root == NULL)return NULL;if (root->data == x)return root;BTNode* leftRet = TreeFind(root->left,x);if (leftRet)return leftRet;BTNode* rightRet = TreeFind(root->right, x);if (rightRet)return rightRet;return NULL;
}

注意点：

1. 递归调用TreeFind遍历左子树或右子树后，一定要创建指针变量接收递归调用的返回值；

2. 若在左子树找到了值为x的结点，直接返回即可，无需再遍历右子树；

查看全文

http://www.lryc.cn/news/573844.html