用c++实现对任意给定的二叉树完成下列操作: (1)根据输入的序列,建立二叉链表存储结构: (2)输出该二叉树的先序、中序、后序遍历结果(递归算法); (3)先序遍历二叉树(非递归算法);(4)借助队列实现二叉树的层次遍历;(5)求二叉树的高度; (6)求二叉树叶子结点个数: (7)将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。
时间: 2024-02-17 20:03:01 浏览: 25
好的,我会依次回答您的问题。
1. 根据输入的序列,建立二叉链表存储结构:
可以采用递归的方式建立二叉树,每次读入一个数,如果是#,表示该节点为空,否则创建一个新节点,然后递归地将左右子树建立完成。
具体代码如下:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void buildTree(TreeNode* &root) {
int val;
cin >> val;
if (val == -1) { // 空节点
root = NULL;
return;
}
root = new TreeNode(val);
buildTree(root->left);
buildTree(root->right);
}
```
2. 输出该二叉树的先序、中序、后序遍历结果(递归算法):
二叉树的递归遍历比较简单,具体代码如下:
```c++
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
```
3. 先序遍历二叉树(非递归算法):
非递归遍历需要借助栈来实现。具体代码如下:
```c++
void preOrderNonRecursive(TreeNode* root) {
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
if (cur == NULL) continue;
cout << cur->val << " ";
s.push(cur->right); // 先压右子树
s.push(cur->left);
}
}
```
4. 借助队列实现二叉树的层次遍历:
层次遍历需要借助队列来实现。具体代码如下:
```c++
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (cur == NULL) continue;
cout << cur->val << " ";
q.push(cur->left);
q.push(cur->right);
}
}
```
5. 求二叉树的高度:
二叉树的高度可以递归地求解。具体代码如下:
```c++
int height(TreeNode* root) {
if (root == NULL) return 0;
return max(height(root->left), height(root->right)) + 1;
}
```
6. 求二叉树叶子结点个数:
可以递归地统计二叉树的叶子节点个数。具体代码如下:
```c++
int countLeaf(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaf(root->left) + countLeaf(root->right);
}
```
7. 将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。
这道题目可以转化为树的遍历问题,可以采用递归的方式来解决。具体代码如下:
```c++
int countLeaf(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaf(root->left) + countLeaf(root->right);
}
int countLeaf(TreeNode* root) {
int res = 0;
while (root) {
if (root->left == NULL) {
res += countLeaf(root->right);
break;
}
TreeNode* pre = root->left;
while (pre->right && pre->right != root) {
pre = pre->right;
}
if (pre->right == NULL) {
pre->right = root;
root = root->left;
} else {
pre->right = NULL;
res += countLeaf(root->left);
root = root->right;
}
}
return res;
}
```
这样就完成了对您提出的问题的回答,希望能够帮助到您。