二叉树，非递归法

递归法

二叉树的递归，有前序遍历、中序遍历、后序遍历，一般采用递归法，比较简单

struct Node {
  int val;
  struct Node *left;
  struct Node *right;
}
//前序遍历
void print_tree(struct Node* root)
{
  if (root != NULL) {
    //中
    printf("%d ", root->val);
    //左
    if(root->left != NULL) {
      print_tree(root->left);
    }
    //右
    if(root->right != NULL) {
      print_tree(root->right);
    }
  }
}

//中序遍历
void print_tree(struct Node* root)
{
  if (root != NULL) {
    //左
    if(root->left != NULL) {
      print_tree(root->left);
    }
    //中
    printf("%d ", root->val);
    //右
    if(root->right != NULL) {
      print_tree(root->right);
    }
  }
}

//后序遍历
void print_tree(struct Node* root)
{
  if (root != NULL) {
    //左
    if(root->left != NULL) {
      print_tree(root->left);
    }
    //右
    if(root->right != NULL) {
      print_tree(root->right);
    }
    //中
    printf("%d ", root->val);
  }
}

非递归法

二叉树非递归法，采用栈来实现

//前序遍历
void print_tree(struct Node* root)
{
  if (root != NULL) {
    s.push(root);  //入栈
  }
  while(s.notEmpty()) {
    p = s.pop();//出栈
    printf("%d ", p->val);
    s.push(p->right);
    s.push(p->left);
  }
}

//中序遍历
void print_tree(struct Node* root)
{
  struct Node *p = root;
  while(p!=NULL || s.notEmpty()) {
    while(p != NULL) {
      s.push(p);
      p = p->left;
    }
    p = s.pop();
    printf("%d ", p->val);
    if(p->right != NULL) {
      p = p->right;
    } else {
      p = NULL;
    }
  }
}

//后序遍历
void print_tree(struct Node* root)
{
  struct Node *p = root;
  while(p!=NULL || s.notEmpty()) {
    while(p != NULL) {
      s.push(p);
      p = p->left;
    }
    p = s.pop();
    printf("%d ", p->val);
    //这里需要判断一下，当前p是否为当前栈顶的左子树，如果是的话那么还需要先访问右子树才能访问根节点
    //如果已经不是左子树的话，那么说明左子数都已经访问完毕，可以访问根节点了，所以讲p复制为NULL
    //取根节点
    if(s.notEmpty() && s.peek().left) {
      p = s.peek().right;
    } else {
      p = NULL;
    }
  }
}