【数据结构】—— 二叉树(C)

二叉树

二叉树的概念：

二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

树的术语

树和子树：以根结点为根的树为全树，以其他结点作为根结点的树为子树

结点的度：表示当前结点拥有的分支个数

树的度：就是当前树结点最多拥有的度

叶子结点：度为0的结点就是叶子结点，它位于树最深层

树根结点：每一个非空树都有且只有一个被称为根的结点。此外如果一个结点没有父结点，那么这个结点就是整棵树的根结点

父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点

子结点：一个结点含有的子树的根结点称为该结点的子结点

祖先：对任意结点x，从根结点到结点x的所有结点都是x的祖先（结点x也是自己的祖先）

子孙：对任意结点x，从结点x到叶子结点的所有结点都是x的子孙（结点x也是自己的子孙）

兄弟结点：拥有共同父结点的结点互称为兄弟结点

路径：从一个结点到另一个结点之间的边和结点构成路径

层次：树根开始定义,根结点为第1层,它的子结点为第2层,以此类推

结点的深度：对任意结点x，x结点的深度表示为根结点到x结点的路径长度。所以根结点深度为0，第二层结点深度为1

树的深度：类似树的度对应于结点的度一样，最深的结点的深度

结点高度：对任意结点x，叶子结点到x结点的路径长度就是结点x的高度

森林：由 m （m >= 0）个互不相交的树组成的集合被称为森林。（上图以B，C为根节点的两棵子树就可以被称为森林）

二叉树的大概样式

单个节点：

树的形式：

//二叉树结构体的建立包括：数据域、左孩子指针、右孩子指针
typedef struct BiTNode {
    char data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode, * BiNodeTree;


1
2
3
4
5
6
7
8

先序创建二叉树

//先序建立二叉树
BiNodeTree CreateBiTree() {
    char ch;
    scanf("%c", &ch);
    BiNodeTree root;
    if (ch == '#') {
        root = NULL;
    } else {
        root = (BiNodeTree)malloc(sizeof(BiTNode));
        root->data = ch;
        root->lchild = CreateBiTree();
        root->rchild = CreateBiTree();
    }
    return root;//返回根节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉树的遍历方式

先序遍历

遍历顺序是根节点、左子树、右子树。

//先序遍历二叉树

void  PreOrderTraverse(BiNodeTree root) {
    if (root) {
        printf("%c ",root->data);
        PreOrderTraverse(root->lchild);
        PreOrderTraverse(root->rchild);
    }
}
1
2
3
4
5
6
7
8
9

中序遍历

遍历顺序：左子树、根节点、右子树

//中序遍历二叉树 
void InOrderTraverse(BiNodeTree root) {
    if (root) {
        InOrderTraverse(root->lchild);
        printf("%c",root->data);
        InOrderTraverse(root->rchild);
    }
}
1
2
3
4
5
6
7
8

后序遍历

遍历顺序：左子树、右子树、根节点

//后序遍历二叉树 
void PostOrderTraverse(BiNodeTree root) {
    if (root) {
        PostOrderTraverse(root->lchild);
        PostOrderTraverse(root->rchild);
        printf("%c",root->data);
    }
}
1
2
3
4
5
6
7
8