struct TreeNode {
TreeNode* left;
TreeNode* right;
int val;
TreeNode(int x) {
val = x;
left = nullptr;
right = nullptr;
}
};
/*
* 前序遍历 递归
*/
void preOrderRecursive(TreeNode* root) {
if (!root) return;
cout << root->val << ", ";
preOrderRecursive(root->left);
preOrderRecursive(root->right);
}
/*
* 前序遍历 非递归
*/
void preOrderIterative(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
while (!s.empty() || root) {
while (root) {
cout << root->val << ", ";
s.push(root);
root = root->left;
}
if (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node->right) root = node->right;
}
}
}
/*
* 中序遍历 递归
*/
void inOrderRecursive(TreeNode* root) {
if (!root) return;
inOrderRecursive(root->left);
cout << root->val << ", ";
inOrderRecursive(root->right);
}
/*
* 中序遍历 非递归
*/
void inOrderIterative(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}
if (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << ", ";
if (node->right) root = node->right;
}
}
}
/*
* 后续遍历 递归
*/
void postOrderRecursive(TreeNode* root) {
if (!root) return;
postOrderRecursive(root->left);
postOrderRecursive(root->right);
cout << root->val << ", ";
}
/*
* 后续遍历 非递归
*/
void postOrderIterative(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
TreeNode* visited = nullptr;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
if (root->right == nullptr || root->right == visited) {
cout << root->val << " ,";
s.pop();
visited = root;
root = nullptr;
} else {
root = root->right;
}
}
}
/*
* 层序遍历 递归
*/
int height(TreeNode* root) {
if (!root) return 0;
int left = 1 + height(root->left);
int right = 1 + height(root->right);
return left > right ? left : right;
}
void levelOrderRecursiveInternal(TreeNode* root, int level) {
if (!root) return;
if (level == 1) {
cout << root->val << " ,";
}
levelOrderRecursiveInternal(root->left, level - 1);
levelOrderRecursiveInternal(root->right, level - 1);
}
void levelOrderRecursive(TreeNode* root) {
if (!root) return;
int h = height(root);
for (int i = 1; i <= h; i++) {
levelOrderRecursiveInternal(root, i);
}
}
/*
* 层序遍历 非递归
*/
void levelOrderIterative(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " ,";
if (node->left) {
s.push(node->left);
}
if (node->right) {
s.push(node->right);
}
}
}
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(4);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(10);
cout << endl << "***** pre order *****" << endl;
preOrderRecursive(root);
cout << endl << "*****" << endl;
preOrderIterative(root);
cout << endl << "*****" << endl;
cout << endl << "***** in order *****" << endl;
inOrderRecursive(root);
cout << endl << "*****" << endl;
inOrderIterative(root);
cout << endl << "*****" << endl;
cout << endl << "***** post order *****" << endl;
postOrderRecursive(root);
cout << endl << "*****" << endl;
postOrderIterative(root);
cout << endl << "*****" << endl;
cout << endl << "***** level order *****" << endl;
levelOrderRecursive(root);
cout << endl << "*****" << endl;
levelOrderIterative(root);
cout << endl << "*****" << endl;
// i = 3, j = 6 // a, 6
}
网友评论