C++ 实现二叉树基本运算及应用示例

本示例使用 C++ 语言实现二叉树的基本运算，包括创建、输出、查找节点、计算高度和释放内存等功能。示例中使用字符串表示二叉树结构，并通过创建相应的二叉链存储结构进行操作。

btree.cpp 代码如下：

#include <iostream>
using namespace std;

// 二叉树结点的定义
struct Node {
    char data;
    Node* left;
    Node* right;
};

// 创建二叉树
void createTree(Node* &root, char* str, int& index) {
    if (str[index] == '\0') {
        root = NULL;
        return;
    }
    if (str[index] == '(') {
        index++;
        if (str[index] == ')') {
            root = NULL;
            index++;
            return;
        }
        root = new Node;
        root->data = str[index];
        root->left = NULL;
        root->right = NULL;
        createTree(root->left, str, ++index);
        createTree(root->right, str, ++index);
    } else {
        index++;
        createTree(root, str, index);
    }
}

// 输出二叉树
void printTree(Node* root) {
    if (root == NULL) return;
    cout << root->data;
    if (root->left != NULL || root->right != NULL) {
        cout << '(';
        printTree(root->left);
        cout << ',';
        printTree(root->right);
        cout << ')';
    }
}

// 获取结点指针
Node* getNode(Node* root, char c) {
    if (root == NULL) return NULL;
    if (root->data == c) return root;
    Node* p = getNode(root->left, c);
    if (p != NULL) return p;
    return getNode(root->right, c);
}

// 获取二叉树高度
int getHeight(Node* root) {
    if (root == NULL) return 0;
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 释放二叉树内存
void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main() {
    char str[] = 'A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))) ';
    Node* root;
    int index = 0;
    createTree(root, str, index);

    cout << '二叉树b: ';
    printTree(root);
    cout << endl;

    Node* h = getNode(root, 'H');
    if (h == NULL) {
        cout << '未找到结点H' << endl;
    } else {
        cout << '结点H的左孩子值为：' << h->left->data << endl;
        cout << '结点H的右孩子值为：' << h->right->data << endl;
    }

    int height = getHeight(root);
    cout << '二叉树b的高度为：' << height << endl;

    freeTree(root);
    return 0;
}

exp1.cpp 代码如下：

#include <iostream>
using namespace std;

// 二叉树结点的定义
struct Node {
    char data;
    Node* left;
    Node* right;
};

// 创建二叉树
void createTree(Node* &root, char* str, int& index) {
    if (str[index] == '\0') {
        root = NULL;
        return;
    }
    if (str[index] == '(') {
        index++;
        if (str[index] == ')') {
            root = NULL;
            index++;
            return;
        }
        root = new Node;
        root->data = str[index];
        root->left = NULL;
        root->right = NULL;
        createTree(root->left, str, ++index);
        createTree(root->right, str, ++index);
    } else {
        index++;
        createTree(root, str, index);
    }
}

// 输出二叉树
void printTree(Node* root) {
    if (root == NULL) return;
    cout << root->data;
    if (root->left != NULL || root->right != NULL) {
        cout << '(';
        printTree(root->left);
        cout << ',';
        printTree(root->right);
        cout << ')';
    }
}

// 获取结点指针
Node* getNode(Node* root, char c) {
    if (root == NULL) return NULL;
    if (root->data == c) return root;
    Node* p = getNode(root->left, c);
    if (p != NULL) return p;
    return getNode(root->right, c);
}

// 获取二叉树高度
int getHeight(Node* root) {
    if (root == NULL) return 0;
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 释放二叉树内存
void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main() {
    char str[] = 'A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))) ';
    Node* root;
    int index = 0;
    createTree(root, str, index);

    cout << '二叉树b: ';
    printTree(root);
    cout << endl;

    Node* h = getNode(root, 'H');
    if (h == NULL) {
        cout << '未找到结点H' << endl;
    } else {
        cout << '结点H的左孩子值为：' << h->left->data << endl;
        cout << '结点H的右孩子值为：' << h->right->data << endl;
    }

    int height = getHeight(root);
    cout << '二叉树b的高度为：' << height << endl;

    freeTree(root);
    return 0;
}

示例代码功能：

创建二叉树: createTree 函数根据字符串表示的二叉树结构创建相应的二叉链存储结构。
输出二叉树: printTree 函数以括号表示法输出二叉树。
查找节点: getNode 函数根据节点值查找对应的节点指针。
计算高度: getHeight 函数计算二叉树的高度。
释放内存: freeTree 函数释放二叉树占用的内存空间。

使用示例：

示例代码中使用字符串 'A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))' 表示二叉树结构，程序会创建相应的二叉树，并执行查找节点 'H'，输出高度以及释放内存等操作。

注意：

该示例代码仅提供了一个简单的二叉树实现，可以根据实际需要进行扩展，例如添加其他操作，如插入节点、删除节点等。