二叉树的基本运算（数据结构学习笔记）

分手后的思念是犯贱 2022-12-28 04:23 132阅读 0赞

### 文章目录 ###

*   *  基本运算
     *   *  创建二叉树 CreateBTNode(\*b,\*str)
         *   *  算法分析
             *  创建二叉树的过程：
             *  创建二叉树图示过程：
             *  算法代码
         *  销毁二叉链 DestroyBT(\*b)
         *   *  算法代码
         *  查找结点 FindNode(\*b，x)
         *   *  算法代码
         *  找孩子结点 LchildNode(p)和RchildNode(p)
         *   *  算法代码
         *  求二叉树高度 BTNodeDepth(\*b)
         *   *  算法代码
         *  输出二叉树 DispBTNode(\*b)
         *   *  算法代码

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

采用二叉链存储结构讨论二叉树的基本运算算法。

## 基本运算 ##

二叉树的基本运算包括：

*  创建二叉树
 *  销毁二叉树
 *  找孩子结点 LchildNode§ 和 RchildNode§
 *  求树高度 BTHeight(b)
 *  输出二叉树 DispBTree(b) ：以括号表示法输出一颗二叉树 b  
    （采用二叉链存储讨论二叉树的基本运算）

### 创建二叉树 CreateBTNode(\*b,\*str) ###

将采用括号表示法表示的二叉树字符串str来创建一颗二叉树，

#### 算法分析 ####

*  “(” 意味着一棵左子树开始
 *  “(” 意味着一颗子树结束
 *  “,” 意味着一颗右子树开始
 *  单个字符：结点的值

#### 创建二叉树的过程： ####

先构造根节点 N，再构造左子树，后构造右子树。  
当左子树构造完后，需要重新找到根节点N，所以要**保存 N**。  
同时，**结点是按照最近原则匹配的**，因此需要用**栈**来保存。

> ① 当 ch=’(’ 时：则将前面刚创建的结点作为双亲结点进栈，并**置 k=1**，表示开始处理左孩子结点；  
> ② 当 ch=’)’ 时：表示栈顶结点的左、右孩子结点处理完毕，退栈；  
> ③ 当 ch=’,’ 时：表示开始处理右孩子节点，**置 k=2**。  
> ④ 当 ch 为单个字符时：  
> 创建结点 \*p 用于存放 ch；  
> **当 k=1 时**，将 \*p 结点作为栈顶结点的左孩子结点；  
> **当 k=2 时**，将 \*p 结点作为栈顶结点的右孩子结点。

#### 创建二叉树图示过程： ####

对于括号表示的二叉树：A ( B ( D ( ， G ) ) ， C ( E ， F ) )

当指针指到 ‘A’ 时，建立结点 A ，并用 b 保存根节点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

当指针指向 ‘(’ 时，将上一结点 ‘A’ 入栈，并将 k=1，准备处理上一结点（即栈顶元素 ‘A’ ）的左孩子结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]

当指针指向 ‘B’ 时，建立结点 B，并将当前栈顶元素的左孩子指针指向 B 结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

当指针指向 ‘(’ 时，将上一结点 ‘B’ 入栈，并将 k=1，准备处理上一结点（即栈顶元素 ‘B’ ）的左孩子结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]

当指针指向 ‘D’ 时，建立结点 D，并将当前栈顶元素的左孩子指针指向 D 结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]

当指针指向 ‘(’ 时，将上一结点入栈 ‘D’，并将 k=1，准备处理上一结点（即栈顶元素 ‘D’ ）的左孩子结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]

当指针指向 ‘,’ 时，将 k=2，准备处理上一结点（即栈顶元素 ‘D’ ）的右孩子结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]

当指针指向 ‘G’ 时，建立结点 G，并将当前栈顶元素的右孩子指针指向 G 结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 7]

当指针指向 ‘)’ 时，意味着该层子树构建完毕，将栈顶元素 ‘C’ 退栈：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 8]

当指针指向 ‘)’ 时，意味着该层子树构建完毕，将栈顶元素 ‘B’ 退栈：

![10][]

当指针指向 ‘,’ 时，将 k=2，准备处理上一结点（即栈顶元素 ‘A’ ）的右孩子结点：

![11][]

当指针指向 ‘C’ 时，建立结点 C，并将当前栈顶元素的右孩子指针指向 C 结点：

![12][]

当指针指向 ‘(’ 时，将上一结点 ‘C’ 入栈，并将 k=1，准备处理上一结点（即栈顶元素 ‘C’ ）的左孩子结点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 9]

后面过程依次进行。

#### 算法代码 ####

void CreateBTNode(BTNode *&b,char *str) //将 str 转化为二叉链 b
    {
        
        BTNode *St[MaxSize];    //栈
        BTNode *p;              //用于新建结点
    
        int top=-1;             //栈顶指针
        int k,j=0;
        char ch;
    
        b=NULL;                 //建立的二叉链初始时为空
        ch=str[j];
    
        while(ch!='\0'){
        
            switch(ch){
        
                case '(':{
        
                    top++;  St[top]=p;  //进栈操作
                    k=1;        //准备处理左孩子
                    break;
                }
                case ')':{
        
                    top--;      //退栈操作
                    break;
                }
                case ',':{
        
                    k=2;        //准备处理右孩子
                    break;
                }
                default:{
               //建立结点并与栈顶结点连接关系
                    p=(BTNode *)malloc(sizeof(BTNode));
                    p->data=ch;
                    p->lchild=p->rchild=NULL;
                    if(b==NULL) // p 为二叉树的根节点
                        b=p;    // b 用于存储根节点
                    else{
               //已建立二叉树根节点
                        switch(k){
        
                            case 1:{
        
                                St[top]->lchild=p;  //栈顶元素的左孩子链接新建节点
                                break;
                            }
                            case 2:{
        
                                St[top]->rchild=p;  //栈顶元素的右孩子链接新建节点
                                break;
                            }
                        }
                    }
                }
                j++;    ch=str[j];      //继续向后搜索
            }
        }
    }

### 销毁二叉链 DestroyBT(\*b) ###

设 f(b) 销毁二叉链 b 为**大问题**。  
则 f(b->lchild) 销毁左子树， f(b->rchild) 销毁右子树为**两个小问题**。

*  因此用**递归的方法**来销毁二叉树！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 10]

> 当 b=NULL 时，f(b) 不做任何事  
> 当 b!=NULL 时，f(b) = f(b->lchild),f(b->rchild)释放 \*b 结点

#### 算法代码 ####

void DestroyBT(BTNode *&b)
    {
        
        if(b==NULL)                 //子树为空
            return;
        else{
        
            DestroyBT(b->lchild);   //先销毁左子树
            DestroyBT(b->rchild);   //再销毁右子树
            free(b);                //剩下最后一个结点*b，直接释放
        }
    }

### 查找结点 FindNode(\*b，x) ###

与**销毁二叉链算法同理**  
设 f(b) 二叉链 b 去查找结点 x 为**大问题**。  
则 f(b->lchild) 去查找结点 x ， f(b->rchild) 去查找结点 x 为**两个小问题**。

*  同样用**递归的方法**来查找结点 x

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 11]

> 当 b=NULL 时，f(b,x) = NULL  
> 当 b->data=x 时，f(b,x) = b  
> 当在左子树找到了，即 p=f(b->lchild,x) 并且p!=NULL 时，f(b,x) = p;  
> 其他情况，f(b,x) = f(p->rchild,x)

#### 算法代码 ####

BTNode *FindNode(BTNode *b,ElemType x)  //函数定义为 BTNode * 因为最后返回结点x
    {
        
        if(b==NULL)                         //当二叉树为空时，返回空结点NULL
            return NULL;
        else if(b->data==x)                 //当二叉树的根节点就是要找的 x 结点时，返回根节点
            return b;
        else{
                                       
            p=FindNode(b->lchild,x);        //否则就在左子树中寻找结点 x
            if(p!=NULL)                     //在左子树中找到了 x 结点
                return p;                   //返回左子树中的 p 结点
            else
                return FindNode(b->rchild,x);   //若都没找到，则最后无论右子树找没找到且二叉树不为空时，都返回值，找到返回结点值，没找到返回空NULL。
        }
    }

### 找孩子结点 LchildNode§和RchildNode§ ###

直接返回\*p结点的左孩子结点或右孩子结点的指针。

#### 算法代码 ####

BTNode *LchildNode(BTNode *p)
    {
        
        return p->lchild;
    }
    
    BTNode *RchildNode(BTNode *p)
    {
        
        return p->rchild;
    }

### 求二叉树高度 BTNodeDepth(\*b) ###

使用递归算法，大问题化为小问题解决。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 12]

> 当 b=NULL 时，f(b)=0  
> 其他情况，f(b) = MAX\{f (b->lchild), f(b->rchild) \} + 1 //加一是因为根节点存在，使得高度为子树高度加一。

#### 算法代码 ####

int BTNodeDepth(BTNode *b)
    {
        
        int lchilddep,rchilddep;        //记录左右子树的高度
        if(b==NULL)         //二叉树为空
            return 0;
        else{
        
            lchilddep=BTNodeDepth(b->lchild);                       //递归求左子树高度
            rchilddep=BTNodeDepth(b->rchild);                       //递归求右子树高度
            return (lchilddep>rchilddep)?(lchild+1):(rchild+1);     //左、右子树高度对比求出最高高度
        }
    }

### 输出二叉树 DispBTNode(\*b) ###

将二叉树的二叉链转化为二叉树的括号表示

![在这里插入图片描述][2020121417053086.png]

#### 算法代码 ####

void DispBTNode(BTNode *b)
    {
        
        if(b!=NULL){
        
            printf("%c",b->data);                       //首先输出根节点
            if(b->lchild!=NULL||b->rchild!=NULL){
               //左子树或者右子树不为空时
                printf("(");                            //先输出左括号 '('，准备输出左子树
                DispBTNode(b->lchild);                  //递归输出左子树
                if(b->rchild!=NULL)                     //右子树不为空时
                    printf(",");                        //输出逗号 ','，准备输出右子树
                DispBTNode(b->rchild);                  //递归输出右子树
                printf(")");                            //括号结束该层子树的输出
            }
        }
    }

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/986bd89d6da8417c9017fb4c1cb8e459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/547377e5630144b995496b1500742a80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: /images/20221120/b5c00ee12c9d4732906ff7c8e939d078.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]: /images/20221120/457b1526cb2441c78fa5496600f10a49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]: /images/20221120/fc250bccb2bd4430a0a67522481f5de9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]: /images/20221120/9388ab17789949abbe8a0164554db8e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]: /images/20221120/e031eaa4dff54741bda4b512b079df60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 7]: /images/20221120/2498738d12ed40cf9e0905a6fe9baba1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 8]: /images/20221120/52f72393421e460c891e6a4f8760b005.png
[10]: /images/20221120/34ed6ce726724dcdb1512c938a06f57c.png
[11]: /images/20221120/b328a105bc8247238ab5542e7079f4aa.png
[12]: /images/20221120/ddcd48d3f38847b6a0a5fddf29b6057a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 9]: /images/20221120/3665b7c0523744789abc69cda9a8bf91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 10]: /images/20221120/780db79ff0ce4caa9466b4c106d6aae6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 11]: /images/20221120/e92b382d3afa4f8eae5a70b123b15647.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 12]: /images/20221120/eae28fa517644fd985c35c35bec6483b.png
[2020121417053086.png]: /images/20221120/342d06ac2cf7439194ca32aab249ba64.png