二叉树
#include <iostream>
#include <queue>
using namespace std;
//树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
typedef TreeNode* Tree;
//前序遍历
void preOrderTraversal(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
//中序遍历
void inOrderTraversal(TreeNode* root) {
if (root == NULL) return;
inOrderTraversal(root->left);
cout << root->val << " ";
inOrderTraversal(root->right);
}
//后序遍历
void postOrderTraversal(TreeNode* root) {
if (root == NULL) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->val << " ";
}
//层次遍历
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != NULL) q.push(node->left);
if (node->right != NULL) q.push(node->right);
}
}
//插入节点
void insertNode(Tree& root, int val) {
if (root == NULL) {
Tree root = new TreeNode;
root->left = NULL;
root->right = NULL;
root->val = val;
return;
}
if (val < root->val) {
insertNode(root->left, val);
} else if (val > root->val) {
insertNode(root->right, val);
}
}
//二叉树高度
int Height(Tree root) {
if (root == NULL) {
return 0;
} else {
int leftHeight = Height(root->left);
int rightHeight = Height(root->right);
return max(leftHeight, rightHeight) + 1;
}
}
评论区