设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 萌新训练营 › 萌新交流区 › c++二叉树
返回列表 发新帖
查看: 1572|回复: 2

[已解决]c++二叉树

[复制链接]
lazy-xy
发表于 2023-10-29 09:16:49 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
将以下内容写成多个函数在一个主函数中实现
1、用创建结点方法创建二叉树；2、层次遍历算法实现；3、将二叉树的顺序存储结构转换为链式存储结构非递归算法和递归算法；4、垂直输出二叉树；5、二叉树前序遍历、中序遍历和后序遍历的递归和非递归算法实现；6、用前序遍历算法创建二叉树；7、二叉树前序遍历应用：快速排序递归算法；8、二叉树前序遍历应用：求幂集递归算法；9、二叉树前序遍历应用：汉诺塔问题递归算法；10、用递归算法求二叉树的高度；11、用递归算法完成两个二叉树的复制；12、由前序和中序序列建立二叉树。
最佳答案
月排行榜 / 总排行榜
陶远航
2023-10-29 09:17:48
这是一个相当大的问题，涉及到许多二叉树的操作和算法。由于篇幅限制，我将提供一些基本的函数和算法的实现，但可能无法覆盖所有的要求。

首先，我们需要定义一个二叉树节点的结构：
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

1. 创建二叉树：
TreeNode* createBinaryTree(vector<int>& nodes, int index) {
    if(index >= nodes.size() || nodes[index] == -1) // -1表示空节点
        return NULL;
    TreeNode* root = new TreeNode(nodes[index]);
    root->left = createBinaryTree(nodes, 2 * index + 1);
    root->right = createBinaryTree(nodes, 2 * index + 2);
    return root;
}

2. 层次遍历算法：
void levelOrderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if(node->left != NULL)
            q.push(node->left);
        if(node->right != NULL)
            q.push(node->right);
    }
}

3. 二叉树的顺序存储结构转换为链式存储结构：
TreeNode* convertArrayToBinaryTree(vector<int>& nodes) {
    return createBinaryTree(nodes, 0);
}

4. 二叉树前序遍历、中序遍历和后序遍历的递归算法实现：
void preorderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void inorderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

void postorderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

以上只是一部分的实现，其他的需求如垂直输出二叉树、用前序遍历算法创建二叉树、二叉树前序遍历的应用、用递归算法求二叉树的高度、用递归算法完成两个二叉树的复制、由前序和中序序列建立二叉树等，都需要更复杂的算法和代码实现，这超出了这个回答的范围。我建议你可以查阅相关的数据结构和算法书籍，或者在线搜索相关的教程和代码示例，这将对你有所帮助。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

陶远航
发表于 2023-10-29 09:17:48 | 显示全部楼层    本楼为最佳答案   
这是一个相当大的问题，涉及到许多二叉树的操作和算法。由于篇幅限制，我将提供一些基本的函数和算法的实现，但可能无法覆盖所有的要求。

首先，我们需要定义一个二叉树节点的结构：
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

1. 创建二叉树：
TreeNode* createBinaryTree(vector<int>& nodes, int index) {
    if(index >= nodes.size() || nodes[index] == -1) // -1表示空节点
        return NULL;
    TreeNode* root = new TreeNode(nodes[index]);
    root->left = createBinaryTree(nodes, 2 * index + 1);
    root->right = createBinaryTree(nodes, 2 * index + 2);
    return root;
}

2. 层次遍历算法：
void levelOrderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if(node->left != NULL)
            q.push(node->left);
        if(node->right != NULL)
            q.push(node->right);
    }
}

3. 二叉树的顺序存储结构转换为链式存储结构：
TreeNode* convertArrayToBinaryTree(vector<int>& nodes) {
    return createBinaryTree(nodes, 0);
}

4. 二叉树前序遍历、中序遍历和后序遍历的递归算法实现：
void preorderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

void inorderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

void postorderTraversal(TreeNode* root) {
    if(root == NULL)
        return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

以上只是一部分的实现，其他的需求如垂直输出二叉树、用前序遍历算法创建二叉树、二叉树前序遍历的应用、用递归算法求二叉树的高度、用递归算法完成两个二叉树的复制、由前序和中序序列建立二叉树等，都需要更复杂的算法和代码实现，这超出了这个回答的范围。我建议你可以查阅相关的数据结构和算法书籍，或者在线搜索相关的教程和代码示例，这将对你有所帮助。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

isdkz
发表于 2023-10-29 09:18:02 | 显示全部楼层
以下是对应的C++代码实现：
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

// 树结点
struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 创建二叉树
TreeNode* createBinaryTree(vector<int>& nums) {
  queue<TreeNode*> q;
  int i = 0;
  TreeNode* root = new TreeNode(nums[ i]);
  q.push(root);
  i++;
  while (!q.empty()) {
    TreeNode* cur = q.front();
    q.pop();
    if (i < nums.size()) {
      TreeNode* left = new TreeNode(nums[ i]);
      cur->left = left;
      q.push(left);
      i++;
    }
    if (i < nums.size()) {
      TreeNode* right = new TreeNode(nums[ i]);
      cur->right = right;
      q.push(right);
      i++;
    }
  }
  return root;
}

// 层次遍历
void levelOrderTraversal(TreeNode* root) {
  if (!root) return;
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      TreeNode* cur = q.front();
      q.pop();
      cout << cur->val << " ";
      if (cur->left) q.push(cur->left);
      if (cur->right) q.push(cur->right);
    }
    cout << endl;
  }
}

// 顺序存储结构转链式存储结构(递归)
void inorderTraversal(TreeNode* root, vector<TreeNode*>& v) {
  if (!root) return;
  inorderTraversal(root->left, v);
  v.push_back(root);
  inorderTraversal(root->right, v);
}
void convertToLinkedListRec(TreeNode* root) {
  if (!root) return;
  vector<TreeNode*> v;
  inorderTraversal(root, v);
  for (int i = 0; i < v.size() - 1; i++) {
    v[ i]->right = v[i + 1];
  }
}

// 顺序存储结构转链式存储结构(非递归)
void convertToLinkedListIter(TreeNode* root) {
  if (!root) return;
  stack<TreeNode*> s;
  TreeNode* cur = root;
  TreeNode* pre = nullptr;
  while (!s.empty() || cur) {
    while (cur) {
      s.push(cur);
      cur = cur->left;
    }
    cur = s.top();
    s.pop();
    if (pre) pre->right = cur;
    pre = cur;
    cur = cur->right;
  }
}

// 二叉树顶部垂直输出
void verticalTraversal(TreeNode* root) {
  if (!root) return;
  map<int, vector<int>> mp;
  queue<pair<TreeNode*, int>> q;
  q.push({root, 0});
  while (!q.empty()) {
    auto [cur, col] = q.front();
    q.pop();
    mp[col].push_back(cur->val);
    if (cur->left) q.push({cur->left, col - 1});
    if (cur->right) q.push({cur->right, col + 1});
  }
  for (auto it : mp) {
    for (auto x : it.second) cout << x << " ";
    cout << endl;
  }
}

// 前序遍历(递归)
void preorderTraversalRec(TreeNode* root) {
  if (!root) return;
  cout << root->val << " ";
  preorderTraversalRec(root->left);
  preorderTraversalRec(root->right);
}

// 前序遍历(非递归)
void preorderTraversalIter(TreeNode* root) {
  if (!root) return;
  stack<TreeNode*> s;
  s.push(root);
  while (!s.empty()) {
    TreeNode* cur = s.top();
    s.pop();
    cout << cur->val << " ";
    if (cur->right) s.push(cur->right);
    if (cur->left) s.push(cur->left);
  }
}

// 中序遍历(递归)
void inorderTraversalRec(TreeNode* root) {
  if (!root) return;
  inorderTraversalRec(root->left);
  cout << root->val << " ";
  inorderTraversalRec(root->right);
}

// 中序遍历(非递归)
void inorderTraversalIter(TreeNode* root) {
  if (!root) return;
  stack<TreeNode*> s;
  TreeNode* cur = root;
  while (!s.empty() || cur) {
    while (cur) {
      s.push(cur);
      cur = cur->left;
    }
    cur = s.top();
    s.pop();
    cout << cur->val << " ";
    cur = cur->right;
  }
}

// 后序遍历(递归)
void postorderTraversalRec(TreeNode* root) {
  if (!root) return;
  postorderTraversalRec(root->left);
  postorderTraversalRec(root->right);
  cout << root->val << " ";
}

// 后序遍历(非递归)
void postorderTraversalIter(TreeNode* root) {
  if (!root) return;
  stack<TreeNode*> s1, s2;
  TreeNode* cur = root;
  s1.push(cur);
  while (!s1.empty()) {
    cur = s1.top();
    s1.pop();
    s2.push(cur);
    if (cur->left) s1.push(cur->left);
    if (cur->right) s1.push(cur->right);
  }
  while (!s2.empty()) {
    cur = s2.top();
    s2.pop();
    cout << cur->val << " ";
  }
}

// 前序遍历创建二叉树
TreeNode* createBinaryTreeByPreorder(vector<int>& preorder) {
  stack<TreeNode*> s;
  TreeNode* root = new TreeNode(preorder[0]);
  s.push(root);
  for (int i = 1; i < preorder.size(); i++) {
    TreeNode* cur = new TreeNode(preorder[ i]);
    if (cur->val < s.top()->val) {
      s.top()->left = cur;
    } else {
      TreeNode* pre = nullptr;
      while (!s.empty() && cur->val > s.top()->val) {
        pre = s.top();
        s.pop();
      }
      pre->right = cur;
    }
    s.push(cur);
  }
  return root;
}

// 前序遍历实现快速排序
void quickSort(vector<int>& nums, int l, int r) {
  if (l >= r) return;
  int i = l, j = r, pivot = nums[l];
  while (i < j) {
    while (i < j && nums[j] >= pivot) j--;
    nums[ i] = nums[j];
    while (i < j && nums[ i] <= pivot) i++;
    nums[j] = nums[ i];
  }
  nums[ i] = pivot;
  quickSort(nums, l, i - 1);
  quickSort(nums, i + 1, r);
}

void quickSortByPreorderRec(TreeNode* root, vector<int>& nums, int& i) {
  if (!root) return;
  nums.push_back(root->val);
  quickSortByPreorderRec(root->left, nums, i);
  quickSortByPreorderRec(root->right, nums, i);
}

// 求幂集
vector<vector<int>> powerSet(vector<int>& nums) {
  vector<vector<int>> res;
  int n = nums.size();
  for (int i = 0; i < pow(2, n); i++) {
    vector<int> cur;
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) {
        cur.push_back(nums[j]);
      }
    }
    res.push_back(cur);
  }
  return res;
}

void powerSetByPreorderRec(TreeNode* root, vector<int>& nums, vector<vector<int>>& res) {
  if (!root) return;
  nums.push_back(root->val);
  if (!root->left && !root->right) {
    res.push_back(nums);
  }
  powerSetByPreorderRec(root->left, nums, res);
  powerSetByPreorderRec(root->right, nums, res);
  nums.pop_back();
}

// 汉诺塔
void hanoi(int n, char A, char B, char C) {
  if (n == 1) {
    cout << "move 1 from " << A << " to " << C << endl;
    return;
  }
  hanoi(n - 1, A, C, B);
  cout << "move " << n << " from " << A << " to " << C << endl;
  hanoi(n - 1, B, A, C);
}

void hanoiByPreorderRec(TreeNode* root, char A, char B, char C) {
  if (!root) return;
  hanoiByPreorderRec(root->left, A, C, B);
  cout << "move " << root->val << " from " << A << " to " << C << endl;
  hanoiByPreorderRec(root->right, B, A, C);
}

// 求树的高度(递归)
int heightOfBinaryTreeRec(TreeNode* root) {
  if (!root) return 0;
  return max(heightOfBinaryTreeRec(root->left), heightOfBinaryTreeRec(root->right)) + 1;
}

// 复制二叉树(递归)
TreeNode* copyBinaryTreeRec(TreeNode* root) {
  if (!root) return nullptr;
  TreeNode* newRoot = new TreeNode(root->val);
  newRoot->left = copyBinaryTreeRec(root->left);
  newRoot->right = copyBinaryTreeRec(root->right);
  return newRoot;
}

// 根据前序和中序序列建立二叉树
TreeNode* buildTreeByPreorderAndInorder(vector<int>& preorder, vector<int>& inorder) {
  if (preorder.size() == 0) return nullptr;
  TreeNode* root = new TreeNode(preorder[0]);
  int index = 0;
  while (inorder[index] != preorder[0]) index++;
  vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
  vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());
  vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + index + 1);
  vector<int> rightPreorder(preorder.begin() + index + 1, preorder.end());
  root->left = buildTreeByPreorderAndInorder(leftPreorder, leftInorder);
  root->right = buildTreeByPreorderAndInorder(rightPreorder, rightInorder);
  return root;
}

int main() {
  // 1、用创建结点方法创建二叉树
  vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
  TreeNode* tree = createBinaryTree(nums);

  // 2、层次遍历
  levelOrderTraversal(tree);

  // 3、将二叉树的顺序存储结构转换为链式存储结构(递归)
  convertToLinkedListRec(tree);

  // 3、将二叉树的顺序存储结构转换为链式存储结构(非递归)
  convertToLinkedListIter(tree);

  // 4、垂直输出二叉树
  verticalTraversal(tree);

  // 5、二叉树前序遍历的递归和非递归算法实现
  preorderTraversalRec(tree);
  cout << endl;
  preorderTraversalIter(tree);
  cout << endl;

  // 5、二叉树中序遍历的递归和非递归算法实现
  inorderTraversalRec(tree);
  cout << endl;
  inorderTraversalIter(tree);
  cout << endl;

  // 5、二叉树后序遍历的递归和非递归算法实现
  postorderTraversalRec(tree);
  cout << endl;
  postorderTraversalIter(tree);
  cout << endl;

  // 6、用前序遍历算法创建二叉树
  vector<int> preorder = {8, 3, 1, 6, 5, 7, 10, 14, 13};
  TreeNode* tree2 = createBinaryTreeByPreorder(preorder);

  // 7、二叉树前序遍历应用：快速排序递归算法
  vector<int> nums2 = {3, 5, 4, 1, 2, 6};
  int i = 0;
  vector<int> numsSorted;
  quickSortByPreorderRec(tree, numsSorted, i);
  for (auto x : numsSorted) cout << x << " ";
  cout << endl;
  quickSort(nums2, 0, nums2.size() - 1);
  for (auto x : nums2) cout << x << " ";
  cout << endl;

  // 8、二叉树前序遍历应用：求幂集递归算法
  vector<int> nums3 = {1, 2, 3};
  vector<vector<int>> powerSetRes = powerSet(nums3);
  for (auto x : powerSetRes) {
    for (auto y : x) cout << y << " ";
    cout << endl;
  }
  vector<int> nums4;
  vector<vector<int>> powerSetRes2;
  powerSetByPreorderRec(tree, nums4, powerSetRes2);
  for (auto x : powerSetRes2) {
    for (auto y : x) cout << y << " ";
    cout << endl;
  }

  // 9、二叉树前序遍历应用：汉诺塔问题递归算法
  hanoi(3, 'A', 'B', 'C');
  hanoiByPreorderRec(tree, 'A', 'B', 'C');

  // 10、用递归算法求二叉树的高度
  int height = heightOfBinaryTreeRec(tree);
  cout << "height: " << height << endl;

  // 11、用递归算法完成两个二叉树的复制
  TreeNode* treeCopy = copyBinaryTreeRec(tree);
  levelOrderTraversal(treeCopy);

  // 12、由前序和中序序列建立二叉树
  vector<int> inorder = {4, 2, 5, 1, 6, 7, 3, 8};
  TreeNode* tree3 = buildTreeByPreorderAndInorder(preorder, inorder);
  levelOrderTraversal(tree3);

  return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-2-24 00:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表