目录😋
任务描述
本关任务：编写一个程序实现二叉树的基本运算。
相关知识
为了完成本关任务，你需要掌握：
- 创建二叉树
- 销毁二叉树
- 查找结点
- 求二叉树的高度
- 输出二叉树
假设二叉树节点结构体定义如下：
// 二叉树节点结构体定义 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
- 创建二叉树
这里以手动构建一个简单二叉树为例，可以根据实际需求从文件、用户输入等方式获取数据来构建更复杂的二叉树。
// 创建二叉树函数（简单示例，手动构建） TreeNode* createBinaryTree() { TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); return root; }
在上述函数中，通过动态分配内存创建二叉树的各个节点，并按照一定的结构关系（这里构建了一个简单的示例二叉树结构）将节点连接起来，最后返回根节点指针，代表创建好的二叉树。
- 销毁二叉树
为了避免内存泄漏，在不再使用二叉树时，需要释放二叉树占用的内存空间，通过递归遍历二叉树，先释放子节点的内存，再释放根节点内存。
// 销毁二叉树函数（释放二叉树内存） void destroyBinaryTree(TreeNode* root) { if (root == NULL) return; destroyBinaryTree(root->left); destroyBinaryTree(root->right); delete root; }
在这个函数里，首先判断根节点是否为空，如果为空则表示已经遍历完整个树或者本身就是空树，直接返回。然后递归地调用函数先销毁左子树，再销毁右子树，最后释放根节点的内存，确保整个二叉树占用的内存都被正确回收。
- 查找结点
可以通过递归的方式在二叉树中查找指定值的节点，遍历二叉树的每个节点，比较节点值与目标值是否相等。
// 在二叉树中查找指定值的节点函数 TreeNode* findNode(TreeNode* root, int target) { if (root == NULL) return NULL; if (root->val == target) return root; TreeNode* leftResult = findNode(root->left, target); if (leftResult!= NULL) return leftResult; return findNode(root->right, target); }
在上述函数中：
- 首先判断根节点是否为空，为空则表示没找到目标节点，返回
NULL。- 接着比较根节点的值与目标值，如果相等则返回根节点指针。
- 如果根节点值不等于目标值，就先递归地在左子树中查找，若在左子树中找到了（返回的指针不为
NULL），则直接返回找到的节点指针。- 若左子树中没找到，则继续递归在右子树中查找，并返回右子树查找的结果。
- 求二叉树的高度
二叉树的高度定义为根节点到叶节点最长路径上的节点数，可以通过递归计算左子树高度和右子树高度，取较大值再加 1（根节点这一层）来得到整棵树的高度。
// 求二叉树高度的函数 int getHeight(TreeNode* root) { if (root == NULL) return 0; int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); return std::max(leftHeight, rightHeight) + 1; }
在这个函数里：
- 先判断根节点是否为空，为空则表示空树，高度为 0，直接返回 0。
- 然后递归地计算左子树的高度和右子树的高度，通过
std::max函数取两者中的较大值，再加上 1（代表根节点所在的这一层），得到整棵二叉树的高度并返回。
- 输出二叉树
以下是使用中序遍历（可以根据需求选择前序、后序、层次遍历等其他遍历方式）的方式简单输出二叉树节点值的函数示例，方便查看二叉树结构。
// 输出二叉树（以中序遍历为例）的函数 void printBinaryTree(TreeNode* root) { if (root == NULL) return; printBinaryTree(root->left); std::cout << root->val << " "; printBinaryTree(root->right); }
在上述函数中，通过递归实现中序遍历，先递归遍历左子树，然后输出当前节点的值，最后递归遍历右子树，这样就按照中序遍历的顺序输出了二叉树的各个节点值，一定程度上展示了二叉树的结构情况。
以下是一个简单的使用示例，展示如何调用这些函数：
int main() { TreeNode* root = createBinaryTree(); std::cout << "创建的二叉树（中序遍历输出）: "; printBinaryTree(root); std::cout << std::endl; TreeNode* targetNode = findNode(root, 5); if (targetNode!= NULL) { std::cout << "找到节点值为5的节点" << std::endl; } else { std::cout << "未找到节点值为5的节点" << std::endl; } std::cout << "二叉树的高度: " << getHeight(root) << std::endl; destroyBinaryTree(root); return 0; }
测试说明
平台会对你编写的代码进行测试：
测试输入：
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
H
预期输出：
(1)创建二叉树
(2)输出二叉树:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
(3)H结点:左孩子为J 右孩子为K
(4)二叉树b的高度:7
(5)释放二叉树
测试输入：
A(B(D,E(G)),C(,F))
C
预期输出：
(1)创建二叉树
(2)输出二叉树:A(B(D,E(G)),C(,F))
(3)C结点:无左孩子 右孩子为F
(4)二叉树b的高度:4
(5)释放二叉树
开始你的任务吧，祝你成功！
通关代码
using namespace std; typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTNode; void CreateBTree(BTNode *&b, const char *str) { BTNode *St[Maxsize], *p; int top = -1, k, j = 0; char ch; b = NULL; ch = str[j]; while (ch != '\0') { switch (ch) { case '(': top++; St[top] = p; k = 1; break; case ')': top--; break; case ',': k = 2; break; default: p = (BTNode *)malloc(sizeof(BTNode)); p->data = ch; p->lchild = p->rchild = NULL; if (b == NULL) b = p; else { switch (k) { case 1: St[top]->lchild = p; break; case 2: St[top]->rchild = p; break; } } } j++; ch = str[j]; } } void DestroyBtree(BTNode *&b) { if (b != NULL) { DestroyBtree(b->lchild); DestroyBtree(b->rchild); free(b); } } BTNode *FindNode(BTNode *b, ElemType x) { BTNode *p; if (b == NULL) { return NULL; } else if (b->data == x) { return b; } else { p = FindNode(b->lchild, x); if (p != NULL) { return p; } else { return FindNode(b->rchild, x); } } } BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; } int BTHeight(BTNode *b) { int lchildh, rchildh; if (b == NULL) return 0; else { lchildh = BTHeight(b->lchild); rchildh = BTHeight(b->rchild); return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1); } } void DispBTree(BTNode *b) { if (b != NULL) { cout << b->data; if (b->lchild != NULL || b->rchild != NULL) { cout << "("; DispBTree(b->lchild); if (b->rchild != NULL) cout << ","; DispBTree(b->rchild); cout << ")"; } } } int main() { BTNode *b = NULL; string input; char searchValue; getline(cin, input); CreateBTree(b, input.c_str()); cin >> searchValue; cout << "(1)创建二叉树" << endl; cout << "(2)输出二叉树:"; DispBTree(b); cout << endl; cout << "(3)"; BTNode *foundNode = FindNode(b, searchValue); if (foundNode != NULL) { cout << searchValue << "结点:"; if (LchildNode(foundNode) != NULL) { cout << "左孩子为" << LchildNode(foundNode)->data; } else { cout << "无左孩子"; } if (RchildNode(foundNode) != NULL) { cout << " 右孩子为" << RchildNode(foundNode)->data; } else { cout << " 无右孩子"; } cout << endl; } else { cout << "未找到字符" << searchValue << " 的结点。" << endl; } cout << "(4)二叉树b的高度:" << BTHeight(b) << endl; DestroyBtree(b); cout << "(5)释放二叉树" << endl; return 0; }
测试结果
编辑
编辑
