9.数据结构之二叉树

亦凉 2022-08-20 06:25 19阅读 0赞

# 数据结构之二叉树 #

--------------------

## 树的简介 ##

之前我们接触了一维线性数据结构双端链表、动态数组以及他们的变形结构栈和队列，以及它们的组合结构hash表，解决了多种查找和存储的问题，但是线性的数据结构在使用上依然存在了不少问题，比如一维线性数据结构的查找效率只能达到O(n)的时间复杂度，所以为了解决上述的问题，我们在一维的基础上进行了扩展，引入和树形结构。

--------------------

### 树的分类 ###

树：**它是由n（n>=1）个有限节点组成一个具有层次关系的集合。**在我们的日常生活中也有很多树形结构的模型，比如家庭的族谱就是一个树形的结构，公司的整个员工层次也是一个树形的结构（不同部门、组织）。因为它的存放是具有一定规则的（按大小顺序、按不同模块），所以由此引申出了多种树形结构：

**B树**  
**二叉树**  
**字典树**

……

--------------------

## 二叉树的结构 ##

其中最常见的树形结构就是二叉树，二叉树有**左孩子**和**右孩子**两个后继节点，这需要我们使用两个二叉树节点指针。在构建二叉树时会大量的采用**递归**的编程思想，接下来我们需要从二叉树的创建、销毁、遍历、以及各种二叉树的性质入手（高度、节点个数、是否平衡等特性），介绍二叉树的部分应用。

--------------------

## 二叉树的实现 ##

对于二叉树的创建我们首先要确定二叉树的节点结构，除了存放数据的数据域、还得有指向其左右孩子的指针。

//二叉树节点结构
    typedef struct Tree_node Tree_node;
    
    struct Tree_node{
        char              data;    //数据区域
        Tree_node  *left_child;    
        Tree_node *right_child;
    };                 
    
    typedef Tree_node *Bin_tree;   //二叉树的根节点

设计好二叉树的节点后，我们需要列举出二叉树的接口，部分接口是笔试面试的重点问题：

//二叉树的接口
    //创建二叉树
    Bin_tree create_tree(char **str);    //创建二叉树
    Bin_tree create_tree_by_pre_mid(char *pre_str, char *mid_str, int length);    //通过先序中序构建二叉树
    Bin_tree create_tree_by_mid_last(char *mid_str, char *last_str, int length);    //通过中序后序构建二叉树
    
    
    void destroy_tree(Bin_tree *root);    //销毁二叉树
    void destroy_tree_nr(Bin_tree *root);   //非递归销毁二叉树
    void pre_order_print(Bin_tree root);    //前序递归遍历
    void mid_order_print(Bin_tree root);    //中序递归遍历
    void last_order_print(Bin_tree root);    //后序递归遍历
    
    void pre_order_print_nr(Bin_tree root);    //前序非递归遍历
    void mid_order_print_nr(Bin_tree root);    //中序非递归遍历
    void last_order_print_nr(Bin_tree root);    //后序非递归遍历
    
    void level_order_print(Bin_tree root);    //层序遍历
    
    Bin_tree copy_binary_tree(Bin_tree root);    //二叉树的拷贝
    Boolean is_binarytree_equal(Bin_tree root1, Bin_tree root2);    //二叉树是否相等
    
    Boolean is_full_binary_tree(Bin_tree root);   //判断是否是满二叉树
    Boolean is_complete_binary_tree(Bin_tree root);   //判断是否是完全二叉树
    Boolean is_balance_binary_tree(Bin_tree root);    //判断是否是平衡二叉树
    
    int get_binarytree_height(Bin_tree root);    //得到二叉树的高度
    int get_binarytree_node_count(Bin_tree root);   //得到二叉树的节点个数
    int get_binarytree_leaf_count(Bin_tree root);    //得到二叉树的叶子节点个数
    void swap_left_right(Bin_tree root);   //得到二叉树的镜像
    int get_binarytree_level_count(Bin_tree root, int level);    //得到指定层级的节点个数
    
    Tree_node *find_value(Bin_tree root, char value);    //找到指定值所在的节点
    Tree_node *find_common_node(Tree_node *node1, Tree_node *node2 );   //找到两个节点的最近公共节点
    
    Tree_node *find_parent(Bin_tree root, Tree_node *node);    //找到指定节点的双亲节点
    
    Boolean is_include_tree(Bin_tree root1, Bin_tree root2);    //二叉树是否包含

在介绍了二叉树的接口之后，我们需要对各个接口的实现进行详细的介绍。

--------------------

**1.二叉树的创建**

二叉树的创建方式非常多样，今天我们介绍利用字符串的方式来创建二叉树，当遇到普通字符时我们直接创建二叉树节点，当遇到‘\#’字符的时候我们认为该二叉树节点不存在，并且当二叉树的节点存在后，再遇到普通字符认为是其左孩子，当左孩子存在时再遇到普通字符我们认为是右孩子，下面我们举一个例子。

例如指定字符串为：  
**ABC\#\#DE\#\#F\#\#GH\#I\#\#J\#\#**

则其对应的二叉树如下图所示：

二叉树图  
![这里写图片描述][20160209203616400]

下面我们介绍二叉树的创建过程，代码如下。

//创建二叉树
    Bin_tree create_tree(char **str)    //创建二叉树
    {
        Bin_tree root =  NULL;
    
        //ABC##DE##F##GH#I##J##
        if(str != NULL && *str != NULL && **str != END){
            //当前的字符符合条件时创建二叉树节点，创建完成后创建其左右孩子
            root = create_node();
            root->data = **str;
            ++*str;    //指向下一个字符
            root->left_child = create_tree(str);
            ++*str;
            root->right_child = create_tree(str);   
        }
    
        return root;
    }

**使用遍历结果字符串构建二叉树**

除了上述的创建方式之外，在以前的学习过程中我们接触过：二叉树的遍历方式包括**先根序遍历**、**中根序遍历**和**后根序遍历**三种方式。

如果告诉了先序遍历和中序遍历的结果，或者是后序遍历和中序遍历的结果，我们可以推测出二叉树的整体结果，这样的结论是正确的，因为中序遍历的结果可以**确定各个节点左右孩子节点的顺序**，而先序和后序的结果可以说明**根结点的位置**。

下面我们给出通过遍历结果生成二叉树的方式：

//通过先序和中序生成二叉树
    Bin_tree create_tree_by_pre_mid(char *pre_str,
                           char *mid_str, int length)
    {
         //A B C D E F G H I J pre
         //C B E D F A H I G J mid
         Bin_tree root       =  NULL; 
         char     root_value =     0;    
         int      index      =    -1;
    
         //1.找到根节点数据value，pre的第一个
         if(pre_str == NULL || mid_str == NULL || length <= 0){
             return root;
         }
         //2.通过value构建该根节点
         root_value = pre_str[0];
         root = create_node();
         root->data = root_value;
         //3.通过查找value在中序的位置，把中序分为左右子树两部分序列，递归调用
         //本函数
         index = find_index(mid_str, root_value);
    
         root->left_child = create_tree_by_pre_mid(pre_str + 1, mid_str, index);
         root->right_child = create_tree_by_pre_mid(pre_str + index + 1,
                                                  mid_str + index + 1,
                                                  length - index - 1);
    
         return root;
    }

通过中序和后序生成二叉树：

//根据中序和后续结果构建二叉树
    Bin_tree create_tree_by_ml(char *mstr, char *lstr, int length)
    {
        Bin_tree root = NULL;
        int index = -1;
        int root_value = 0;
    
        if(mstr == NULL || lstr == NULL || length <= 0){ 
            return root;
        }
    
        root_value = lstr[length - 1];   //获取根节点的数据
        root = buy_node(); 
        root->data = root_value;
    
        index = find_char_index(mstr, root_value); 
        root->left_child = create_tree_by_ml(mstr, lstr, index);
        root->right_child = create_tree_by_ml(mstr + index + 1,
                                lstr + index, length - index - 1);
    
        return root;
    }

--------------------

**2.二叉树的销毁**

完成了二叉树的创建工作，紧接着我们介绍二叉树的销毁，很多资料上都介绍了一种递归的销毁方式，及先销毁二叉树的左孩子，再销毁二叉树的右孩子，最后销毁当前二叉树节点。这种做法是为了防止节点地址的丢失，如果首先销毁当前二叉树节点，则其左右孩子的地址就会丢失，造成内存泄露，所以递归是一种不错的解决方案。代码示例如下：

//二叉树的递归销毁
    //销毁二叉树
    void destroy_tree(Bin_tree *root)
    {
        //二叉树不存在，直接退出
        if(root == NULL || *root == NULL){
            return ;
        }
    
        destroy(*root);
        *root = NULL;
    }
    
    static void destroy(Bin_tree root)
    {
        if(root != NULL){
            destroy(root->left_child);    //删除左孩子
            destroy(root->right_child);    //删除右孩子
            free(root);
        }
    }

再次思考问题，我们使用递归的方式无非就是为了记录二叉树左右孩子的地址，如果借助队列记录每个二叉树节点的左右孩子地址，则可以采用迭代的方式进行二叉树的销毁，所以利用层序遍历的思想，可以使用循环操作销毁二叉树，因为减少了函数的递归调用，所以可以极大的提高效率。

**\*其中用到的queue（队列）数据结构在之前的线性数据结构中有所介绍。**

关于代码示例如下所示：

//模拟层序遍历方式销毁二叉树
    
    void destroy_tree_nr(Bin_tree *root)   //非递归销毁二叉树
    {
        //思路：
        // 
        //
        // A
        // / \
        // B C
        //
        // 1.在销毁n层节点之前，首先把n + 1的节点入队进行地址保存
        //
        Queue *queue = init_queue();
        Tree_node *p_node = NULL;
    
        if(root == NULL || *root == NULL){
            return ;    
        }
    
        p_node = *root;
        *root = NULL;
        in(queue, p_node);
    
        while(!is_queue_empty(queue)){
             get_queue_front(queue, (void **)&p_node);
             out(queue);
    
             //先记录p_node对应的下一层节点的地址，再销毁p_node
             if(p_node->left_child != NULL){
                 in(queue, p_node->left_child);
             }
    
             if(p_node->right_child != NULL){
                 in(queue, p_node->right_child);
             }
    
             free(p_node);
        }
    
        destroy_queue(&queue);
    }

--------------------

**3.二叉树的递归方式（递归）**

二叉树的递归方式非常的简单，我们以先根序为例，即先打印二叉树的数据内容，然后再打印二叉树的左孩子部分，再打印二叉树的右孩子部分（**都是在调用打印函数本身，只是传入的参数不同**），代码示例如下所示：

void pre_order_print(Bin_tree root)    //前序递归遍历
    {
        if(root != NULL){
             printf("%c ", root->data);
             pre_order_print(root->left_child);
             pre_order_print(root->right_child);
        }
    }
    
    void mid_order_print(Bin_tree root)    //中序递归遍历
    {
        if(root != NULL){
             mid_order_print(root->left_child);
             printf("%c ", root->data);
             mid_order_print(root->right_child);
        }
    }
    
    void last_order_print(Bin_tree root)    //后序递归遍历
    {
        if(root != NULL){
             last_order_print(root->left_child);
             last_order_print(root->right_child);
             printf("%c ", root->data);
        }
    }

除了递归遍历方式之外，我们还可以对二叉树进行非递归遍历，这需要借助栈来记录所遍历过的节点信息，从而可以达到回溯的效果。代码示例如下所示：

//二叉树的非递归遍历方式
    
    void pre_order_print_nr(Bin_tree root)    //前序非递归遍历
    {
        Stack *stack = init_stack();    //使用栈保存左右孩子的地址
        Tree_node *p_node = NULL;
    
        if(root == NULL){
            return ;
        }
    
        p_node = root;
        push(stack, p_node);
    
        while(!is_stack_empty(stack)){
            get_top(stack, (void **)&p_node);
            printf("%c ", p_node->data);
            pop(stack);
    
            if(p_node->right_child != NULL){
                push(stack, p_node->right_child);
            }
    
            if(p_node->left_child != NULL){
                push(stack, p_node->left_child);
            }
        }
    
        destroy_stack(&stack);
         //
        // A
        // / \
        // B G 
        // / \ / \
        // C D H J
        // / \ \
        // E F I
        //
        // 先序遍历：
        //
        // 借助栈，在打印当前节点后分别记录其右、左孩子
        //
        //
        //
        // 
        // D
        // G
        //
        //
        // A B C
    }
    
    void mid_order_print_nr(Bin_tree root)    //中序非递归遍历
    {
        Stack *stack = NULL;
        Tree_node *p_node = NULL;
    
        if(root == NULL){
            return ;
        }
    
        stack = init_stack();
        p_node = root;
    
        while(!is_stack_empty(stack) || p_node != NULL){
            while(p_node != NULL){  //首先找到当前节点最左边的节点
                push(stack, p_node);
                p_node = p_node->left_child;
            }
    
            get_top(stack, (void **)&p_node);
            printf("%c ", p_node->data);
            pop(stack);
    
            p_node = p_node->right_child;
        }
        destroy_stack(&stack);
    
        // A
        // / \
        // B G 
        // / \ / \
        // C D H J
        // / \ \
        // E F I
        //
        // CBEDFAHIGJ
        //
        // 思路：
        //
        // 1.使用栈进行回溯
        // 2.每打印完一个节点，要对其右孩子做处理
        // 3.每个节点都需要不断找到最左边的孩子进行打印
    }
    
    void last_order_print_non(Bin_tree root)    //后序遍历（非递归）
    {
        Tree_node *p_node = NULL;
        Tree_node **temp = NULL; 
        Tree_node *prev = NULL;
        Stack *stack = init_stack();
    
        if(root == NULL){ 
            return ;
        }
    
        p_node = root;
        push(stack, p_node);
    
        while(!is_stack_empty(stack)){
            get_top(stack, (void **)&p_node);
            if((p_node->left_child == NULL && p_node->right_child == NULL)
            || (prev != NULL && (p_node->left_child == prev || p_node->right_child == prev))){
            //如果当前节点没有左右孩子，或者虽然有左右孩子但是已经被
            //访问输出，则直接输出该节点，并且将其设为上一个访问的节点
                printf("%c ", p_node->data);
                pop(stack);
                prev = p_node;
            }else{    //如果不满足上面的情况，则将其右孩子和左孩子依次入栈
                if(p_node->right_child != NULL){
                    push(stack, p_node->right_child);
                }
                if(p_node->left_child != NULL){
                    push(stack, p_node->left_child);
                }
            }
        }
        printf("\n");
        destroy_stack(&stack);
    }

二叉树的层序遍历：每次遍历二叉树一层的节点，直到遍历完所有高度。关键点在于遍历完当前节点后一定要把其左右孩子依次添加到遍历队列中。代码示例如下：

void level_print(Bin_tree root)    //层序遍历
    {
        Tree_node *p_node = NULL;
        // A B G C D H E F
        // 1.利用队列存储当前节点的左右孩子，每次出队打印完数据后，都保存
        // 被打印节点的左右孩子地址，直到队列为空，则遍历结束
        if(root == NULL){
            return ;
        }
    
        p_node = root;
        Queue *queue = init_queue();
    
        in(queue, p_node);
        while(!is_queue_empty(queue)){
            get_queue_front(queue, (void **)&p_node);
            out(queue);
            //sleep(1);
            printf("%c ", p_node->data);
            //分别将p_node的左右子树入队
            if(p_node->left_child != NULL){
                in(queue, p_node->left_child);
            }
            if(p_node->right_child != NULL){
                in(queue, p_node->right_child);
            }
        }
        destroy_queue(&queue);
    }

--------------------

**4.二叉树的相关属性（高度、节点个数、叶子节点个树）**

得到二叉树的高度：

int get_binarytree_height(Bin_tree root)   //树的高度
    {
        //1.二叉树的高度：
        //
        // max(左子树高度，右子树高度) + 1；
        if(root == NULL){
           return 0;
        }
    
        return 1 + max(get_binarytree_height(root->left_child),
                       get_binarytree_height(root->right_child));
    }

得到二叉树的节点个树

int get_binarytree_node_count(Bin_tree root)   //节点个数
    {
        //二叉树内节点个数 = 1 + 左子树个数 + 右子树个数
        if(root == NULL){
            return 0;
        }
    
        return 1 + get_binarytree_node_count(root->left_child)
                 + get_binarytree_node_count(root->right_child);
    }

得到二叉树叶子节点个树

int get_binarytree_leaf_count(Bin_tree root)   //叶子节点个数
    {
        //叶子节点个数没有左右孩子
        if(root == NULL){
            return 0;
        }else if(root->left_child == NULL && root->right_child == NULL){
            //找到叶子节点，返回1
            return 1;
        }else{ 
            //递归的统计左右子树部分所有叶子节点的个数
            return get_binarytree_leaf_count(root->left_child)
                 + get_binarytree_leaf_count(root->right_child);
        }
    }

--------------------

**5.判断二叉树的状态（是否相等、是否为平衡、完全、满二叉树）**

（1）判断二叉树是否相等

根据二叉树的性质，如果两个二叉树相等，则其当前节点数据内容相等，并且其左孩子和右孩子的数据内容也要相等，并且二叉树的结构要相等。代码如下所示：

Boolean is_binary_equal(Bin_tree root1, Bin_tree root2)    //判断二叉树是否相等
    {
        //相等的条件：
        //
        //1.如果两个树都为空，则认为相等
        //
        //2.
        // (1)两个子树都不能为空；
        // (2)两个节点的值相等；
        // (3)左子树部分相等；
        // (4)右子树部分相等。
        if(root1 == NULL && root2 == NULL){ 
            return TRUE;
        }else if((root1 != NULL && root2 != NULL)
              && (root1->data == root2->data)
              && is_binary_equal(root1->left_child, root2->left_child)
              && is_binary_equal(root1->right_child, root2->right_child)){
            return TRUE;
        }else{
            return FALSE;
        }
    }

（2）判断一个二叉树是否时满二叉树

满二叉树意味着除了叶子节点（没有左右孩子）之外，其他的二叉树节点必须同时具有左右孩子。我们还可以通过计算二叉树的高度h和二叉树的节点个树count，如果二者之间满足(2^h - 1 == count),则说明二叉树是满二叉树。代码示例如下：

Boolean is_full_binary_tree(Bin_tree root)   //判断是否是满二叉树
    {
    
        //求出二叉树height的高度和count节点个数
        //
        //
       // 判断 2^height - 1 == count
        int height = 0;
        int count = 0;
    
        if(root == NULL){ 
            return FALSE;
        }
    
        height = get_binarytree_height(root);
        count = get_binarytree_node_count(root);
    
        return (powl(2, height) - 1) == count; 
    }

（3）判断二叉树是否是完全二叉树

完全二叉树是一个和满二叉树容易混淆的概念，而完全二叉树是一种近似的满二叉树，他可以转化为特定的数据结构（堆），下面我们开介绍以下如何判断二叉树是一颗完全二叉树。代码如下所示：

Boolean is_complete_binary_tree(Bin_tree root)    //判断是否是完全二叉树
    {
        //层序遍历一个二叉树，一旦找到一个不含有子节点或者只含有一个左孩子节点之后，那么
        //后续的所有节点都必须是叶子节点，否则该树就不是完全二叉树
        Queue *queue = init_queue();
        Tree_node *p_node = NULL;
        Boolean find_last = FALSE;   //判断当前是否已经找到第一个不含有两个子节点的节点
    
        if(root == NULL){
            return FALSE;
        }
    
        in(queue, root);
        while(!is_queue_empty(queue)){
            get_queue_front(queue, (void **)&p_node);
            out(queue);
            if(find_last == FALSE){
                if(p_node->left_child != NULL && p_node->right_child != NULL){
                    //当前节点含有两个子节点
                    in(queue, p_node->left_child);
                    in(queue, p_node->right_child);
                }else if(p_node->left_child != NULL && p_node->right_child == NULL){
                    //当前节点只含有左孩子，没有右孩子，则后续的节点必须是叶子节点
                    find_last = TRUE;
                    in(queue, p_node->left_child);
                }else if(p_node->left_child == NULL && p_node->right_child != NULL){
                    //当前节点只含有右子树，该树是不完全的
                    return FALSE;
                }else{
                    //当前节点不含有任何的子节点
                    find_last = TRUE;
                }
            }else{
                //之前已经找到不含有两个子节点的节点，当前的节点必须是叶子节点
                if(p_node->left_child != NULL || p_node->right_child != NULL){
                    return FALSE;
                }
            }
        }
    
        destroy_queue(&queue);
        return TRUE;
    }

(4)判断二叉树是否是平衡二叉树

平衡二叉树是一种特殊的要求，即二叉树的左右孩子高度差不能大于一，一般情况下这种严苛的要求用于查找二叉树，查找二叉树树的性质如下：用来进行元素查找，如果比当前节点小的元素，则在当前节点的左子树部分进行查找，如果比当前节点大的元素，则在当前节点的右子树部分进行查找，如果和当前节点数据域的元素相等则认为已经找到，如果当前节点为空，则认为在整个二叉树中都没有找到。  
代码示例如下：

Boolean is_balance_binary_tree(Bin_tree root)   //判断是否是平衡二叉树
    {
        int height_left = 0;
        int height_right = 0;
        Boolean left = FALSE;
        Boolean right = FALSE;
    
        //平衡二叉树的判断依据:
        //
        if(root == NULL){
            return TRUE;
        }
    
        height_left = get_binarytree_height(root->left_child);
        height_right = get_binarytree_height(root->right_child);
    
        left = is_balance_binary_tree(root->left_child);
        right = is_balance_binary_tree(root->right_child);
    
        //判断该树的左右子树是否是平衡二叉树，并且该节点
        //左右孩子的高度差值不能大于1
        if(left == TRUE && right == TRUE 
        && abs(height_left - height_right) <= 1){
            return TRUE;
        }else{
            return FALSE;
        }
    }

--------------------

6.二叉树其他操作

（1）得到二叉树的镜像，这需要我们交换当前二叉树节点的左右孩子地址，并且对其左右孩子进行递归的处理（交换其左右孩子），最终对原二叉树做了镜面对称的处理。代码如下所示：

void swap_left_right(Bin_tree root)   //得到树的镜像
    {
        if(root == NULL || (root->left_child == NULL 
                         && root->right_child == NULL)){
            return ;
        }
    
        //对它的左右孩子进行交换，再对其左右孩子做同样的处理
        swap(&(root->left_child), &(root->right_child), sizeof(root->left_child));
        swap_left_right(root->left_child);
        swap_left_right(root->right_child);  
    }

（2）查找二叉树中值为value的节点

如果只是一般的二叉树，我们需要对整棵树进行遍历。这将依赖于二叉树的节点个数，可以先判断当前节点的数据值是否符合条件，如果不符合可以对其左右子树部分先后进行判断。代码如下：

Tree_node *find_value(Bin_tree root, char value)    //查找树中值为value的节点
    {
        Tree_node *p_node = NULL;
    
        if(root == NULL || root->data == value){
            return root;
        }
    
        p_node = find_value(root->left_child, value);
        if(p_node == NULL){
            p_node = find_value(root->right_child, value);
        }
    
        return p_node;
    }

（3）找到指定节点的父节点

Tree_node *find_parent(Bin_tree root, Tree_node *node)   //找到指定节点的父节点
    {
        Tree_node *p_node = NULL;
    
        if(root == NULL || node == NULL
         || root->left_child == node || root->right_child == node){
            //如果该节点不存在或者它的左右孩子为所找的节点，则返回该节点
            return root;
        }
    
        //否则递归地在该节点的左孩子部分进行查找判断，如果左孩子部分没有找到，
        //则在右孩子部分进行递归的查找。如果右孩子部分也没有找到，则返回NULL
        p_node = find_parent(root->left_child, node);
        if(p_node == NULL){ 
            p_node = find_parent(root->right_child, node);
        }
    
        return p_node;
    }

（4）判断两个节点否具有包含关系  
这个首先要判断两个二叉树包含的第一个节点（根节点）的关系，如果tree2的根结点存在与tree1，则才能够对tree2的其他部分进行判断，当tree2的所有节点都存在于tree1的时候，我们就认为tree2包含于tree1，代码示例如下：

Boolean has_sub_tree(Bin_tree root1, Bin_tree root2)   //是否有包含关系
    {
        Boolean ok = FALSE;
    
        if(root1 != NULL && root2 != NULL){
            if(root1->data == root2->data){
                //如果当前两个根节点值相等，则开始判断他们的左右孩子情况
                ok = does_tree1_has_tree2(root1, root2);
            }
    
            if(ok == FALSE){
                ok = has_sub_tree(root1->left_child, root2);
            }
    
            if(ok == FALSE){ 
                ok =  has_sub_tree(root1->right_child, root2);
            }
        } 
        return ok;
    }

（5）找到两个树节点的最近公共祖先

关于这个问题我们需要针对两种情况作特殊的处理：  
1.当这两个节点本身具有直接继承关系时（即一个是另一个节点的双亲），我们需要向上层继续查找他们的祖先。

2.如果两者之间没有继承关系，则需要对这两个节点的位置进行判断。

代码示例如下：

Tree_node *find_common_node(Bin_tree root, Tree_node *node1,
                                Tree_node *node2 )   //找到两个节点的最近公共节点
    {
        // A
        // / \
        // B G 
        // / \ / \
        // C D H J
        // / \ \
        // E F I
        //
        // 1.如果出现node1和node2有继承关系，则返回高度较高节点的双亲节点
        //
        // find_value
        // find_parent
        //
        int height1 = get_binarytree_height(node1);
        int height2 = get_binarytree_height(node2);
    
        //处理包含关系
        if(height1 > height2){   
            if(find_value(node1, node2->data) != NULL){
                return find_parent(root, node1);         
            }
        }else if(height1 < height2){
            if(find_value(node2, node1->data) != NULL){
                return find_parent(root, node2);
            }
        }
    
        //处理非包含关系
        return find_common(root, node1, node2);
    }
    
    Tree_node *find_parent(Bin_tree root,
                           Tree_node *node)    //找到指定节点的双亲节点
    {
        Tree_node *p_node = NULL;
    
        if(root == NULL || root->left_child == node 
                        || root->right_child == node){
            //root不存在或者root是所要找的双亲节点
            return root;
        }
        p_node = find_parent(root->left_child, node); 
        if(p_node == NULL){ 
            p_node = find_parent(root->right_child, node);
        }
        return p_node;
    }
    
    static Tree_node *find_common(Bin_tree root,
                                  Tree_node *node1, Tree_node *node2){
        // 从根节点开始：
        //
        // 如果node1和node2分别在root左右子树部分，则root为最近公共祖先；
        //
        // 如果在左（右），则对root的左（右）子树部分进行递归的处理，直到满足
        //
        // node1 和node2在不同侧的情况
        if(find_value(root->left_child, node1->data)){
            if(find_value(root->right_child, node2->data)){
                return root;
            }else{ 
                return find_common(root->left_child, node1, node2);
            }
        }else{
            if(find_value(root->left_child, node2->data)){ 
                return root;
            }else{ 
                return find_common(root->right_child, node1, node2);
            }
        }
    }

上述我们给出了很多关于二叉树的操作，然后对这些操作进行测试，测试代码如下所示：

//二叉树接口测试代码
    #include <stdio.h>
    #include "binary_tree.h"
    
    int main(int argc, char **argv)
    {
        Bin_tree root = NULL;
        Bin_tree root1 = NULL;
        Bin_tree root2 = NULL;
        Tree_node *find = NULL;
        char *str = "ABC##DE##F##GH#I##J##";
        char *pre  = "ABCDEFGHIJ";
        char *mid  = "CBEDFAHIGJ";
        char *last = "CEFDBIHJGA";
        Boolean equal = FALSE;
    
    
        root = create_tree(&str);    //二叉树的创建
        root1 = create_tree_by_pre_mid(pre, mid, strlen(pre));
    
        printf("pre order:\n");
        pre_order_print(root);
        printf("\n");
    
        printf("mid order:\n");
        mid_order_print(root);
        printf("\n");
    
        printf("last order:\n");
        last_order_print(root);
        printf("\n");
    
        printf("last order:\n");
        last_order_print(root1);
        printf("\n");
    
    
        printf("level order:\n");
        level_order_print(root1);
        printf("\n");
    
        printf("pre order:\n");
        pre_order_print_nr(root);
        printf("\n");
    
        printf("mid order:\n");
        mid_order_print_nr(root);
        printf("\n");
    
        root2 = copy_binary_tree(root1);    //二叉树地拷贝
    
        if((equal = is_binarytree_equal(root1, root2)) == TRUE){
            printf("two trees are equal!\n");
        }
    
    
        printf("mid order:\n");
        mid_order_print_nr(root2);
        printf("\n");
    
        printf("the height of root2:%d\n", get_binarytree_height(root2));
        printf("the count of root2:%d\n", get_binarytree_node_count(root2));
        printf("the leaves count of root2:%d\n", get_binarytree_leaf_count(root2));
    
        //得到二叉树镜像
        swap_left_right(root1);
        printf("pre order:\n");
        pre_order_print_nr(root1);
        printf("\n");
    
        //判断是否是满二叉树
        if(is_full_binary_tree(root1) == TRUE){
            printf("root1 is full!\n");
        }else{
            printf("root1 is not full!\n");
        }
    
        //得到第n层二叉树的节点个数
        printf("the %d level count is:%d\n", 3, get_binarytree_level_count(root, 3));
    
        if((find = find_value(root, 'H')) == NULL){
            printf("H is not found!\n");
        }else{
            printf("%c is found!\n", find->data);
        }
    
        Tree_node *find1 = find_value(root, 'B');
        Tree_node *find2 = find_value(root, 'I');
        //找到两个节点的最近公共祖先
        Tree_node *parent = find_common_node(root, find1, find2);
    
        if(parent != NULL){ 
            printf("(%c and %c) parent is:%c\n",
                find1->data, find2->data, parent->data);
        }else{
            printf("not have baba!\n");
        }
    
        destroy_tree_nr(&root);
        destroy_tree_nr(&root1);
        destroy_tree_nr(&root2);
        return 0;
    }

--------------------

## 小结 ##

二叉树是一个非常神奇的数据结构，它解决了线性数据结构的查找和插入效率的瓶颈，所以我们需要深入的了解它的结构和应用，在接下面的章节中我们将会介绍更多的二叉树类型（二叉查找树、二叉线索树等），以及多叉树（B树）。敬请期待。

[20160209203616400]: /images/20220731/b87f74d7971b47188579612b3e0e3bf3.png