ZBLOG

#include using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; bool isThreaded; // 标记是否为线索 }; // 中序遍历线索化二叉树 void inorderThreading(TreeNode* root, TreeNode*& prev) { if (root == nullptr) return; ino...

根据您提供的代码,我注意到在插入节点时存在一些问题。请注意以下几点:

  1. insertNodeInThreadedTree函数中,第一个判断条件应该是if (position == 0 && curr->isThreaded && curr->left != nullptr && curr->left->isThreaded)而不是position == 1。因为位置编号是从0开始计数的。

  2. 在第二个判断条件中,也需要修改为if (position == 1 && curr->isThreaded && curr->right != nullptr && curr->right->isThreaded)以适应从0开始计数的位置编号。

  3. 在遍历过程中,在输出节点值之后,应先检查右孩子是否为线索(通过!curr -> right -> isThreaded),如果不是,则将当前指针移至右孩子;否则,将指针置为空。

  4. 在主函数结束前,请确保释放动态分配的内存,避免内存泄漏。

修正后的代码如下:

  1. #include <iostream>
  2. using namespace std;
  3. struct TreeNode {
  4. int val;
  5. TreeNode* left;
  6. TreeNode* right;
  7. bool isThreaded; // 标记是否为线索
  8. };
  9. // 中序遍历线索化二叉树
  10. void inorderThreading(TreeNode* root, TreeNode*& prev) {
  11. if (root == nullptr)
  12. return;
  13. inorderThreading(root->left, prev);
  14. if (root->left == nullptr) {
  15. root->left = prev;
  16. root->isThreaded = true;
  17. }
  18. if (prev != nullptr && prev->right == nullptr) {
  19. prev->right = root;
  20. prev->isThreaded = true;
  21. }
  22. prev = root;
  23. inorderThreading(root->right, prev);
  24. }
  25. // 在线索二叉树中插入结点
  26. void insertNodeInThreadedTree(TreeNode*& root, int position, int value) {
  27. if (root == nullptr)
  28. return;
  29. TreeNode* newNode = new TreeNode();
  30. newNode->val = value;
  31. TreeNode* curr = root; // 当前结点指针
  32. while (curr != nullptr) {
  33. // 判断当前位置是否为指定位置
  34. if (position == 0 && curr->isThreaded && curr->left != nullptr && curr->left->isThreaded) {
  35. newNode->left = curr->left; // 新节点的左孩子为当前结点的前驱(线索)
  36. newNode->right = curr; // 新节点的右孩子为当前结点
  37. curr->left = newNode; // 当前结点的前驱指向新节点
  38. curr->isThreaded = false; // 当前结点不再为线索
  39. return;
  40. }
  41. else if (position == 1 && curr->isThreaded && curr->right != nullptr && curr->right -> isThreaded) {
  42. newNode -> right=curr -> right; // 新节点的右孩子为当前结点的后继(线索)
  43. newNode -> left=curr; // 新节点的左孩子为当前结点
  44. curr -> right=newNode; // 当前结点的后继指向新节点
  45. curr -> isThreaded=false; // 当前结点不再为线索
  46. return;
  47. }
  48. if (!curr->isThreaded)
  49. position -= 2;
  50. if (curr->left != nullptr && !curr->left->isThreaded)
  51. position--;
  52. if (position > 0) {
  53. if (curr == root || !curr->isThreaded)
  54. position--;
  55. curr = curr->right;
  56. }
  57. else {
  58. curr = curr->left;
  59. }
  60. }
  61. }
  62. // 中序遍历输出线索二叉树(用于验证结果)
  63. void inorderTraversal(TreeNode* root) {
  64. TreeNode* curr = root;
  65. while (curr != nullptr) {
  66. while (curr->left != nullptr && !curr -> left -> isThreaded)
  67. curr = curr -> left;
  68. cout << curr -> val << " ";
  69. if (!curr -> isThreaded)
  70. curr = curr -> right;
  71. else
  72. curr= nullptr;
  73. }
  74. }
  75. int main() {
  76. TreeNode* root = new TreeNode();
  77. root->val = 5;
  78. root->isThreaded = false;
  79. TreeNode* left1 = new TreeNode();
  80. left1->val = 3;
  81. left1->isThreaded = true;
  82. TreeNode* right1 = new TreeNode();
  83. right1->val = 8;
  84. right1->isThreaded = true;
  85. TreeNode* left2 = new TreeNode();
  86. left2->val = 2;
  87. left2->isThreaded = true;
  88. TreeNode* right2= new TreeNode();
  89. right2 -> val=4;
  90. right2 -> isThreaded=true;
  91. TreeNode* left3=new TreeNode();
  92. left3 -> val=6;
  93. left3 -> isThreaded=true;
  94. TreeNode*right3=new TreeNode();
  95. right3 -> val=9;
  96. right3 -> isThreaded=true;
  97. root ->left=left1;
  98. root ->right=right1;
  99. left1 ->left=left2;
  100. left1 ->right=right2;
  101. right1 ->left=left3;
  102. right1 ->right=right3;
  103. cout << "插入前的线索二叉树:";
  104. inorderTraversal(root);
  105. insertNodeInThreadedTree(root, 4, 7); // 在第4个位置(即节点值为6)后插入值为7的节点
  106. cout << endl << "插入后的线索二叉树:";
  107. inorderTraversal(root);
  108. delete root;
  109. delete left1;
  110. delete right1;
  111. delete left2;
  112. delete right2;
  113. delete left3;
  114. delete right3;
  115. return 0;
  116. }

现在代码已经修复,应该可以正确运行了。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=16011

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?