有下图所示的二叉树,编写一个程序btree.cpp, 实现二叉树的基本运算，在此基础上编写一个程序exp5-1.c, 实现下面的各项功能。 （1）根据上图所示二叉树的括号表示串为“ A（B（D，E（G，H）），C（，F（K）））,创建该二叉树的链式存储，并输出该二叉树； （2）求该二叉树的高度； （3）求该二叉树的总结点数； （4）求该二叉树的叶子结点数； （5）判断并输出结点E是否是树中结点； （6）输出该二叉树的先序遍历的序列； （7）输出该二叉树的中序遍历的序列； （8）销毁该二叉树。

### 编写二叉树程序实现基本操作 以下是基于C++和C两种语言分别编写的二叉树程序，涵盖了创建链式存储、输出二叉树、求高度、总结点数、叶子结点数、判断节点是否存在、先序和中序遍历以及销毁二叉树等功能。 --- #### **C++版本 (btree.cpp)** ```cpp #include <iostream> #include <cstring> using namespace std; // 定义二叉树节点结构体 struct BTNode { char data; BTNode* lchild; BTNode* rchild; }; // 创建二叉树（通过字符串构建） void CreateBTNode(BTNode*& b, const string& str) { static unsigned int index = 0; // 静态变量用于记录当前解析位置 if (index >= str.length()) return; char ch = str[index++]; if (ch == ',') { // 空节点 b = nullptr; } else if (ch != '(' && ch != ')') { // 构建新节点 b = new BTNode{ch, nullptr, nullptr}; if (str[index] == '(') { // 左子树 ++index; CreateBTNode(b->lchild, str); } if (str[index] == ',') { // 右子树 ++index; CreateBTNode(b->rchild, str); } if (str[index] == ')') { // 结束标志 ++index; } } } // 输出二叉树（括号表示法） void DispBTNode(const BTNode* b) { if (!b) return; cout << b->data; if (b->lchild || b->rchild) { cout << "("; DispBTNode(b->lchild); if (b->rchild) cout << ","; DispBTNode(b->rchild); cout << ")"; } } // 计算二叉树的高度 int BTNodeDepth(const BTNode* b) { if (!b) return 0; int leftHeight = BTNodeDepth(b->lchild); int rightHeight = BTNodeDepth(b->rchild); return max(leftHeight, rightHeight) + 1; } // 统计总结点数 int CountNodes(const BTNode* b) { if (!b) return 0; return CountNodes(b->lchild) + CountNodes(b->rchild) + 1; } // 统计叶子结点数 int LeafCount(const BTNode* b) { if (!b) return 0; if (!b->lchild && !b->rchild) return 1; return LeafCount(b->lchild) + LeafCount(b->rchild); } // 判断节点是否存在 bool FindNode(const BTNode* b, char x) { if (!b) return false; if (b->data == x) return true; return FindNode(b->lchild, x) || FindNode(b->rchild, x); } // 先序遍历 void PreOrderTraverse(const BTNode* b) { if (!b) return; cout << b->data << " "; PreOrderTraverse(b->lchild); PreOrderTraverse(b->rchild); } // 中序遍历 void InOrderTraverse(const BTNode* b) { if (!b) return; InOrderTraverse(b->lchild); cout << b->data << " "; InOrderTraverse(b->rchild); } // 销毁二叉树 void DestroyBTNode(BTNode*& b) { if (!b) return; DestroyBTNode(b->lchild); DestroyBTNode(b->rchild); delete b; b = nullptr; } ``` --- #### **C版本 (exp5-1.c)** ```c #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node { char data; struct Node* lchild; struct Node* rchild; } BTNode; static size_t index = 0; // 创建二叉树（通过字符串构建） void CreateBTNode(BTNode** b, const char* str) { if (*str == '\0' || index >= strlen(str)) return; char ch = str[index++]; if (ch == ',') { // 空节点 *b = NULL; } else if (ch != '(' && ch != ')') { // 构建新节点 *b = (BTNode*)malloc(sizeof(BTNode)); (*b)->data = ch; (*b)->lchild = NULL; (*b)->rchild = NULL; if (str[index] == '(') { // 左子树 ++index; CreateBTNode(&((*b)->lchild), str); } if (str[index] == ',') { // 右子树 ++index; CreateBTNode(&((*b)->rchild), str); } if (str[index] == ')') { // 结束标志 ++index; } } } // 输出二叉树（括号表示法） void DispBTNode(const BTNode* b) { if (!b) return; printf("%c", b->data); if (b->lchild || b->rchild) { putchar('('); DispBTNode(b->lchild); if (b->rchild) putchar(','); DispBTNode(b->rchild); putchar(')'); } } // 计算二叉树的高度 int BTNodeDepth(const BTNode* b) { if (!b) return 0; int leftHeight = BTNodeDepth(b->lchild); int rightHeight = BTNodeDepth(b->rchild); return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; } // 统计总结点数 int CountNodes(const BTNode* b) { if (!b) return 0; return CountNodes(b->lchild) + CountNodes(b->rchild) + 1; } // 统计叶子结点数 int LeafCount(const BTNode* b) { if (!b) return 0; if (!(b->lchild) && !(b->rchild)) return 1; return LeafCount(b->lchild) + LeafCount(b->rchild); } // 判断节点是否存在 int FindNode(const BTNode* b, char x) { if (!b) return 0; if (b->data == x) return 1; return FindNode(b->lchild, x) || FindNode(b->rchild, x); } // 先序遍历 void PreOrderTraverse(const BTNode* b) { if (!b) return; printf("%c ", b->data); PreOrderTraverse(b->lchild); PreOrderTraverse(b->rchild); } // 中序遍历 void InOrderTraverse(const BTNode* b) { if (!b) return; InOrderTraverse(b->lchild); printf("%c ", b->data); InOrderTraverse(b->rchild); } // 销毁二叉树 void DestroyBTNode(BTNode* b) { if (!b) return; DestroyBTNode(b->lchild); DestroyBTNode(b->rchild); free(b); } ``` --- 以上代码实现了二叉树的基本操作，包括但不限于创建链式存储、输出二叉树、计算高度、统计总结点数和叶子结点数、判断节点存在性、先序/中序遍历以及销毁二叉树的功能[^1][^2][^3]。 --- ###