美文网首页
数据结构与算法10——二叉树

数据结构与算法10——二叉树

作者: Foxhoundsun | 来源:发表于2020-04-28 02:35 被阅读0次


    数据结构的树存储结构,常用于存储逻辑关系为 "一对多" 的数据。

    :对于一个结点,拥有的子树数(结点有多少分支)称为结点的度(Degree)
    层次:从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推。
    深度:一棵树的深度(高度)是树中结点所在的最大的层次

    二叉树

    二叉树是一种特定的树结构,是n(n>=0)个结点的有限集合,该集合为空集(空二叉树)或者由一个根结点和两个互不相交的、分别称为根结点左子树和右子树构成。

    image.png

    二叉树的特点

    1.每个结点最多有两棵子树,即二叉树中不存在度大于2的结点
    2.左子树和右子树有有序的,不能互相颠倒
    3.即使树中某结点只有一棵子树,也要区分是左子树还是右子树

    二叉树的性质

    1.在二叉树的第i层上最多有i^2 个结点

    2.深度为k的二叉树最多有2^k-1个结点

    3.对于任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则存在n0=n2+1
    4.具有n个结点的完全二叉树深度为[log2(n)]+1
    5.对含有n个结点的完全二叉树,如果按照从上到下且从左到右进行1n的编号,则对完全二叉树任意一个编号为i的结点有如下特性:

    i=1,则该结点是二叉树的根,没有双亲,否则编号为[i/2]的结点为双亲结点
    2i>n,则该结点无左孩子,否则,编号为2i的结点为其左孩子
    2i+1>n,则该结点没有右孩子,否则,编号为2i+1的结点为其右孩子

    二叉树的存储
    1.顺序存储
    二叉树的顺序存储指的是使用顺序表来存储二叉树。

    image.png

    按照层序的顺序把二叉树的各个结点依次存入顺序表中,可以发现,在完全二叉树的情况下,顺序表的存储空间得到最大程度的使用。

    但不是完全二叉树


    image.png

    代码:

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 15 // 存储空间初始分配量 
    #define MAX_TREE_SIZE 15 // 二叉树的最大结点数 
    
    typedef int Status;        // Status是函数的类型,其值是函数结果状态代码,如OK等 
    typedef int CElemType;     // 树结点的数据类型,目前暂定为整型 
    typedef CElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点  
    CElemType Nil = 0;   //设整型以0为空 或者以 INT_MAX(65535)
    
    typedef struct {
      //结点层
        int level; 
      //本层的序号(按照满二叉树给定序号规则)
        int order; 
    }Position;
    
    // visit
    Status visit(CElemType c){
        printf("%d ",c);
        return OK;
    }
    
    // 构造空二叉树T,因为T是固定数组,不会改变.
    Status InitBiTree(SqBiTree T){
        for(int i = 0; i < MAXSIZE; i++) {
            T[i] = Nil;
        }
        return OK;
    }
    
    
    // 按层序次序输入二叉树中的结点值(字符型或整型),构造顺序存储的二叉树T
    Status CreateBiTree(SqBiTree T){
        int i = 0;
        
        //printf("按层序输入结点的值(整型),0表示空结点, 输入999结束.结点数<=%d\n",MAX_TREE_SIZE);
    
        while(i < 10) {
            T[i] = i+1;
            //结点不为空并且没有双亲结点
            if(i!=0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
                return printError("出现无双亲的非根结点\n", ERROR);
            }
            i++;
        }
        return OK;
    }
    
    //清空二叉树
    //在顺序存储结构中, 两个函数完全一样的结果
    #define ClearBiTree InitBiTree
    
    //判断二叉树是否为空
    
    Status BiTreeEmpty(SqBiTree T){
        //根结点为空,则二叉树为空
        if (T[0] == Nil)
            return TRUE;
        
        return FALSE;
    }
    
    //获取二叉树的深度
    int BiTreeDepth(SqBiTree T){
        int i;
        for(i = MAXSIZE-1; i >= 0; i--) {
            if(T[i] != Nil) {
                break;
            }
        }
        
        //左斜树序号为 1-2-4-8
        //左斜树索引为 0-1-3-7
        int j = 0;
        while(powl(2, j)-1 < i) {
            j++;
        }
        return j;
    }
    
    //返回处于位置e(层,本层序号)的结点值
    CElemType Value(SqBiTree T,Position e){
        /*
        Position.level -> 结点层.表示第几层;
        Position.order -> 本层的序号(按照满二叉树给定序号规则)
        */
        
        //层数从1开始
        int depth = e.level-1;
        //某一层开端的索引
        int levelStart = powl(2, depth)-1;
        //序号从1开始
        int order = e.order-1;
        return T[levelStart+order];
    }
    
    /*
      获取二叉树跟结点的值
      初始条件: 二叉树T存在
      操作结果: 当T不空,用e返回T的根, 返回OK; 否则返回ERROR
    */
    Status Root(SqBiTree T,CElemType *e){
        if(BiTreeEmpty(T)) {
            return printError("二叉树为空", ERROR);
        }
        *e = T[0];
        return OK;
    }
    
    /*
     给处于位置e的结点赋值
     初始条件: 二叉树存在,e是T中某个结点的位置
     操作结果: 给处于位置e的结点赋值Value;
     */
    Status Assign(SqBiTree T,Position e,CElemType value){
        //找到位置e的具体索引
        int index = powl(2, e.level-1)+(e.order-2);
        //如果结点双亲为空
        if(value!=Nil && T[(index+1)/2]==Nil) {
            return printError("结点双亲为空", ERROR);
        }
        //双亲赋空值,但是有叶子结点
        if(value==Nil && (T[index*2+1]!=Nil || T[index*2+2]!= Nil)) {
            return printError("双亲赋空但是孩子有值", ERROR);
        }
        T[index] = value;
        return OK;
    }
    
    /*
     获取e的双亲;
     初始条件: 二叉树存在,e是T中的某一个结点
     操作结果: 若e是T的非根结点, 则返回它的双亲,否则返回"空"
     */
    CElemType Parent(SqBiTree T, CElemType e){
        
        for(int i = 1; i < MAXSIZE; i++) {
            if(T[i] == e) {
                return T[(i+1)/2-1];
            }
        }
        //没有找到
        return Nil;
    }
    
    //获取某个结点的左孩子
    
    CElemType LeftChild(SqBiTree T,CElemType e){
        for (int i = 0; i < MAXSIZE; i++) {
            if(T[i] == e) {
                if(i*2+1 >= MAXSIZE) {
                    return Nil;
                }
                return T[i*2+1];
            }
        }
        return Nil;
    }
    
    //获取某个结点的右孩子
    CElemType RightChild(SqBiTree T,CElemType e){
        for (int i = 0; i < MAXSIZE; i++) {
            if(T[i] == e) {
                if(i*2+2 >= MAXSIZE) {
                    return Nil;
                }
                return T[i*2+2];
            }
        }
        return Nil;
    }
    
    //获取结点的左兄弟
    CElemType LeftSibling(SqBiTree T,CElemType e) {
        //从1开始,0为根结点,没有左兄弟
        for(int i = 1; i < MAXSIZE; i++) {
            //右结点的索引为偶数
            if(T[i] == e && i%2==0) {
                return T[i-1];
            }
        }
        return Nil;
    }
    
    //获取结点的右兄弟
    CElemType RightSibling(SqBiTree T,CElemType e)
    {
        for(int i=1;i<MAX_TREE_SIZE;i++)
            //左结点的索引为奇数
            if(T[i]==e&&i%2==1)
                return T[i+1];
        
        return Nil;
    }
    
    #pragma mark -- 二叉树的遍历
    
     //层序遍历二叉树
    void LevelOrderTraverse(SqBiTree T){
        //找到二叉树的最后一个非空结点
        int i = MAXSIZE-1;
        while(i >= 0 && T[i] != Nil) {
            i--;
        }
        for(int j = 0; j <= i; j++) {
            if(T[j] != Nil) {
                visit(T[j]);
            }
        }
        printf("\n");
    }
    
    //前序遍历二叉树
    void PreTraverse(SqBiTree T,int e){
        visit(T[e]);
        if((e*2+1)<MAXSIZE && T[e*2+1] != Nil) {
            PreTraverse(T, e*2+1);
        }
        if((e*2+2)<MAXSIZE && T[e*2+2] != Nil) {
            PreTraverse(T, e*2+2);
        }
    }
    
    Status PreOrderTraverse(SqBiTree T){
        
        //树不为空
        if (!BiTreeEmpty(T)) {
            PreTraverse(T, 0);
        }
        printf("\n");
        return  OK;
    }
    
    //中序遍历
    
    void InTraverse(SqBiTree T, int e){
        
        // 左子树不空 
        if ((e*2+1)<MAXSIZE && T[2*e+1] != Nil)
            InTraverse(T, 2*e+1);
        
        visit(T[e]);
        
        // 右子树不空
        if ((e*2+2)<MAXSIZE && T[2*e+2] != Nil)
            InTraverse(T, 2*e+2);
    }
    
    Status InOrderTraverse(SqBiTree T){
        
        // 树不空
        if (!BiTreeEmpty(T)) {
            InTraverse(T, 0);
        }
        printf("\n");
        return OK;
    }
    
    //后序遍历
    
    void PostTraverse(SqBiTree T,int e)
    {   // 左子树不空
        if((e*2+1)<MAXSIZE && T[2*e+1]!=Nil)
            PostTraverse(T,2*e+1);
        // 右子树不空
        if((e*2+2)<MAXSIZE && T[2*e+2]!=Nil)
            PostTraverse(T,2*e+2);
        
        visit(T[e]);
    }
    Status PostOrderTraverse(SqBiTree T)
    {
        if(!BiTreeEmpty(T)) //树不空
            PostTraverse(T,0);
        printf("\n");
        return OK;
    }
    

    链式存储

    image.png
    //'#'为结束符表示当前结点的双亲结点没有左孩子或者右孩子,如上图所示二叉树转换为字符串为"ABDH#K###E##CFI###G#J##"
    CElemType Nil = '#';
    typedef struct BiTNode {
        CElemType data;
        struct BiTNode *lchild, *rchild;
    } BiTNode, *BiTree;
    
    
    // 构造空二叉树T
    Status InitBiTree(BiTree *T)
    {
        *T=NULL;
        return OK;
    }
    
    // 销毁二叉树
    void DestroyBiTree(BiTree *T){
        if(*T) {
            DestroyBiTree(&(*T)->lchild);
            DestroyBiTree(&(*T)->rchild);
            free(*T);
            *T = NULL;
        }
    }
    
    #define ClearBiTree DestroyBiTree
    
    // 创建二叉树
    void CreateBiTree(BiTree *T, char* str, int* index){
        CElemType ch = str[(*index)++];
        if(ch == Nil) {
            *T = NULL;
        }else {
            //创建新的结点
            *T = (BiTree)malloc(sizeof(struct BiTNode));
            //是否创建成功
            if(!*T) {
                exit(0);
            }
            //结点赋值
            (*T)->data = ch;
            //创建当前结点的左子树
            CreateBiTree(&(*T)->lchild, str, index);
            //创建当前结点的右子树
            CreateBiTree(&(*T)->rchild, str, index);
        }
    }
    
    // 二叉树T是否为空;
    Status BiTreeEmpty(BiTree T){
        if(T) {
            return FALSE;
        }else {
            return TRUE;
        }
    }
    
    // 二叉树T的深度
    int BiTreeDepth(BiTree T){
        
        if(!T) {
            return 0;
        }
        int i = 0;
        int j = 0;
        //分别计算出左子树的深度和右子树的深度,取较深的一边+1
        i = BiTreeDepth(T->lchild);
        j = BiTreeDepth(T->rchild);
        return i>j?i+1:j+1;
    }
    
    // 二叉树T的根
    CElemType Root(BiTree T){
        if (BiTreeEmpty(T))
            return Nil;
        
        return T->data;
    }
    
    // 返回p所指向的结点值;
    CElemType Value(BiTree p){
        return p->data;
    }
    
    // 给p所指结点赋值为value;
    void Assign(BiTree p,CElemType value)
    {
        p->data=value;
    }
    
    

    二叉树的遍历
    前序遍历

    //前序递归遍历T
    void PreOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return;
    // 显示结点数据,可以更改为其它对结点操作 
        printf("%c",T->data);
        //再先序遍历左子树
        PreOrderTraverse(T->lchild); 
        //最后先序遍历右子树
        PreOrderTraverse(T->rchild); 
    }
    
    

    非递归-1

    image.png

    树是一种重复的结构,在遍历的过程中,我们需要不停地回溯,因此选择采用栈思想。
    前序遍历的顺序为中-左-右

    image.png
    void PreOrderTraverse_1(BiTree T) {
        if(!T) return;
        int depth = BiTreeDepth(T);
        BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
        int top = -1;
        //根入栈
        stack[++top] = T;
        while(top>-1) {
            //根出栈,打印根结点的值
            BiTree cur = stack[top];
            top--;
            printf("%c",cur->data);
            //右孩子入栈
            if(cur->rchild) {
                stack[++top] = cur->rchild;
            }
            //左孩子入栈
            if(cur->lchild) {
                stack[++top] = cur->lchild;
            }
        }
        free(stack);
    }
    
    

    非递归-2
    1.找到当前二叉树的最左结点,在此过程中依次打印结点的值并入栈
    2.栈顶结点出栈,栈顶结点有右孩子,则当前二叉树变为栈顶结点的右子树,重复步骤1,否则一直出栈直到栈为空

    void PreOrderTraverse_2(BiTree T) {
        if(!T) return;
        int depth = BiTreeDepth(T);
        BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
        int top = -1;
        BiTree cur = T;
        while(cur || top>-1) {
            if (cur) {
                //找到最左结点
                printf("%c",cur->data);
                stack[++top] = cur;
                cur = cur->lchild;
            }else {
                //指向右孩子,重复遍历
                cur = stack[top];
                top--;
                cur = cur->rchild;
            }
        }
    }
    
    

    中序遍历

    //递归
    void InOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return ;
          //中序遍历左子树
        InOrderTraverse(T->lchild); 
      //显示结点数据,可以更改为其它对结点操作
        printf("%c",T->data);
        //最后中序遍历右子树
        InOrderTraverse(T->rchild); 
    }
    //非递归
    //和前序类似,前序是中-左-右,在入栈的过程中进行打印,中序为左-中-右
    void InOrderTraverse_1(BiTree T) {
        if(!T) return;
        int depth = BiTreeDepth(T);
        BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
        int top = -1;
        BiTree cur = T;
        while(cur || top>-1) {
            if(cur) {
                stack[++top] = cur;
                cur = cur->lchild;
            }else {
                cur = stack[top];
                top--;
                printf("%c",cur->data);
                cur = cur->rchild;
            }
        }
    }
    
    

    后序遍历

    void PostOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return;
        //先后序遍历左子树
        PostOrderTraverse(T->lchild); 
       /再后序遍历右子树
        PostOrderTraverse(T->rchild); 
        //显示结点数据,可以更改为其它对结点操作
        printf("%c",T->data);
    }
    
    //非递归-1
    //后序遍历的顺序为左-右-中 ,我们需要一个额外的lastVisit指针来记录最后一次访问的结点
    //找到最左结点,并且入栈
    //栈顶结点没有右孩子或者右孩子已经被访问过,才能将栈顶结点弹出并打印,否则,以栈顶结点的右子树开始重新遍历
    void PostOrderTraverse_1(BiTree T) {
        if(!T) return;
        int depth = BiTreeDepth(T);
        BiTree *stack = (BiTree*)malloc(sizeof(BiTree)*depth);
        int top = -1;
        BiTree cur = T, lastVisit = NULL;
        while(cur || top>-1) {
            if(cur) {
                //找到最左侧结点
                stack[++top] = cur;
                cur = cur->lchild;
            }else {
                cur = stack[top];
                //如果没有右孩子或者右孩子已经被访问过,则需要出栈并打印
                if(!cur->rchild || lastVisit == cur->rchild) {
                    printf("%c",cur->data);
                    top--;
                    lastVisit = cur;
                    cur = NULL;
                }else {
                    //有右孩子并且没有被访问过,开始访问右子树
                    cur = cur->rchild;
                }
            }
        }
    }
    
    //非递归-2
    //在非递归解法1中,压栈顺序为右-左,因为后序遍历的顺序为左-右-中,
    //因对前序遍历的非递归解法1加以改造,改变入栈的顺序为左-右,在出栈的时候不是打印而是用另外一个新栈来进行入栈操作
    
    void PostOrderTraverse_2(BiTree T) {
        if(!T) return;
        int depth = BiTreeDepth(T);
        BiTree* stack = (BiTree*)malloc(sizeof(BiTree)*depth);
        BiTree* outStack = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
        int top = -1;
        int outTop = -1;
        stack[++top] = T;
        while(top>-1) {
            BiTree topNode = stack[top];
            top--;
            outStack[++outTop] = topNode;
            if(topNode->lchild) {
                stack[++top] = topNode->lchild;
            }
            if(topNode->rchild) {
                stack[++top] = topNode->rchild;
            }
        }
        while(outTop>-1) {
            BiTree topNode = outStack[outTop--];
            printf("%c",topNode->data);
        }
    }
    
    

    层序遍历

    链式存储不是连续的内存空间,不能直接进行遍历。可以利用队列来进行遍历。

    image.png
    void LevelOrderTraverse(BiTree T) {
        if(!T) return;
        BiTree *queue = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
        int prior = 0;
        int rear = 0;
        queue[rear++] = T;
        while(prior != rear) {
            BiTree head = queue[prior++];
            printf("%c",head->data);
            if(head->lchild) {
                queue[rear++] = head->lchild;
            }
            if(head->rchild) {
                queue[rear++] = head->rchild;
            }
        }
    }
    
    
    

    相关文章

      网友评论

          本文标题:数据结构与算法10——二叉树

          本文链接:https://www.haomeiwen.com/subject/leguwhtx.html