【一起学数据结构】二叉树的基本操作

浅浅的花香味﹌ 2022-10-24 13:21 202阅读 0赞

# 学习目标： #

1.了解二叉树的基本概念  
2.掌握并理解树的性质  
3.简单地实现树的构造和遍历

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

# 学习内容： #

1、 树的一些基本术语

（1）节点：根节点、子节点、孩子节点  
（2）度：深度、度为2、1、0的节点  
（3）完全二叉树、非完全二叉树、一般树

2、 树的性质

（1）n0 = n2+1 <= 推导过程理解 （分支和节点的关系是关键点）  
（2）若根节点从1开始编号，i编号的左孩子编号为2*i，右孩子节点为2*i+1

其他略…

3、 三种存储实现方法

（1）数组  
（2）双链表  
（3）三链表

// 数组方式
    #define maxSize 100
    typedef int BiTree[maxSize];
    BiTree b;
    
    // 链表方式
    typedef struct BiTNode{ 
        int data;
        BiTNode *lChild,*rChild;
    }BiTNode,*BTree;
    
    // 三链表
    
    typedef struct BiTNodes{ 
        int data;
        BiTNodes *parent,*lChild,*rChild;
    }BiTNodes;

4.基本操作

//
    // Created by 674619459 on 2021/1/29.
    //
    
    /** * @Author LYF * @DESC * * 1.二叉树的基本操作实现() * （1）初始化 * （2） * 2. * */
    
    #include "iostream"
    using namespace std;
    
    // 数组方式
    #define maxSize 100
    typedef int BiTree[maxSize];
    BiTree b;
    
    // 链表方式
    typedef struct BiTNode{ 
        int data;
        BiTNode *lChild,*rChild;
    }BiTNode,*BTree;
    
    // 三链表
    
    typedef struct BiTNodes{ 
        int data;
        BiTNodes *parent,*lChild,*rChild;
    }BiTNodes;
    
    // 1.构造空树
    bool InitTree(BiTNode *&T){ 
        T  =  (BiTNode*)malloc(sizeof(BiTNode));
    
        T->data = NULL;
        T->lChild = NULL;
        T->rChild = NULL;
    
        if(T){ return false;}//分配失败,构造空树失败
        return true;
    }
    
    // 2.摧毁树
    bool DestroyTree(BiTNode *&T){ 
        /** * 问题！ */
        free(T);//直接收回该空间可以吗？？那他的子树呢？或者应该遍历收回？
    }
    
    // 3.创建二叉树
    bool CreateTree(BiTNode *&T,int data[],int len){  //Root
    // T->data =10;
        // 按照左子树<根<右子树的规则创建
        for(int i =0;i<len;i++){ 
            BiTNode *p = T;
            while(p!=NULL){  //当该地址非空才能进行遍历推进
                if(data[i]<=p->data){ //考虑数据小于根节点，当根节点的左孩子为空则插入，非空则进行移动到此节点
                    if(p->lChild==NULL)
                    { 
                        BiTNode *temp = (BiTNode*)malloc(sizeof(BiTNode));
                        temp->data = data[i];
                        temp->rChild=NULL;
                        temp->lChild=NULL;
                        p->lChild=temp;
                        break;
                    }else
                    { p=p->lChild;}
    
                }else{ 
                    if(p->rChild==NULL)
                    { 
                        BiTNode *temp = (BiTNode*)malloc(sizeof(BiTNode));
                        temp->data = data[i];
                        temp->rChild=NULL;
                        temp->rChild=NULL;
                        p->rChild=temp;
                        break;
                    }else
                    { p=p->rChild;}
                }
            }
        }
        return true;
    }
    
    
    // 4.求深度
    // (1)若是完全二叉树则直接一致left
    // (2)一般二叉树？
    // 递归＋1？
    int maxs = 1;
    int counts = 1;
    int TreeDepth(BiTNode *T){ 
    
        if(T->rChild!=NULL||T->lChild!=NULL){  //当都为空则该趟递归结束
    
            if(T->lChild!=NULL){ counts++;if(counts>maxs){ maxs=counts;}TreeDepth(T->lChild);}
    
            if(T->rChild!=NULL){ counts++;if(counts>maxs){ maxs=counts;}TreeDepth(T->rChild);}
        }
    
        counts=1;// 回到起点
    
        return maxs;
    }
    
    
    
    // 先序遍历（递归方法）
    void PerOrderTraverse(BiTNode *T){ 
        if(T!=NULL){  //->data // 为空则是递归结束条件！！常见写法为if(T==NULL){return;}// 递归结束，返回上层，可能更好理解
    
            printf("%d=>",T->data); //先访问根
    
            PerOrderTraverse(T->lChild); // 递归深入左子树,递进的同时先打印（对应根节点），直到该递归结束跳出 ，开始递归右子树
    
            PerOrderTraverse(T->rChild);
        }
    
    }
    
    
    void MidOrderTraverse(BiTNode *T){ 
        if(T!=NULL){  //->data // 为空则是递归结束条件！！
    
            MidOrderTraverse(T->lChild);
            printf("%d=>",T->data);
            MidOrderTraverse(T->rChild);
        }
    
    }
    
    void AfterOrderTraverse(BiTNode *T){ 
        if(T!=NULL){  //->data // 为空则是递归结束条件！！
    
            AfterOrderTraverse(T->lChild);
    
            AfterOrderTraverse(T->rChild);
    
            printf("%d=>",T->data);
        }
    }
    int main(){ 
        BiTNode *tree;
        int data[4]={ 1,5,12,4};
        InitTree(tree);
        tree->data = 10;
        CreateTree(tree,data,4);
    
        cout<<"先序遍历:";
        PerOrderTraverse(tree);
        cout<<endl;
        cout<<"中序遍历:";
        MidOrderTraverse(tree);
        cout<<endl;
        cout<<"后序遍历:";
        AfterOrderTraverse(tree);
    
        cout<<"deepTh:"<<TreeDepth(tree);
    
    }

关于怎么去检验构造的树是否和预期一样（也可用来检验深度），可以采用idea的调试工具，如下图所示，通过调试可以发现各个节点指向的地址，以及其值的情况，很直观地反应了其逻辑关系！可以当做树的凹式表示法！![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjU0OTc0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/722c3728b83a4100ac84b1acfe8dda00.png