二叉树前序 中序 后序 递归算法以及非递归算法

二叉树前序 中序 后序 递归算法以及非递归算法

一：递归算法`

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
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("\n");
 inorderTraversal(a);printf("\n");
 postorderTraversal(a);printf("\n");

二：非递归

#include<stdio.h>
#include<stdlib.h>
#include<stack>
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;
  }
 }
}