ツリー前シーケンスにおけるシーケンス後シーケンス再帰アルゴリズムおよび非再帰アルゴリズム
22533 ワード
ツリー前シーケンスにおけるシーケンス後シーケンス再帰アルゴリズムおよび非再帰アルゴリズム
一:再帰アルゴリズム`
二:非再帰
一:再帰アルゴリズム`
#include
#include
#include
typedef struct Node {
char value;
struct Node* left;
struct Node* right;
}Node;
//
void preorderTraversal(Node* root) {
if (root == NULL) {
return;
}
else {
printf("%c ", root->value);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
//
void inorderTraversal(Node* root) {
if (root == NULL) {
return;
}
else {
inorderTraversal(root->left);
printf("%c ", root->value);
inorderTraversal(root->right);
}
}
//
void postorderTraversal(Node* root) {
if (root == NULL) {
return;
}
else {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->value);
}
}
Node* createNode(ch) {
Node* node = (Node*)malloc(sizeof(Node));
node->value = ch;
node->left = node->right = NULL;
return node;
}
int main() {
Node* a = createNode('A');
Node* b = createNode('B');
Node* c = createNode('C');
Node* d = createNode('D');
Node* e = createNode('E');
Node* f = createNode('F');
Node* g = createNode('G');
Node* h = createNode('H');
a->left = b;a->right = c;
b->left = d;b->right = e;
c->left = f;c->right = g;
d->left = NULL;d->right = NULL;
e->left = NULL;e->right = h;
preorderTraversal(a);printf("
");
inorderTraversal(a);printf("
");
postorderTraversal(a);printf("
");
二:非再帰
#include
#include
#include
typedef struct Node {
int val;
struct Node* left;
struct Node* right;
}Node;
//
void preorderNor(Node* root) {
Node* cur = root;
std::stack<Node*>st;
while (cur != NULL || !st.empty()) {
while (cur != NULL) {
printf("%d ", cur->val);
st.push(cur);
cur = cur->left;
}
Node* top = st.top();
st.pop();
cur = top->right;
}
}
//
void inorderNor(Node* root) {
Node* cur = root;
std::stack<Node*>st;
while (cur != NULL || !st.empty()) {
while (cur != NULL) {
st.push(cur);
cur = cur->left;
}
Node* top = st.top();
printf("%d ", top->val);
st.pop();
cur = top->right;
}
}
//
void postorderNor(Node* root) {
Node* cur = root;
std::stack<Node*>st;
Node* last = NULL;
while (cur != NULL || !st.empty()) {
while (cur != NULL) {
st.push(cur);
cur = cur->left;
}
Node* top = st.top();
if (top->right == NULL|| top->right == last) {
st.pop();
printf("%d ", top->val);
last = top;
}
else {
cur = top->right;
}
}
}