2.6 二叉树

树(tree)是一类比较重要的非线性的数据结构。之所以叫“树”,是因为它看起来像是一棵倒挂的树,根朝上,叶朝下。

树的基本哲学

树,是一种递归定义的数据结构。

树的相关概念

以上图为准,下面介绍相关概念:

  1. 节点:树中每一个字母代表的区域都可以称为节点。
  2. 根节点:一棵树只有一个根节点(root),例如图中的R。
  3. 子树:假设有蓝色部分的树1={B, A, U, K, L}, 黄色部分的树2={C, S}, 绿色部分的树3={D, T, I, N, L}。那么,树1,2,3,都称为是以R为根的树的子树。其中树1又有以A为根节点的{K, L}和以B为根节点的{U}等若干个子树,所以树是递归定义的。一棵树包含若干子树,子树里面可能又有子树,子子孙孙~
  4. 节点的度:一个节点含有的子树的个数。比如节点R与D的度为3,B和A的度为2,C和T的度为1, K、L、U等节点的度为0。
  5. 叶结点:也叫终端节点,是指度为0的节点。比如, S、L、I、N、还有前面提到的K、L、U。
  6. 非终端节点:也叫分支节点,是指度不为0的节点。
  7. 父节点子节点:父节点也叫双亲节点,子节点也可以叫做孩子。一个节点的子树的根称为该节点的孩子,以根节点为例,R的子树有树1,2,3,这三棵子树的的根节点分别为B,C,D,都是根节点R的子节点,同时该节点称为孩子的父节点,也即R是B,C,D的父节点。其他子树也同理。
  8. 兄弟节点:具有相同父节点的节点互称为兄弟节点;比如,A和U互称兄弟节点,T,I,N等。
  9. 祖先和子孙: 祖先是指,从根节点到该节点所经分支上的所有节点。比如L的祖先为T,D,R。子孙是指,以某节点为根的子树中任一节点都称为该节点的子孙。比如,B的子孙有A,U,K,L。
  10. 节点的层次:根为第1层,根的孩子为第2层,以此类推。

二叉树

二叉树(Binary tree)是指树中节点的度不大于2的有序树,当节点数为0时,是一棵空树,否则为非空树。它是数据结构中的重点研究对象。

有如下特征或性质:

  1. 根节点只有一个
  2. 每个节点至多有两棵子树,如果有两棵子树,左边的叫左子树,右边的叫右子树
  3. 子树有左右之分,次序不能随意颠倒。
  4. 二叉树也是递归定义的,如果一个节点有子树,那么这个子树本身又是一棵二叉树。

二叉树的遍历

下图是一个以节点A为根的二叉树:

再提树的基本哲学

还记得前面我说的树是一种递归定义的数据结构吗?带着这种思想来学习二叉树树的遍历吧。

前序遍历

前序遍历(Pre-Order Traversal)的次序为:根 -> 左 -> 右

  1. 从根节点出发,访问根节点,得到 A。
  2. A有左右子树,按照次序,应该访问左子树,得到 U。
  3. 以U为根,它又有左右子树,按照先序遍历顺序,这时候应该再次访问U的左子树,得到T。
  4. T没有子节点,因为是递归,而刚才以U为根节点,遍历了它的左子树,所以回到U。
  5. 现在开始遍历U的右子树,得到 I。
  6. 然后回到A,以A为根,刚才遍历了A的左子树,现在开始同样以根 -> 左 -> 右的次序遍历A的右子树即可。

最后可以得到前序遍历的结果:A -> U -> T -> I -> S -> N -> X, 也即是从A出发,沿着这棵树的外围绕了一圈,但重要的思想还是:树是递归定义的数据结构。

当先序遍历一棵二叉树时,根节点总是在第一个。

中序遍历

中序遍历(In-Order Traversal)的次序为:左 -> 根 -> 右

  1. 从根节点出发,有左右子树,前进到左子树U。
  2. U还有左右子树,继续前进到T,T没有子节点,得到 T。
  3. 根据递归与中序遍历次序,轮到“根”了,得到 U。
  4. 然后是“右”,得到 I。
  5. 这样A的左子树就遍历完了,到“根”了,得到 A。
  6. “左”和“根”都已经遍历完毕,再按照中序遍历的次序遍历“右”即可。

最后可以得到中序遍历的结果:T -> U -> I -> A -> N -> S -> X。当中序遍历一棵满而二叉树(比如上图中的树)时,根节点总是在结果的中间。

后序遍历

后序遍历(Post-Order Traversal)的次序为:左 -> 右 -> 根

  1. 从根节点A出发,沿着左子树往下走直到一个终端节点,得到T。
  2. 按照后序遍历次序,得到I。
  3. 然后U.....

最后可以得到后序遍历的结果:T -> I -> U -> N -> X -> S -> A。后序遍历一棵二叉树,根节点总是在最后一个。

层次遍历

层次遍历很简单,按照层次,从上到下,从左到右。

层次遍历的结果是:A -> U -> S -> T -> I -> N -> X.

二叉树的节点

/* 树的节点 */
typedef struct tree_node {
    /* 左孩子指针 */
    struct tree_node *left;
    /* 右孩子指针 */
    struct tree_node *right;
    /* 关键字 */
    char key;
}tree_node;

这个结构体定义了指向树的节点的左右指针,以及一个char类型的关键字, key。

二叉树节点的创建

/* 创建一个节点 */
tree_node *tree_create_node(char key)
{
    tree_node *node = (struct tree_node*)malloc(sizeof(struct tree_node));
    if(node==NULL) return NULL;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    
    return node;
}

上面的方法,接收一个关键字(key)作为参数,然后使用创建一个二叉树的节点并初始化,最后返回指向该节点的指针。

二叉树的创建

/* 创建一棵二叉树 */
tree_node *tree_create()
{
    char str;
    tree_node *current;   
    scanf("%c", &str);
    if('#' == str)
    {
        current = NULL;   
    } 
    else {
        current = tree_create_node(str);
        current->left = tree_create();
        current->right = tree_create();
    }
    return current;
}

递归法创建一颗二叉树。

  1. 定义一个char类型变量str,和一个节点指针current
  2. 等待用户输入,并将输入的字符赋值给 str
  3. #表示空节点,按照先序遍历的次序,生成二叉树。

注意,使用该函数时,用户一次输入一颗完整的二叉树。 比如:

ABD##E##CF##G##

按道理,递归创建,该函数会被自己多次调用,我们就应该输入多次,以表示节点的字符。但由于我们在最开始一次输入完了,所以每次scanf函数都会从缓冲区读取一个字符并执行程序。

最后我们成功创建了一颗如下的二叉树:

tree_create
tree_link.png

递归法遍历二叉树

这里函数不仅可以遍历一颗完整的二叉树,还可以遍历以参数节点为根节点的子树。

看这段程序,只需要记住树的基本哲学是递归,以及对应的遍历次序即可。

/* 前序遍历 */
void preorder_traverse1(tree_node *node)
{
    if(node != NULL) {
        printf("%c\t", node->key);
        preorder_traverse1(node->left);
        preorder_traverse1(node->right);
    }
}

/* 中序遍历 */
void inorder_traverse1(tree_node *node)
{
    if(node != NULL) {
        inorder_traverse1(node->left);
        printf("%c\t", node->key);
        inorder_traverse1(node->right);
    }
}

/* 后序遍历 */
void postorder_traverse1(tree_node *node)
{
    if(node != NULL) {
        postorder_traverse1(node->left);
        postorder_traverse1(node->right);
        printf("%c\t", node->key);
    }
}

非递归法遍历二叉树

非递归法主要是利用了栈来实现(模拟递归,其实函数的递归本身就是栈实现的),这里我们直接用前面章节实现的栈就可以。

代码中别忘了把之前写好的stack.hstack.c放入当前目录中,并且写好头文件包含:

#include "stack.h"

非递归法前序遍历二叉树的思路:

  1. 定义一个称为指向当前节点的指针current。
  2. 从根节点出发,即current=root,沿着current的左子树(如果有)往下走,并把current的根节点压入到栈中。
  3. 循环上述过程,直到叶子节点。
  4. 出栈,并将current置为出栈的节点的右子树,再回到步骤1,循环执行。
  5. 循环的终止条件是:当前节点为空或栈为空。

沿着这个思路就很容易实现非递归前序遍历:

/* 前序遍历2 */
void preorder_traverse2(tree_node *node)
{
    stack *stack = stack_create();
    tree_node *current = node;   
    
    while (current != NULL || stack->length)
    {
        if(current != NULL) {
            printf("%c\t", current->key);
            stack_push(stack, current);
            current = current->left;
        } else {
            current = stack_pop(stack);
            current = current->right;
        }
    }
    
    stack_release(stack);
}

非递归中序遍历也是用栈来实现,思路大致相同:

/* 中序遍历2 */
void inorder_traverse2(tree_node *node)
{
    stack *stack = stack_create();
    tree_node *current = node;   
    
    while (current != NULL || stack->length)
    {
        if(current != NULL) {
            stack_push(stack, current);
            current = current->left;
        } else {
            current = stack_pop(stack);
            printf("%c\t", current->key);
            current = current->right;
        }
    }

    stack_release(stack);
}

非递归后序遍历略有不同,这里用的是较为简单的思路:双栈。

第一个栈用根 -> 右 -> 左的顺序非递归遍历二叉树,利用第二个栈把结果反过来,就是后序遍历的顺序左 -> 右 -> 根,妙不?

/* 后序遍历2 */
void postorder_traverse2(tree_node *node)
{
    stack *s = stack_create();
    stack *stack = stack_create();

    tree_node *current = node;   
    
    while (current != NULL || stack->length)
    {
        if(current != NULL) {
            stack_push(s, &(current->key));
            stack_push(stack, current);
            current = current->right;
        } else {
            current = stack_pop(stack);
            current = current->left;
        }
    }
    while (s->length)
    {
        printf("%c\t", *(char *)stack_pop(s));
    }
    stack_release(s);
    stack_release(stack);
}

层次遍历二叉树

层次遍历一颗二叉树,比较简单,利用队列。这里也用前面章节写好的就行。

代码中别忘了把之前写好的queue.hqueue.c放入当前目录中,并且写好头文件包含:

#include "queue.h"

层次遍历的基本思路:

  1. 从根节点出发,把根节点放到队列中
  2. 队列出队,输出出队节点的关键字。
  3. 判断出队节点是否有左右孩子,如果有就按照,从左到右的顺序将节点加入队列。
  4. 回到步骤2,往下执行,直到队列为空,遍历终止。
/* 层次遍历 */
void level_traversel(tree_node *root)
{
    /* 创建一个队列 */
    queue *queue = queue_create();
    

    if(root != NULL)
    {
        queue_push_data(queue, root);
    }

    while (queue->length)
    {
        tree_node *current = queue_pull_data(queue);
        printf("%c\t", current->key);
        if(current->left) queue_push_data(queue, current->left);
        if(current->right) queue_push_data(queue, current->right);
    }

    /* 队列用完后,释放 */
    queue_release(queue);
}

编译并测试

测试函数写在main函数中。

int main() {

    /* ABD##E##CF##G## */
    tree_node *root = tree_create();

    printf("\n前序遍历1:");
    preorder_traverse1(root);
    
    printf("\n前序遍历2:");
    preorder_traverse2(root);

    printf("\n\n中序遍历1:");
    inorder_traverse1(root);
    
    printf("\n中序遍历2:");
    inorder_traverse2(root);

    printf("\n\n后序遍历1:");
    postorder_traverse1(root);
    
    printf("\n后序遍历2:");
    postorder_traverse2(root);

    printf("\n\n层次遍历0:");
    level_traversel(root);
    printf("\n");
    return 0;
}

编译命令:

# gcc *.c && ./a.out

输入:

ABD##E##CF##G##

输出:

前序遍历1:A    B       D       E       C       F       G
前序遍历2:A    B       D       E       C       F       G

中序遍历1:D    B       E       A       F       C       G
中序遍历2:D    B       E       A       F       C       G

后序遍历1:D    E       B       F       G       C       A
后序遍历2:D    E       B       F       G       C       A

层次遍历0:A    B       C       D       E       F       G

已有 2 条评论

  1. maths maths

    中序遍历 似乎不对 T -> I -> U -> A -> N -> S -> X

  2. 抱歉,确实错了。感谢你指出错误,已修改。

添加新评论