[leetcode]树的操作

一.定义二叉树的结构

// 定义二叉树结构
typedef struct node {
    char ch;
    node* LChild;
    node* RChild;
} TiTNode, * BiTree;

二.创建BiTree

// 创建BiTree
void createTree(BiTree& bt) {
    char ch;
    cin >> ch;
    if (ch == '#') {
        bt = NULL;
    }
    else {
        bt = new node;
        bt->ch = ch;
        createTree(bt->LChild);
        createTree(bt->RChild);
    }
}

三.访问节点数据

// 访问节点数据
void visit(char ch) {
    cout << ch << " ";
}

四.先序遍历

// 先序遍历
void PreOrder(BiTree root) {
    if (root != NULL) {
        visit(root->ch);
        PreOrder(root->LChild);
        PreOrder(root->RChild);
    }
}

五. 中序遍历

// 中序遍历
void InOrder(BiTree root) {
    if (root != NULL) {
        InOrder(root->LChild);
        visit(root->ch);
        InOrder(root->RChild);
    }
}

六.后序遍历

// 后序遍历
void PostOrder(BiTree root) {
    if (root != NULL) {
        PostOrder(root->LChild);
        PostOrder(root->RChild);
        visit(root->ch);
    }
}

七.后序遍历求二叉树的高度

// 后序遍历求二叉树的高度
int PostTreeDepth(BiTree bt) {
    if (bt == NULL) {
        return 0;
    }
    int hl = PostTreeDepth(bt->LChild);
    int hr = PostTreeDepth(bt->RChild);
    return (hl > hr ? hl : hr) + 1;
}

八.先序遍历求二叉树的高度

// 先序遍历求二叉树的高度
int PreTreeDepth(BiTree bt) {
    if (bt == NULL) {
        return 0;
    }
    int hl = PreTreeDepth(bt->LChild);
    int hr = PreTreeDepth(bt->RChild);
    return (hl > hr ? hl : hr) + 1;
}

九.计算二叉树的叶子节点的个数

//计算二叉树的叶子节点的个数
void caculateLeaves(BiTree bt,int* leaf)
{
    if (bt != NULL)
    {
        if (bt->LChild == NULL && bt->RChild == NULL)
        {
            (*leaf)++;
        }
        caculateLeaves(bt->LChild, leaf);
        caculateLeaves(bt->RChild, leaf);
    }
    else
    {
        return;
    }
}

Coding:

#include <iostream>
using namespace std;

// 定义二叉树结构
typedef struct node {
    char ch;
    node* LChild;
    node* RChild;
} TiTNode, * BiTree;

// 创建BiTree
void createTree(BiTree& bt) {
    char ch;
    cin >> ch;
    if (ch == '#') {
        bt = NULL;
    }
    else {
        bt = new node;
        bt->ch = ch;
        createTree(bt->LChild);
        createTree(bt->RChild);
    }
}

// 访问节点数据
void visit(char ch) {
    cout << ch << " ";
}

// 先序遍历
void PreOrder(BiTree root) {
    if (root != NULL) {
        visit(root->ch);
        PreOrder(root->LChild);
        PreOrder(root->RChild);
    }
}

// 中序遍历
void InOrder(BiTree root) {
    if (root != NULL) {
        InOrder(root->LChild);
        visit(root->ch);
        InOrder(root->RChild);
    }
}

// 后序遍历
void PostOrder(BiTree root) {
    if (root != NULL) {
        PostOrder(root->LChild);
        PostOrder(root->RChild);
        visit(root->ch);
    }
}

// 后序遍历求二叉树的高度
int PostTreeDepth(BiTree bt) {
    if (bt == NULL) {
        return 0;
    }
    int hl = PostTreeDepth(bt->LChild);
    int hr = PostTreeDepth(bt->RChild);
    return (hl > hr ? hl : hr) + 1;
}

// 先序遍历求二叉树的高度
int PreTreeDepth(BiTree bt) {
    if (bt == NULL) {
        return 0;
    }
    int hl = PreTreeDepth(bt->LChild);
    int hr = PreTreeDepth(bt->RChild);
    return (hl > hr ? hl : hr) + 1;
}

//计算二叉树的叶子节点的个数
void caculateLeaves(BiTree bt,int* leaf)
{
    if (bt != NULL)
    {
        if (bt->LChild == NULL && bt->RChild == NULL)
        {
            (*leaf)++;
        }
        caculateLeaves(bt->LChild, leaf);
        caculateLeaves(bt->RChild, leaf);
    }
    else
    {
        return;
    }
}

int main() {
    // 示例输入：ABD##E##CF###
    BiTree root = NULL;
    cout << "Enter the tree structure (use # for null nodes): ";
    createTree(root);

    cout << "PreOrder: ";
    PreOrder(root);
    cout << endl;

    cout << "InOrder: ";
    InOrder(root);
    cout << endl;

    cout << "PostOrder: ";
    PostOrder(root);
    cout << endl;

    int height = PostTreeDepth(root);
    cout << "The height of the tree (PostOrder): " << height << endl;

    height = PreTreeDepth(root);
    cout << "The height of the tree (PreOrder): " << height << endl;

    int leaf = 0;
    caculateLeaves(root,&leaf);
    cout << "The number of leaves is : " << leaf << endl;

    return 0;
}