初阶数据结构二叉树常用函数(二)

2024/10/24 3:24:28 来源：https://blog.csdn.net/Zbldx/article/details/140246188 浏览: 次关键词：初阶数据结构二叉树常用函数(二)

函数一求二叉树第K层的节点个数

还是一样我们假设 K就是等于一

如果说是一个空数的话就返回0

如果说有值的话就返回一个1就可以

假设这个这层既不为空又不是第K层的话那么就说明第K层肯定是子树下面

那么就说明是左右子树的第（K-1）层

那么只将它们相加并且返回它们的值就好了

核心代码表示如下

//树的第k层个数
//树的第k层个数 = 左子树第k-1层个数+右子树第k-1层个数
int TreeLevle(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}int leftk = TreeLevle(root->left, k - 1);int rightk = TreeLevle(root->right, k - 1);return leftk + rightk;
}

我们来看看结果怎么样

函数二求二叉树的深度

这里还是一样我们先来看图

我们先来看第极限的情况

假如我们的本身就是一个空树的话我们可以直接返回0

如果不是空树的话我们可以寻找我们的左子树和右子树中的较大值（一样大返回哪一个都可以）

将它们加一后返回就可以

核心代码如下

//树的高度
//当前树的高度=左右子树大的那个+1
int TreeHight(BTNode* root)
{if (root == NULL){return 0;}int leftHight = TreeHight(root->left);int rightHight = TreeHight(root->right);return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}

还是一样我们来看看效果

深度是4确实没错

函数三求某个值为X的节点

还是一样我们首先考虑极限情况

假设值就在根上

那么我们直接返回根的位置就好了

否则的话我们就往左边右边子树遍历

我们来看看核心代码

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

我们发现这里可以找出来了