二叉树系列主题Code
Python实现二叉树遍历
# 定义二叉树节点类
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 前序遍历（非递归）
def preorderTraversal(root): if not root: return [] stack, output = [root], [] while stack: node = stack.pop() if node: output.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return output # 中序遍历（非递归）
def inorderTraversal(root): stack, output, current = [], [], root while True: while current: stack.append(current) current = current.left if not stack: return output current = stack.pop() output.append(current.val) current = current.right # 后序遍历（非递归）
def postorderTraversal(root): if not root: return [] stack1, stack2, output = [root], [], [] while stack1: node = stack1.pop() if node: stack2.append(node) if node.left: stack1.append(node.left) if node.right: stack1.append(node.right) while stack2: node = stack2.pop() output.append(node.val) return output[::-1] # 逆序输出，得到后序遍历结果 # 层次遍历（非递归）
def levelOrderTraversal(root): if not root: return [] from collections import deque queue, output = deque([root]), [] while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() # 弹出队列左侧元素 current_level.append(node.val) if node.left: queue.append(node.left) # 左孩子入队 if node.right: queue.append(node.right) # 右孩子入队 output.append(current_level) return output
cpp实现二叉树遍历
#include <iostream>
#include <stack>
#include <queue>
using namespace std; // 二叉树节点定义
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; // 前序遍历（递归实现）
void preorderTraversalRecursive(TreeNode* root) { if (root == NULL) { return; } cout << root->val << " "; preorderTraversalRecursive(root->left); preorderTraversalRecursive(root->right);
} // 前序遍历（迭代实现）
void preorderTraversalIterative(TreeNode* root) { if (root == NULL) { return; } stack<TreeNode*> stk; stk.push(root); while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); cout << node->val << " "; if (node->right != NULL) { stk.push(node->right); } if (node->left != NULL) { stk.push(node->left); } }
} // 中序遍历（递归实现）
void inorderTraversalRecursive(TreeNode* root) { if (root == NULL) { return; } inorderTraversalRecursive(root->left); cout << root->val << " "; inorderTraversalRecursive(root->right);
} // 中序遍历（迭代实现）
void inorderTraversalIterative(TreeNode* root) { if (root == NULL) { return; } stack<TreeNode*> stk; TreeNode* curr = root; while (curr != NULL || !stk.empty()) { while (curr != NULL) { stk.push(curr); curr = curr->left; } curr = stk.top(); stk.pop(); cout << curr->val << " "; curr = curr->right; }
} // 后序遍历（递归实现）
void postorderTraversalRecursive(TreeNode* root) { if (root == NULL) { return; } postorderTraversalRecursive(root->left); postorderTraversalRecursive(root->right); cout << root->val << " ";
} // 后序遍历（迭代实现）
void postorderTraversalIterative(TreeNode* root) { if (root == NULL) { return; } stack<TreeNode*> stk1, stk2; stk1.push(root); while (!stk1.empty()) { TreeNode* node = stk1.top(); stk1.pop(); stk2.push(node); if (node->left != NULL) { stk1.push(node->left); } if (node->right != NULL) { stk1.push(node->right); } } while (!stk2.empty()) { cout << stk2.top()->val << " "; stk2.pop(); }
} // 层次遍历
void levelOrderTraversal(TreeNode* root) { if (root == NULL) { return; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; i++) { 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); } } cout << endl; // 每一层遍历完后换行 } int main() { // 创建二叉树 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); cout << "前序遍历（递归实现）: "; preorderTraversalRecursive(root); cout << endl; // 输出：1 2 4 5 3 6 7
}水平有限，有问题随时联系~