美文网首页
二叉树

二叉树

作者: 大橘猪猪侠 | 来源:发表于2020-04-25 14:33 被阅读0次

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。

相关术语：

  1. 结点 : 树中的⼀个独⽴单元. 包含⼀个数据元素及若⼲指向其他⼦树的分⽀. 例如, A,B,C,D等都是结点;
  2. 结点的度: 结点拥有的⼦树数称谓结点的度. 例如A的度是3, C的度为1, D的度为3, F的度为0.
  3. 树的度: 数的度是树内各结点度的最⼤值,例如,上图中的应该是3;
  4. 叶⼦: 度为0的结点称谓叶⼦或终端结点. 例如,K,J,F,G,M,I,J 都是树的叶⼦.
  5. ⾮终端结点: 度不为0的结点成为⾮终端结点或分⽀结点. 除了根结点以外,⾮终端结点也称为内部结点;
  6. 双亲和孩⼦: 结点的⼦树的根称为该结点的孩⼦, 相应地, 该结点称为孩⼦的双亲. 例如,B的双亲为A, B 的孩⼦有E和F.
  7. 兄弟: 同⼀个双亲的孩⼦之间称为兄弟结点, 例如H,I和J互为兄弟;
  8. 祖先: 从根到该结点所经历的分⽀上的所有结点, 例如, M的祖先为A,D,H.
  9. ⼦孙: 以某结点为根的⼦树中的任⼀结点都称为该结点的⼦树. 例如,B的⼦孙为E,F.
  10. 层次:结点的层次从根开始定义起, 根为第⼀层, 根的孩⼦为第⼆层. 树中任⼀层次等于双亲结点的层次 加1.
  11. 堂兄弟: 双亲在同⼀层的解答互为堂兄弟. 例如,结点G与E,F,H,i,J 互为堂兄弟.
  12. 有序树和⽆序树: 如果将树的结点的各⼦树看成从左到右是有次序的(即不能互换)则称为该树为有序树, 否则是⽆序树. 在有序树中最左边的⼦树的根称为第⼀个孩⼦,最右边的称为最后⼀个孩⼦. 什么叫有序 树,就类似在家谱中第⼀房太太,到第五房太太以及孩⼦是有顺序的.这样存在顺序关系叫有序树.
  13. 节点的⾼度: 节点到叶⼦节点的最⻓路径(边数)
  14. 节点的深度: 根结点到这个结点所经历的边的个数
  15. 节点的层数: 节点的深度-1
  16. 树的⾼度 : 根结点的⾼度.

⼆叉树(Binary Tree) 是n (n>=0)个结点所构成的集合. 它或为空树(n=0),对于⾮空树T:

  1. 有且仅有⼀个称之为根结点
  2. 除了根结点以外的其余结点分为2个互不相交的⼦集T1,T2. 分别称为T的左⼦树和右⼦树,且T1和T2本身 都是⼆叉树.

二叉树的特性

  1. ⼆叉树每个结点⾄多只有2颗⼦树(⼆叉树中不存在度⼤于2的结点). 所以⼆叉树中不存在⼤于2的结点. 注意: 不是只有2个⼦树,⽽是最多只有. 如果⼆叉树中没有⼦树或者只有⼀颗树是可以的.
  2. ⼆叉树的⼦树有左右之分,其次序不能任意颠倒.类似:就像⼈的双⼿,双脚.有顺序之分
  3. 即使只有⼀棵树,也需要区分是左⼦树还是右⼦树. 类似: 就像你在⽣活中,摔伤了⼿.伤的是左⼿还是右 ⼿,对你的⽣活影响都是完全不同的

对⼀颗具有n个结点的⼆叉树按层序编号,如果编号为i(1=< i <= n)的结点与同样深度的满⼆叉树中编号为i 的结点⼆叉树中位置完全相同. 则这颗⼆叉树称为完全⼆叉树.

  1. ⾸先"完全" 和 "满" 的差异, 满⼆叉树⼀定是⼀个完全⼆叉树不⼀定是满的.
  2. 完全⼆叉树的所有结点和同样深度的满⼆叉树,它们按照层序编号相同的结点⼀⼀对应. 这⾥有⼀个关键 词是按层序编号.
    1. 叶⼦结点只能出现在最下两层
    2. 最下层的叶⼦⼀定集中在左部连接
    3. 倒数第⼆层,若有叶⼦节点, ⼀定都在右部连续位置
    4. 如果结点度为1, 则该结点只有左孩⼦, 既不存在只有右⼦树的情况
    5. 同样结点数的⼆叉树, 完全⼆叉树的深度最⼩;

了解了二叉树的一些基本概念后，接下来通过顺序存储和链式存储来实现二叉树的一些基本操作

二叉树的顺序存储

二叉树的顺序存储可以直接利用数组来进行存储，通过数组来实现一系列的操作

用数组实现二叉树清空，直接利用跟二叉树的初始化一样，但是为了区分开来，我们用宏定义来换了一个名字

//构建空二叉树
Status InitBiTree(SqBiTree T){
    for (int i = 0; i<MAX_TREE_SIZE; i++) {
        T[i] = Nil;
    }
    return OK;
}

//按层次序依次输入二叉树节点值
Status CreateBiTree(SqBiTree T){
    int i = 0;
    while (i<10) {
        T[i] = i+1;
        //节点不为空，且有父节点
        if(i!=0 && T[(i+1)/2-1] == Nil && T[i]!=Nil){
            printf("出现无父节点的非根节点%d\n",T[i]);
            exit(ERROR);
        }
        i++;
    }
    //将空值赋值给后面的节点
    while (i<MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }
    return OK;
}
//清除二叉树,根初始化二叉树一摸一样
#define ClearBiTree  InitBiTree

//判断二叉树是否为空
Status BiTreeEmpty(SqBiTree T){
    if(T[0] == Nil){
        return TRUE;
    }
    return FALSE;
}

根据二叉树的特性，第0层时，数量为1，第1层时，数量为2，第三层数量为8……第n层时，数量为2^n-1

/*
返回二叉树的深度
初始条件：二叉树是否存在，e是T中某个节点的位置
操作结构：返回处于位置e（层，本层序号）的节点值
*/
int BiTreeDepth(SqBiTree T){
    int j = -1;
    int i;
    //找到最后一个节点
    for (i = MAX_TREE_SIZE-1; i>0; i--) {
        if(T[i]!=Nil)
            break;
    }
    do {
        j++;
    } while (powl(2, j)<=i);
    return j;
}

定位二叉树的节点的位置，查找根节点，对固定节点的值进行替换

/*返回处于位置e(层,本层序号)的结点值
初始条件: 二叉树T存在,e是T中某个结点(的位置)
操作结构: 返回处于位置e(层,本层序号)的结点值
*/
ElemType Value(SqBiTree T,Position e){
    
    /*
     Position.level -> 结点层.表示第几层;
     Position.order -> 本层的序号(按照满二叉树给定序号规则)
     */
    
    //pow(2,e.level-1) 找到层序
    printf("%d\n",(int)pow(2, e.level-1));
    //e.order
    printf("%d\n",e.order);
    
    return T[(int)pow(2, e.level-1)+e.order-2];
}

/* 获取二叉树跟结点的值
初始条件: 二叉树T存在
操作结果: 当T不空,用e返回T的根, 返回OK; 否则返回ERROR
*/
Status Root(SqBiTree T,ElemType *e){
    if(BiTreeEmpty(T)){
        return ERROR;
    }
    *e = T[0];
    return OK;
}

/*
给处于位置e的结点赋值
初始条件: 二叉树存在,e是T中某个结点的位置
操作结果: 给处于位置e的结点赋值Value;
*/
Status Assign(SqBiTree T,Position p,ElemType e){
    //找到当前e的位置
    int i = (int)powl(2, p.level-1)+p.order-2;
    //叶子节点的双亲
    if(e!=Nil && T[(i+1)/2-1] == Nil){
        return ERROR;
    }
    //给双亲节点赋值
    if(e == Nil && (T[i*2+1]!=Nil || T[i*2+2]!=Nil)){
        return ERROR;
    }
    T[i] = e;
    
    return OK;
}

找到一个节点的父节点，兄弟节点，都需要找到当前节点的值，在根据值的顺序求出另一个节点

/*
获取e的双亲;
初始条件: 二叉树存在,e是T中的某一个结点
操作结果: 若e是T的非根结点, 则返回它的双亲,否则返回"空"
*/

ElemType Parent(SqBiTree T,ElemType e){
    //判空
    if(T[0] == Nil){
        return ERROR;
    }
    for (int i = 1; i<MAX_TREE_SIZE; i++) {
        //找到e
        if(T[i] == e){
            return T[(i+1)/2-1];
        }
    }
    //没有找到
    return Nil;
}

/*
获取某个结点的左孩子;
初始条件:二叉树T存在,e是某个结点
操作结果:返回e的左孩子,若e无左孩子,则返回"空"
*/
ElemType LeftChild(SqBiTree T,ElemType e){
    //判空
    if(T[0] == Nil){
        return ERROR;
    }
    for (int i = 0; i<MAX_TREE_SIZE-1; i++) {
        //找到e
        if(T[i] == e){
            return T[i*2+1];
        }
    }
    
    return Nil;
}
/*
获取某个结点的右孩子;
初始条件:二叉树T存在,e是某个结点
操作结果:返回e的左孩子,若e无左孩子,则返回"空"
*/
ElemType RightChild(SqBiTree T,ElemType e){
    //判空
    if(T[0] == Nil){
        return ERROR;
    }
    for (int i = 0; i<MAX_TREE_SIZE-1; i++) {
        //找到e
        if(T[i] == e){
            return T[i*2+2];
        }
    }
    
    return Nil;
}
/*
获取结点的左兄弟
初始条件:  二叉树T存在,e是T中某个结点
操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂
*/
ElemType LeftSibling(SqBiTree T,ElemType e){
    //判空
    if(T[0] == Nil){
        return ERROR;
    }
    for (int i = 1; i<=MAX_TREE_SIZE; i++) {
        if(T[i] == e&&i%2 == 0){
            return T[i-1];
        }
    }
    return Nil;
}
/*  获取结点的右兄弟
初始条件: 二叉树T存在,e是T中某个结点
操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂
*/
ElemType RightSibling(SqBiTree T,ElemType e){
    //判空
    if(T[0] == Nil){
        return ERROR;
    }
    for (int i = 1; i<=MAX_TREE_SIZE; i++) {
        if(T[i] == e&&i%2 == 1){
            return T[i+1];
        }
    }
    return Nil;
}

对二叉树进行前序，中序，后序和层序遍历

//1、层序遍历
void LevelOrderTree(SqBiTree T){
    int i = MAX_TREE_SIZE-1;
    //找到最后一个非空节点序号
    while (T[i] == Nil) {
        i--;
    }
    //从根节点开始，遍历
    for (int j = 0; j<=i; j++) {
        if(T[j] != Nil)
            printf("%3d",T[j]);
    }
    printf("\n");
}

void preDisplay(SqBiTree T,int e){
    if(!BiTreeEmpty(T)){
        //打印根节点
        printf("%3d",T[e]);
        
        //先序遍历左子树
        if(T[2*e+1]!=Nil)
            preDisplay(T, 2*e+1);
        
        //后序遍历右子树
        if(T[2*e+2]!=Nil)
            preDisplay(T, 2*e+2);
    }
//    printf("\n");
}

void InDisplay(SqBiTree T,int e){
    if(!BiTreeEmpty(T)){
        //先序遍历左子树
        if(T[2*e+1]!=Nil)
            InDisplay(T, 2*e+1);
        
        printf("%3d",T[e]);
        
        //后序遍历右子树
        if(T[2*e+2]!=Nil)
            InDisplay(T, 2*e+2);
    }
//    printf("\n");
}

void backDisplay(SqBiTree T,int e){
    if(!BiTreeEmpty(T)){
        //先序遍历左子树
        if(T[2*e+1]!=Nil)
            backDisplay(T, 2*e+1);
    
        //后序遍历右子树
        if(T[2*e+2]!=Nil)
            backDisplay(T, 2*e+2);
        
        printf("%3d",T[e]);
    }
//    printf("\n");
}

main函数调用

Status iStatus;
    Position p;
    ElemType e;
    SqBiTree T;
    
    InitBiTree(T);
    CreateBiTree(T);
    printf("建立二叉树后，树空否？%d(1:是 0:否)\n",BiTreeEmpty(T));
    printf("树的深度=%d\n",BiTreeDepth(T));
    
    p.level = 3;
    p.order = 2;
    e = Value(T, p);
    printf("第%d层第%d个节点的值:%d\n",p.level,p.order,e);
    
    iStatus = Root(T, &e);
    if(iStatus){
        printf("二叉树的根为:%d\n",e);
    }else{
        printf("树为空，无根!\n");
    }
    
    e = 99;
    Assign(T, p, e);
    
    e = Value(T, p);
    printf("第%d层第%d个节点的值:%d\n",p.level,p.order,e);
    
    printf("节点%d的父节点为:%d\n",e,Parent(T, e));
    
    printf("左右兄弟节点分别为:%d,%d\n",LeftChild(T, e),RightChild(T, e));
    
    printf("节点%d的左右兄弟节点:%d,%d\n",e,LeftSibling(T, e),RightSibling(T, e));
    
    Assign(T, p, 5);
    
    printf("二叉树T层序遍历:");
    LevelOrderTree(T);
    printf("\n");
    printf("二叉树T先序遍历:");
    preDisplay(T,0);
    printf("\n");
    
    printf("二叉树T中序遍历:");
    InDisplay(T,0);
    printf("\n");
    
    printf("二叉树T后序遍历:");
    backDisplay(T, 0);
    printf("\n");
15877953718677.png

二叉树的链式存储

构建二叉树

typedef char ElemType;
ElemType Nil = ' ';
typedef struct BitNode{
    ElemType data;
    struct BitNode *lChild,*rChild;
}BiTNode,*BiTree;

//构建二叉树
Status InitBiTree(BiTree *T){
    *T = NULL;
    return OK;
}

二叉树的销毁和清空，性质都一样，需要释放节点

/* 销毁二叉树
初始条件: 二叉树T存在。
操作结果: 销毁二叉树T
*/

void DestoryBiTree(BiTree *T){
    if(*T){
        if((*T)->lChild)
            DestoryBiTree(&(*T)->lChild);
        if((*T)->rChild)
            DestoryBiTree(&(*T)->rChild);
        
        free(*T);
        *T = NULL;
    }
}

#define ClearBiTree DestoryBiTree

void CreateBiTree(BiTree *T){
    ElemType ch;
    //获取字符
    ch = str[indexs++];
    //判断当前字符是不是'#'
    if(ch == '#'){
        *T = NULL;
    }else{
            //创建新的节点
            *T = (BiTree)malloc(sizeof(BiTNode));
            //是否创建成功
            if (!*T) {
                exit(OVERFLOW);
            }
            /* 生成根结点 */
            (*T)->data = ch;
            /* 构造左子树 */
            CreateBiTree(&(*T)->lChild);
            /* 构造右子树 */
            CreateBiTree(&(*T)->rChild);
    }
}

判断二叉树是否为空，直接判断根节点的值是否为空
对二叉树的深度求值，需要对左子树和右子树进行递归层层遍历，得到的两个值进行比较

/*
 二叉树T是否为空;
初始条件: 二叉树T存在
操作结果: 若T为空二叉树,则返回TRUE,否则FALSE
*/

Status BiTreeEmpty(BiTree T){
    if(T)
        return FALSE;
    else
        return TRUE;
}
/*
 二叉树T的深度
初始条件: 二叉树T存在
操作结果: 返回T的深度
*/

int BiTreeDepth(BiTree T){
    
    int i,j;
    if(!T)
        return 0;
    
    //计算左孩子的深度
    if(T->lChild)
        i=BiTreeDepth(T->lChild);
    else
        i=0;
    
    //计算右孩子的深度
    if(T->rChild)
        j=BiTreeDepth(T->rChild);
    else
        j=0;
    
    //比较i和j
    return i>j?i+1:j+1;
}

/*
二叉树T的根
初始条件: 二叉树T存在
操作结果: 返回T的根
*/

ElemType Root(BiTree T){
    if(BiTreeEmpty(T))
        return Nil;
    
    return T->data;
}

前序、中序、后序遍历

#pragma mark--二叉树遍历
/*
 前序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 前序递归遍历T
 */

void preDisplay(BiTree T){
    if(T == NULL)
        return;
    printf("%2c",T->data);
    preDisplay(T->lChild);
    preDisplay(T->rChild);
}
/*
 中序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
*/
void InDisplay(BiTree T){
    if(T == NULL)
        return;
    InDisplay(T->lChild);
    printf("%2c",T->data);
    InDisplay(T->rChild);
}
/*
  后序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
*/
void backDisplay(BiTree T){
    if(T == NULL)
        return;
    backDisplay(T->lChild);
    backDisplay(T->rChild);
    printf("%2c",T->data);
}

main函数调用

BiTree T;
    ElemType e;
    
    InitBiTree(&T);
    StrAssign(str, "ABDH#K###E##CFI###G#J##");
    
    CreateBiTree(&T);
    
    printf("判断二叉树是否为空:%d(1:是 0:否),树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    
    e = Root(T);
    printf("二叉树的根为:%c\n",e);
    
    printf("二叉树的前序遍历:");
    preDisplay(T);
    printf("\n");
    
    printf("二叉树的中序遍历:");
    InDisplay(T);
    printf("\n");
    
    printf("二叉树的后序遍历:");
    backDisplay(T);
    printf("\n");

打印结果


15877962626755.png

相关文章

  • 数据结构与算法-二叉树02

    二叉树的定义 二叉树的特点 二叉树的五中基本形态 其他二叉树 斜二叉树 满二叉树 完全二叉树图片.png满二叉树一...

  • 二叉树

    二叉树 高度 深度真二叉树 满二叉树 完全二叉树 二叉树遍历前序 中序 后序层序遍历 翻转二叉树 递归法...

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 二叉树的宽度优先搜索（层次遍历，BFS）

    二叉树结构： 二叉树宽度优先搜索： 按照二叉树的层数依次从左到右访问二叉树的节点；例如：给定一个二叉树： 按照宽度...

  • 剑指 offer：39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 解题思路： 平衡二叉树：Wiki:在...

  • Algorithm小白入门 -- 二叉树

    二叉树二叉树构造二叉树寻找重复子树 1. 二叉树 基本二叉树节点如下： 很多经典算法，比如回溯、动态规划、分治算法...

  • 14-树&二叉树&真二叉树&满二叉树

    一、树 二、二叉树 三、真二叉树 四、满二叉树

  • 二叉树的应用

    完美二叉树（满二叉树） 除了最下一层的节点外，每层节点都有两个子节点的二叉树为满二叉树 完全二叉树 除二叉树最后一...

  • 12.树Tree（2）

    目录:1.二叉树的基本概念2.二叉树的性质3.二叉树的创建4.二叉树的遍历 1.二叉树的基本概念 2.二叉树的性质...

网友评论

      本文标题：二叉树

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|二叉树|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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