【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】

// 二叉树节点结构体定义
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);
}

// 求二叉树高度的函数
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;
}

// 输出二叉树（以中序遍历为例）的函数
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;
}

#include <iostream>
#include <string>
#define Maxsize 100
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;
}