编写算法建立一棵二叉树的二叉链表; 2. 输出二叉树先序遍历序列; 3. 编写算法统计二叉树结点个数。
时间: 2024-01-23 17:13:29 浏览: 84
1. 二叉树的二叉链表结构如下:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
建立二叉树的算法可以使用递归实现,如下所示:
```
TreeNode* buildTree(vector<int>& nums, int start, int end) {
if (start > end) return nullptr;
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildTree(nums, start, mid - 1);
root->right = buildTree(nums, mid + 1, end);
return root;
}
TreeNode* buildBinaryTree(vector<int>& nums) {
return buildTree(nums, 0, nums.size() - 1);
}
```
2. 输出二叉树先序遍历序列的算法可以使用递归实现,如下所示:
```
void preorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return;
result.push_back(root->val);
preorderTraversal(root->left, result);
preorderTraversal(root->right, result);
}
vector<int> preorder(TreeNode* root) {
vector<int> result;
preorderTraversal(root, result);
return result;
}
```
3. 统计二叉树结点个数的算法可以使用递归实现,如下所示:
```
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
```
阅读全文