二叉树的基本操作C语言

二叉树是一种非常重要的数据结构，它在计算机科学中有着广泛的应用。下面是二叉树的基本操作C语言实现：

1. 定义二叉树结构体

typedef struct Bitnode {
    Elemtype data;
    Bitnode *lchild, *rchild;
} Bitnode, *Bitree;

2. 前序递归建立二叉树

void Creat(Bitree &T) {
    Elemtype n;
    scanf("%c", &n);
    if (n == '#') {
        T = NULL;
    } else {
        T = (Bitnode *)malloc(sizeof(Bitnode));
        T->data = n;
        T->lchild = NULL;
        T->rchild = NULL;
        Creat(T->lchild);
        Creat(T->rchild);
    }
}

3. 前序递归遍历二叉树

void Preorder(Bitree T) {
    if (T) {
        printf("%c", T->data); // 根
        Preorder(T->lchild);   // 左
        Preorder(T->rchild);   // 右
    }
}

4. 中序递归遍历二叉树

void Inorder(Bitree T) {
    if (T) {
        Inorder(T->lchild);   // 左
        printf("%c", T->data); // 根
        Inorder(T->rchild);   // 右
    }
}

5. 后序递归遍历二叉树

void Postorder(Bitree T) {
    if (T) {
        Postorder(T->lchild); // 左
        Postorder(T->rchild); // 右
        printf("%c", T->data); // 根
    }
}

6. 非递归统计二叉树节点个数

int CountNodes(Bitree T) {
    int count = 0;
    stack<Bitree> s;
    Bitree p = T;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            count++;
            p = p->lchild;
        } else {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    return count;
}

7. 非递归统计二叉树度为1的节点个数

int CountDegree1(Bitree T) {
    int count = 0;
    stack<Bitree> s;
    Bitree p = T;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            if ((p->lchild && !p->rchild) || (!p->lchild && p->rchild)) {
                count++;
            }
            p = p->lchild;
        } else {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    return count;
}

8. 非递归统计二叉树度为2的节点个数

int CountDegree2(Bitree T) {
    int count = 0;
    stack<Bitree> s;
    Bitree p = T;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            if (p->lchild && p->rchild) {
                count++;
            }
            p = p->lchild;
        } else {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    return count;
}

9. 非递归统计二叉树叶子节点个数

int CountLeaves(Bitree T) {
    int count = 0;
    stack<Bitree> s;
    Bitree p = T;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            if (!p->lchild && !p->rchild) {
                count++;
            }
            p = p->lchild;
        } else {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    return count;
}

10. 非递归求二叉树数据值的最大值

Elemtype MaxValue(Bitree T) {
    Elemtype max = T->data;
    stack<Bitree> s;
    Bitree p = T;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            if (p->data > max) {
                max = p->data;
            }
            p = p->lchild;
        } else {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    return max;
}