ZBLOG

实现二叉树类的设计,要求具有的功能:1)根据二叉树括号表示法根据字符串str生成对应的二叉链存储结构b,二叉树括号表示串中只有4类字符:‘(‘、‘)’,‘,’和A-Z字母,如"A(B(D(,G)),C(E,F))",一般在构造函数中实现;2)销毁二叉链存储结构Release():销毁二叉链b并释放空间,一般在析构函数中实现;3)查找结点Find(x):在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针;4)求高度Height():求二叉树b的高度;5)(选做)设置结点的其他数据...

下面是一个示例的二叉树类设计,实现了所要求的功能:

  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. struct TreeNode {
  5. char data; // 结点数据
  6. int data2; // 结点其他数据域
  7. TreeNode* left; // 左子结点指针
  8. TreeNode* right; // 右子结点指针
  9. TreeNode(char d, int d2) : data(d), data2(d2), left(nullptr), right(nullptr) {}
  10. };
  11. class BinaryTree {
  12. private:
  13. TreeNode* root; // 根结点指针
  14. public:
  15. BinaryTree(const string& str) {
  16. root = nullptr;
  17. buildTree(str);
  18. }
  19. ~BinaryTree() {
  20. Release();
  21. }
  22. void Release() {
  23. destroy(root);
  24. root = nullptr;
  25. }
  26. TreeNode* Find(char x) {
  27. return findNode(root, x);
  28. }
  29. int Height() {
  30. return getHeight(root);
  31. }
  32. void SetNode(char x, int y) {
  33. setNodeData2(root, x, y);
  34. }
  35. void Disp() {
  36. display(root);
  37. cout << endl;
  38. }
  39. private:
  40. // 根据括号表示法构建二叉树
  41. TreeNode* buildTree(const string& str) {
  42. stack<TreeNode*> s;
  43. TreeNode* p = nullptr;
  44. bool isLeftChild = true;
  45. for (char c : str) {
  46. if (c == '(') { // 左括号,创建左子结点
  47. s.push(p);
  48. isLeftChild = true;
  49. } else if (c == ')') { // 右括号,回退到父结点
  50. s.pop();
  51. } else if (c == ',') { // 逗号,创建右子结点
  52. isLeftChild = false;
  53. } else {
  54. p = new TreeNode(c, 0);
  55. if (root == nullptr) { // 第一个结点作为根结点
  56. root = p;
  57. } else {
  58. if (isLeftChild) {
  59. s.top()->left = p; // 连接到父结点的左子结点
  60. } else {
  61. s.top()->right = p; // 连接到父结点的右子结点
  62. }
  63. }
  64. }
  65. }
  66. return root;
  67. }
  68. void destroy(TreeNode* node) {
  69. if (node != nullptr) {
  70. destroy(node->left);
  71. destroy(node->right);
  72. delete node;
  73. }
  74. }
  75. TreeNode* findNode(TreeNode* node, char x) {
  76. if (node == nullptr || node->data == x) {
  77. return node;
  78. }
  79. TreeNode* leftResult = findNode(node->left, x); // 在左子树中查找
  80. TreeNode* rightResult = findNode(node->right, x); // 在右子树中查找
  81. return leftResult ? leftResult : rightResult; // 返回结果(如果在左子树中找到则返回左子树结果,否则返回右子树结果)
  82. }
  83. int getHeight(TreeNode* node) {
  84. if (node == nullptr) {
  85. return 0;
  86. }
  87. int leftHeight = getHeight(node->left); // 左子树高度
  88. int rightHeight = getHeight(node->right); // 右子树高度
  89. return max(leftHeight, rightHeight) + 1; // 返回较大的子树高度加1
  90. }
  91. void setNodeData2(TreeNode* node, char x, int y) {
  92. if (node != nullptr) {
  93. if (node->data == x) { // 如果找到目标结点,设置data2值
  94. node->data2 = y;
  95. }
  96. setNodeData2(node->left, x, y); // 在左子树中递归查找并设置
  97. setNodeData2(node->right, x, y); // 在右子树中递归查找并设置
  98. }
  99. }
  100. void display(TreeNode* node) {
  101. if (node != nullptr) {
  102. cout << "<" << node->data << "," << node->data2 << ">";
  103. if (node->left || node->right) { // 如果有子结点,输出括号
  104. cout << "(";
  105. display(node->left); // 输出左子树
  106. if (node->right) {
  107. cout << ",";
  108. display(node->right); // 输出右子树
  109. }
  110. cout << ")";
  111. }
  112. }
  113. }
  114. };
  115. int main() {
  116. string str = "A(B(D(,G)),C(E,F))";
  117. BinaryTree tree(str);
  118. tree.Disp();
  119. TreeNode* foundNode = tree.Find('D');
  120. if (foundNode != nullptr)
  121. cout << "Found Node: <" << foundNode->data << "," << foundNode->data2 << ">" << endl;
  122. int height = tree.Height();
  123. cout << "Tree Height: " << height << endl;
  124. tree.SetNode('B', 10);
  125. tree.Disp();
  126. return 0;
  127. }

这个示例中实现了二叉树类,可以根据括号表示法的字符串构建二叉树,支持销毁二叉链存储结构、查找结点、求高度、设置其他数据域以及输出二叉树等功能。在括号表示法中,左括号’(‘表示创建左子结点,右括号’)‘表示回退到父结点,逗号’,‘表示创建右子结点。


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

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

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

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

联系我们

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

微信号:3007537140

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

关注我们
x

注册

已经有帐号?