遍历二叉树的神级方法

[编程题]遍历二叉树的神级方法

热度指数：1703 时间限制：C/C++ 8秒，其他语言16秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

分别按照二叉树先序，中序和后序打印所有的节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

输出三行分别表示二叉树的前序，中序和后序遍历。

示例1

输入

输出

1 2 3
2 1 3
2 3 1

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct TreeNode {
  ElemType data;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTreeNode;

PTreeNode buildTree(int (*data)[2], int index) {
  // recursion exit conditon
  if (!index) return NULL;
  
  PTreeNode root = (PTreeNode) malloc(sizeof(TreeNode));
  if (!root) return NULL;
  
  root->data  = index;
  root->left  = buildTree(data, **(data + index));
  root->right = buildTree(data, *(*(data + index) + 1));
  return root;
}

void output(PTreeNode node) {
  fprintf(stdout, "%d ", (*node).data);
}

// recursively
void preorder(PTreeNode root, void (*visit) (PTreeNode)) {
  if (!root) return;
  visit(root);
  preorder(root->left,  visit);
  preorder(root->right, visit);
}

// iteratively
void inorder(PTreeNode root, void (*visit) (PTreeNode)) {
  
  PTreeNode stk[(int) 1E6];
  int top = 0;
  
  PTreeNode p = root, curr;
  while (top || p)  {
    while (p) {
      *(stk + top++) = p;
      p = p->left;
    }
    curr = *(stk + --top);
    visit(curr);
    
    p = curr->right;
  }
}

// recursively
void postorder(PTreeNode root, void (*visit) (PTreeNode)) {
  if (!root) return;
  postorder(root->left,  visit);
  postorder(root->right, visit);
  visit(root);
}

int main(const int argc, const char* const argv[]) {
  int n, root;
  fscanf(stdin, "%d %d", &n, &root);
  
  int data[n + 1][2];
  int fa, lch, rch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &lch, &rch);
    **(data + fa) = lch;
    *(*(data + fa) + 1) = rch;
  }
  
  PTreeNode pRoot = buildTree(data, root);
  preorder(pRoot, output);
  fputc(10, stdout);
  
  inorder(pRoot, output);
  fputc(10, stdout);
  
  postorder(pRoot, output);
  return 0;
}

发表于 2021-07-21 09:24:58 回复(0)