数据结构与算法--树与二叉树的代码实现（C语言）

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 注意：一棵树用它的根结点来表示，因为只要有根结点，就能访问整棵树

// 二叉树先序(前序)遍历的递归实现
#include 
void PreTraverse(TreeNode *node) {
    if (!node) {
        return;  // 递归出口
    }
    printf("%dn", node->data);  // 先访问当前结点
    PreTraverse(node->left);     // 其次递归遍历左子树
    PreTraverse(node->right);    // 最后递归遍历右子树
}

// 二叉树中序遍历的递归实现
void MidTraverse(TreeNode *node) {
    if (!node) {
        return;  // 递归出口
    }
    MidTraverse(node->left);     // 先递归遍历左子树
    printf("%dn", node->data);  // 其次访问当前结点
    MidTraverse(node->right);    // 最后递归遍历右子树
}

// 二叉树后序遍历的递归实现
void PostTraverse(TreeNode *node) {
    if (!node) {
        return;  // 递归出口
    }
    PostTraverse(node->left);    // 先递归遍历左子树
    PostTraverse(node->right);   // 其次递归遍历右子树
    printf("%dn", node->data);  // 最后访问根结点
}

// 求树的高度(深度)的递归实现
int GetHeight(TreeNode *node) {
    if (!node) {
        return 0;
    }
    int lh = GetHeight(node->left);
    int rh = GetHeight(node->right);
    // 返回 1 + 左右子树中高度较大者，这里1是指当前结点贡献1个高度
    return 1 + (lh > rh ? lh : rh);
}

// 二叉树的层序遍历(利用队列)
#include 
void LevelTraverse(TreeNode *node) {
    if (!node) {
        return;
    }

    std::queue q;  // 队列元素是TreeNode*
    q.push(node);
    while (!q.empty()) {
        TreeNode *cur = q.front();  // 获取当前队首
        printf("%dn", cur->data);  // 访问之
        q.pop();                    // 队首离开队伍
        if (cur->left) {
            q.push(cur->left);  // 左孩子(若有)入队
        }
        if (cur->right) {
            q.push(cur->right);  // 右孩子(若有)入队
        }
    }
}