二叉树以及链式二叉树的常见操作

素颜马尾好姑娘i 2022-05-26 03:56 191阅读 0赞

##### 二叉树是树这部分中最重要的知识之一，今天看完了郝斌老师关于树部分的知识，并对老师在看上所说的链式二叉树代码进行了实现 #####

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

# 一、二叉树的中的一些专有名词的解释： #

#### 1.先序遍历:指先访问根节点，再先序遍历左子树，再先序遍历右子树 ####

#### 2.中序遍历:指先中序遍历左子树，再访问根节点，再中序遍历右子树 ####

#### 3.后序遍历:指先后序遍历左子树，再后序遍历右子树，再访问根节点 ####

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

### 下面是郝斌老师上课时关于这三种遍历的视频截图 ###

#### 先序遍历： ####

![这里写图片描述][70]  
![这里写图片描述][70 1]

#### 中序遍历： ####

![这里写图片描述][70 2]  
![这里写图片描述][70 3]

#### 后序遍历： ####

![这里写图片描述][70 4]  
![这里写图片描述][70 5]

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

# 二、通过先序与中序求后序以及通过中序与后序求先序 #

### 不论是先序还是后序，我们分别可以从先序的第一个以及后序的最后一个来确认二叉树的根节点，然后通过中序可得出该二叉树的左子树部分由哪些组成，以及右子树部分由哪些组成。 ###

#### 1.在先序与中序求后序时，先序中谁先出现，谁就是子树的根节点 ####

#### 2.在中序与后序求后序时，后序中谁后出现，谁就是子树的根节点 ####

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

### 下面是郝斌老师关于求二叉树时的视频截图: ###

#### 已知先序中序求后序 ####

![这里写图片描述][70 6]

![这里写图片描述][70 7]

#### 已知中序后序求先序 ####

![这里写图片描述][70 8]

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

## 三、链式二叉树的常见操作 ##

##### 链式二叉树是常见二叉树的程序实现方法，根据郝斌老师的课程，我对他上课所敲的代码进行了实现，具体代码如下: #####

/* 该二叉树的树状图如下： A * * B C * D * E */
    
    
    //程序实现代码
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct BTNode{
        char data;
        struct BTNode * pLeft;
        struct BTNode * pRight;
    }BTNode;
    
    struct BTNode * createBTree(void);//创建二叉树
    void PreTraverseBTree(struct BTNode * pT);//前序遍历
    void InTraverseBTree(struct BTNode * pT);//中序遍历
    void PostTraverseBTree(struct BTNode * pT);//后序遍历
    
    int main(){
        struct BTNode * pT = createBTree();
    
        printf("该二叉树的前序遍历为:\n");
        PreTraverseBTree(pT);
    
        printf("\n该二叉树的中序遍历为:\n");
    
        printf("\n该二叉树的后序遍历为:\n");
        PostTraverseBTree(pT);
    
        printf("\n");
        return 0;
    }
    
    struct BTNode * createBTree(){
        BTNode * pA = (struct BTNode*)malloc(sizeof(BTNode));
        BTNode * pB = (struct BTNode*)malloc(sizeof(BTNode));
        BTNode * pC = (struct BTNode*)malloc(sizeof(BTNode));
        BTNode * pD = (struct BTNode*)malloc(sizeof(BTNode));
        BTNode * pE = (struct BTNode*)malloc(sizeof(BTNode));
    
        //给树的每个节点添加数据
        pA->data = 'A';
        pB->data = 'B';
        pC->data = 'C';
        pD->data = 'D';
        pE->data = 'E';
    
        //给树的相关节点通过指针连接
        pA->pLeft = pB;
        pA->pRight = pC;
        pB->pLeft = pB->pRight = NULL;
        pC->pLeft = pD;
        pC->pRight = NULL;
        pD->pLeft = NULL;
        pD->pRight = pE;
        pE->pLeft = pE->pRight = NULL;
    
        return pA;
    }
    
    void PreTraverseBTree(struct BTNode * pT){
        if(pT != NULL){
            printf("%c ",pT->data);
            if(pT->pLeft != NULL){
                PreTraverseBTree(pT->pLeft);
            }
            if(pT->pRight != NULL){
                PreTraverseBTree(pT->pRight);
            }
        }
    }
    
    void InTraverseBTree(struct BTNode * pT){
        if(pT != NULL){
            if(pT->pLeft != NULL){
                InTraverseBTree(pT->pLeft);
            }
            printf("%c ",pT->data);
            if(pT->pRight != NULL){
                InTraverseBTree(pT->pRight);
            }
        }
    }
    
    void PostTraverseBTree(struct BTNode * pT){
        if(pT != NULL){
            if(pT->pLeft != NULL){
                PostTraverseBTree(pT->pLeft);
            }
            if(pT->pRight != NULL){
                PostTraverseBTree(pT->pRight);
            }
            printf("%c ",pT->data);
        }
    }

[70]: /images/20220526/e6551f09ac5545ccb279e036237ced95.png
[70 1]: /images/20220526/fb0f0a0c33164ced93d8097f68c06949.png
[70 2]: /images/20220526/764ceba3045e4fd5ac3f8129263eb6f0.png
[70 3]: /images/20220526/c247e629b3164bc3bb069af6c6599bb0.png
[70 4]: /images/20220526/1c2f353fdbb34691bbbe097eb4cb7a49.png
[70 5]: /images/20220526/cbe14ab6e3e9496882b21d9f6efa4a5c.png
[70 6]: /images/20220526/c214532bb06e4102a61428c106d86b38.png
[70 7]: /images/20220526/79920412f05b404d9e478012ca2d0ff8.png
[70 8]: /images/20220526/8bb2d76e7e644a3d89200c05f6c9c783.png