输入一个二叉树,用一位数组存储,完成: 1、二叉树的层序输出 2、输入一个结点值,求其左右孩子 3、输入一个结点值,求其父结点 4、求树的深度
时间: 2023-06-04 08:05:49 浏览: 48
1、关于二叉树的层序输出:
可以使用队列来实现二叉树的层序遍历,从根节点开始,先将根节点入队,然后依次将每个节点的左右孩子入队,依次出队遍历即可,代码如下:
```
void levelorder_print(BinaryTreeNode* pRoot) {
if (pRoot == nullptr) return;
std::queue<BinaryTreeNode*> Q;
Q.push(pRoot);
while (!Q.empty()) {
BinaryTreeNode* pNode = Q.front();
Q.pop();
std::cout << pNode->data << " ";
if (pNode->left != nullptr) Q.push(pNode->left);
if (pNode->right != nullptr) Q.push(pNode->right);
}
}
```
2、关于输入一个结点值,求其左右孩子:
可以在遍历过程中寻找对应的节点,若找到则返回其左右孩子即可,代码如下:
```
BinaryTreeNode* find_node(BinaryTreeNode* pRoot, int value) {
if (pRoot == nullptr) return nullptr;
if (pRoot->data == value) return pRoot;
BinaryTreeNode* pLeft = find_node(pRoot->left, value);
BinaryTreeNode* pRight = find_node(pRoot->right, value);
if (pLeft != nullptr) return pLeft;
if (pRight != nullptr) return pRight;
return nullptr;
}
void find_children(BinaryTreeNode* pRoot, int value) {
BinaryTreeNode* pNode = find_node(pRoot, value);
if (pNode != nullptr) {
if (pNode->left != nullptr)
std::cout << "left child: " << pNode->left->data << std::endl;
if (pNode->right != nullptr)
std::cout << "right child: " << pNode->right->data << std::endl;
} else {
std::cout << "Not found!" << std::endl;
}
}
```
3、关于输入一个结点值,求其父结点:
同样可以在遍历过程中寻找对应的节点,若找到则返回其父节点即可,代码如下:
```
BinaryTreeNode* find_parent(BinaryTreeNode* pRoot, int value) {
if (pRoot == nullptr) return nullptr;
if (pRoot->left && pRoot->left->data == value)
return pRoot;
if (pRoot->right && pRoot->right->data == value)
return pRoot;
BinaryTreeNode* pLeft = find_parent(pRoot->left, value);
BinaryTreeNode* pRight = find_parent(pRoot->right, value);
if (pLeft != nullptr) return pLeft;
if (pRight != nullptr) return pRight;
return nullptr;
}
void find_parent_node(BinaryTreeNode* pRoot, int value) {
BinaryTreeNode* pNode = find_parent(pRoot, value);
if (pNode != nullptr) {
std::cout << "parent node: " << pNode->data << std::endl;
} else {
std::cout << "Not found!" << std::endl;
}
}
```
4、关于求树的深度:
可以使用递归的方式求出树的深度,代码如下:
```
int tree_depth(BinaryTreeNode* pRoot) {
if (pRoot == nullptr) return 0;
int left_depth = tree_depth(pRoot->left);
int right_depth = tree_depth(pRoot->right);
return std::max(left_depth, right_depth) + 1;
}
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)