美文网首页
数据结构与算法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个结点的完全二叉树，如果按照从上到下且从左到右进行1至n的编号，则对完全二叉树任意一个编号为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

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构与算法10——二叉树|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！