二叉树的定义
// 定义一个二叉树节点
struct BiTreeNode {
int value;
struct BiTreeNode *left;
struct BiTreeNode *right;
};
先序遍历 (递归的形式)
void preOrderTraversal(struct BiTreeNode *node) {
if (node != NULL) {
printf("%d", node->value); // 先序遍历
preOrderTraversal(node->left); // 递归调用,前序遍历左子树
// printf("%d", node->value); // 中序遍历
preOrderTraversal(node->right); // 递归调用,前序遍历右子树
// printf("%d", node->value); // 后序遍历
}
}
先序遍历 (非递归的形式)
void preOrderTraversalWithNonrecursively(struct BiTreeNode *T) {
std::stack<BiTreeNode *> s;
s.push(T); // 先让根进栈
while (!s.empty()) {
BiTreeNode *temp = s.top(); // 从栈顶取出来
printf("%d", temp->value);
s.pop(); // 从栈顶移除
if (temp->right) {
s.push(temp->right);
}
if (temp->left) {
s.push(temp->left);
}
}
}
中序遍历 (非递归的形式)
#include <stack>
void InOrderTraversalWithNonrecursively(struct BiTreeNode *node) {
if (node == NULL) {
return;
}
std::stack<BiTreeNode *> s;
s.push(node);
struct BiTreeNode *current = node->left;
while (current != NULL || !s.empty()) {
while (current != NULL) { // 一直向左走
s.push(current);
current = current->left;
}
current = s.top();
s.pop();
printf("%d", current->value);
current = current->right;
}
}
二叉树翻转
struct BiTreeNode * reverseBiTree(struct BiTreeNode *node) {
if (node == NULL) {
return node;
}
struct BiTreeNode *n = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
n->value = node->value;
// 先翻转左边的节点赋值给右边
if (node->left != NULL) {
node->right = reverseBiTree(node->left);
} else {
node->right = NULL;
}
// 再翻转右边的节点赋值给左边
if (node->right) {
node->left = reverseBiTree(node->right);
} else {
node->left = NULL;
}
return n;
}
完整的代码
#include <stack>
// 定义一个二叉树节点
struct BiTreeNode {
int value;
struct BiTreeNode *left;
struct BiTreeNode *right;
};
// 先序遍历 (递归的形式)
void preOrderTraversal(struct BiTreeNode *node) {
if (node != NULL) {
printf("%d", node->value); // 先序遍历
preOrderTraversal(node->left); // 递归调用,前序遍历左子树
// printf("%d", node->value); // 中序遍历
preOrderTraversal(node->right); // 递归调用,前序遍历右子树
// printf("%d", node->value); // 后序遍历
}
}
// 先序遍历 (非递归的形式)
void preOrderTraversalWithNonrecursively(struct BiTreeNode *T) {
std::stack<BiTreeNode *> s;
s.push(T); // 先让根进栈
while (!s.empty()) {
BiTreeNode *temp = s.top(); // 从栈顶取出来
printf("%d", temp->value);
s.pop(); // 从栈顶移除
if (temp->right) {
s.push(temp->right);
}
if (temp->left) {
s.push(temp->left);
}
}
}
// 中序遍历 (非递归的形式)
void InOrderTraversalWithNonrecursively(struct BiTreeNode *node) {
if (node == NULL) {
return;
}
std::stack<BiTreeNode *> s;
s.push(node);
struct BiTreeNode *current = node->left;
while (current != NULL || !s.empty()) {
while (current != NULL) { // 一直向左走
s.push(current);
current = current->left;
}
current = s.top();
s.pop();
printf("%d", current->value);
current = current->right;
}
}
// 二叉树翻转
struct BiTreeNode * reverseBiTree(struct BiTreeNode *node) {
if (node == NULL) {
return node;
}
struct BiTreeNode *n = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
n->value = node->value;
// 先翻转左边的节点赋值给右边
if (node->left != NULL) {
node->right = reverseBiTree(node->left);
} else {
node->right = NULL;
}
// 再翻转右边的节点赋值给左边
if (node->right) {
node->left = reverseBiTree(node->right);
} else {
node->left = NULL;
}
return n;
}