c++ 二叉树标准代码
时间: 2023-03-13 14:26:20 浏览: 58
二叉树是一种常用的数据结构,其标准代码如下:struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
相关问题
二叉树两点最短距离 C++
以下是使用C++编写的二叉树两点最短距离的代码示例:
```cpp
#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 寻找最低公共祖先节点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
} else if (left) {
return left;
} else {
return right;
}
}
// 计算节点到最低公共祖先节点的距离
int distanceToLCA(TreeNode* node, TreeNode* target) {
if (node == nullptr) {
return INT_MAX;
}
if (node == target) {
return 0;
}
return 1 + std::min(distanceToLCA(node->left, target), distanceToLCA(node->right, target));
}
// 计算最短距离
int shortestDistance(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* lca = lowestCommonAncestor(root, p, q);
int distance_p = distanceToLCA(lca, p);
int distance_q = distanceToLCA(lca, q);
return distance_p + distance_q;
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(5);
root->right = new TreeNode(1);
root->left->left = new TreeNode(6);
root->left->right = new TreeNode(2);
root->right->left = new TreeNode(0);
root->right->right = new TreeNode(8);
root->left->right->left = new TreeNode(7);
root->left->right->right = new TreeNode(4);
// 寻找节点5和节点4的最短距离
int distance = shortestDistance(root, root->left, root->left->right->right);
std::cout << distance << std::endl; // 输出2,即节点5和节点4之间的最短距离
return 0;
}
```
请注意,此示例代码中使用了C++标准库的queue和iostream头文件,并假设了树中的节点值不重复。在实际应用中,你可能需要根据具体情况进行调整。
建立C++代码二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现,可以自己输入字母来构成二叉树
好的,我来帮您解答这个问题。
首先,我们需要定义二叉树的节点结构体,包括节点值、左右子节点指针:
```c++
struct Node {
char value; // 节点值
Node* left; // 左子节点指针
Node* right; // 右子节点指针
};
```
然后,我们可以定义一个二叉树类,包括插入节点、先序遍历、层次遍历等方法:
```c++
class BinaryTree {
public:
BinaryTree(); // 构造函数
~BinaryTree(); // 析构函数
void insert(char value); // 插入节点
void preorderTraversal(); // 先序遍历
void levelTraversal(); // 层次遍历
private:
Node* root; // 根节点指针
void preorderTraversalHelper(Node* node); // 先序遍历辅助函数
};
```
下面是具体实现:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
char value; // 节点值
Node* left; // 左子节点指针
Node* right; // 右子节点指针
};
class BinaryTree {
public:
BinaryTree() {
root = nullptr;
}
~BinaryTree() {
// TODO: 析构函数
}
void insert(char value) {
if (root == nullptr) {
root = new Node{value, nullptr, nullptr};
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
if (node->left == nullptr) {
node->left = new Node{value, nullptr, nullptr};
return;
} else {
q.push(node->left);
}
if (node->right == nullptr) {
node->right = new Node{value, nullptr, nullptr};
return;
} else {
q.push(node->right);
}
}
}
void preorderTraversal() {
preorderTraversalHelper(root);
cout << endl;
}
void levelTraversal() {
if (root == nullptr) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->value << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
cout << endl;
}
private:
Node* root;
void preorderTraversalHelper(Node* node) {
if (node == nullptr) {
return;
}
cout << node->value << " ";
preorderTraversalHelper(node->left);
preorderTraversalHelper(node->right);
}
};
int main() {
BinaryTree tree;
// 构建二叉树
tree.insert('A');
tree.insert('B');
tree.insert('C');
tree.insert('D');
tree.insert('E');
tree.insert('F');
tree.insert('G');
tree.insert('H');
tree.insert('I');
// 先序遍历
tree.preorderTraversal();
// 层次遍历
tree.levelTraversal();
return 0;
}
```
输入字母来构成二叉树,可以将 `insert` 方法改为从标准输入读入节点值,具体实现略。