二叉树的递归和迭代遍历-C++版-蒲公英云

二叉树的递归和迭代遍历-C++版

文章目录

- - 1. 前序遍历
  - 1. 中序遍历
  - 1. 后序遍历
  - 1. 层序遍历
  - 1. 测试函数
// binary_tree.h
// 结点
struct TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int value) : val(value), left(nullptr), right(nullptr) { }
};

/** 二叉树增加结点 **/
void addTreeNode(TreeNode &root, TreeNode node) {
if (node->val <= root->val && root->left) {
addTreeNode(root->left, node);
} else if (node->val <= root->val && root->left == nullptr) {
root->left = node;
} else if (root->right) {
addTreeNode(root->right, node);
} else {
root->right = node;
}
}

1. 前序遍历

/********************** 前序遍历-递归版 **********************/
void preorderRecursive(TreeNode *root) { 
  if (nullptr == root) { 
    return;
  }
  cout << root->val << " ";
  preorderRecursive(root->left);
  preorderRecursive(root->right);
  return;
}
/********************** 前序遍历-迭代版 **********************/
void preorderIterative(TreeNode *root) { 
  if (nullptr == root) { 
    return;
  }
  std::stack<TreeNode *> stk;
  TreeNode *node = root;
  stk.push(node);
  while (!stk.empty()) { 
    node = stk.top();
    stk.pop();
    cout << node->val << " ";
    if (node->right) { 
      stk.push(node->right);
    }
    if (node->left) { 
      stk.push(node->left);
    }
  }
  return;
}

2. 中序遍历

/********************** 中序遍历-递归版 **********************/
void inorderRecursive(TreeNode *root) { 
  if (root) { 
    inorderRecursive(root->left);
    cout << root->val << " ";
    inorderRecursive(root->right);
  }
  return;
}
/********************** 中序遍历-迭代版 **********************/
void inorderIterative(TreeNode *root) { 
  std::stack<TreeNode *> stk;
  TreeNode *node = root;
  while (node || !stk.empty()) { 
    if (node) { 
      stk.push(node);
      node = node->left;
    } else { 
      node = stk.top();
      stk.pop();
      cout << node->val << " ";
      node = node->right;
    }
  }
  return;
}

3. 后序遍历

/********************** 后序遍历-递归版 **********************/
void postorderRecursive(TreeNode *root) { 
  if (root) { 
    postorderRecursive(root->left);
    postorderRecursive(root->right);
    cout << root->val << " ";
  }
  return;
}
/********************** 后序遍历-迭代版 **********************/
void postorderIterative(TreeNode *root) { 
  if (nullptr == root) { 
    return;
  }
  std::stack<TreeNode *> stk;
  std::vector<int> result;
  TreeNode *node = root;
  stk.push(node);
  while (!stk.empty()) { 
    node = stk.top();
    stk.pop();
    result.emplace(result.begin(), node->val);
    if (node->left) { 
      stk.push(node->left);
    }
    if (node->right) { 
      stk.push(node->right);
    }
  }
  std::copy(result.begin(), result.end(), std::ostream_iterator<int>{ cout, " "});
  return;
}

4. 层序遍历

/********************** 层序遍历-迭代版 **********************/
void levelorderTraversal(TreeNode *root) { 
  if (nullptr == root) { 
    return;
  }
  std::queue<TreeNode *> que;
  TreeNode *node = root;
  que.push(node);
  while (!que.empty()) { 
    node = que.front();
    que.pop();
    cout << node->val << " ";
    if (node->left) { 
      que.emplace(node->left);
    }
    if (node->right) { 
      que.emplace(node->right);
    }
  }
  return;
}

5. 测试函数

void binaryTreeTest() { 
  TreeNode *root = new TreeNode(3);
  std::vector<int> treeElem{ 1, 2, 4, 5};
  for (int i{ }; i < treeElem.size(); ++i) { 
    TreeNode *node = new TreeNode(treeElem.at(i));
    addTreeNode(root, node);
  }
  cout << "\ntraversal result: " << endl;
  cout << std::string(32, '*') << endl;
  // preorderRecursive(root); // 3 1 2 4 5
  // preorderIterative(root); // 3 1 2 4 5
  // inorderRecursive(root); // 1 2 3 4 5
  // inorderIterative(root); // 1 2 3 4 5
  // postorderRecursive(root); // 2 1 5 4 3
  // postorderIterative(root); // 2 1 5 4 3
  levelorderTraversal(root); // 3 1 4 2 5
  cout << endl;
  cout << std::string(32, '*') << endl;
  return;
}