IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 二叉树存储与基本算法 -> 正文阅读

[数据结构与算法]二叉树存储与基本算法

树与二叉树

树的定义

  1. 树是n个结点的有限集合
  2. 若n等于0,称为空树
  3. 若n>0,满足一下条件
    1. 有且仅有一个根(root)
    2. 其余结点可分为m个互不相交的有限集T1,T2……,其中每一个集合本身又是一棵树,称为根的子树。

树的基本术语

  1. 根结点:没有前驱的结点
  2. 结点的度:结点拥有的子树
  3. 树的度:树内各节点度的最大值
  4. 度为0的结点称为叶子结点或者终端结点
  5. 度不等于0,为分支结点。
  6. 分支结点中除了根结点外其他结点称为内部结点
  7. 结点子的树的根称为该结点孩子,该结点称为孩子的双亲
  8. 拥有共同双亲结点的,称为兄弟结点
  9. 在同一层次上,双亲不同的结点称为堂兄弟
  10. 结点的祖先:从根到该结点所经分支上的所有结点
  11. 结点的子孙:从某结点为根的子树中任一结点
  12. 树的深度:树中节点的最大层次
  13. 有序树:树中节点的子树从左到右有次序
  14. 无序树:树中节点各子树无次序
  15. 森林:m棵树互不相交的树的集合

二叉树的定义

  1. 每个结点最多有俩个孩子
  2. 子树有左右之分,期中次序不能颠倒
  3. 二叉树可以是空集合

二叉树的性质

  1. 第i层上最多有2^(i-1)个结点
  2. 深度为k为二叉树最多有2^k - 1个结点
  3. 叶子数n0 度为2 的结点为n2 ,则 n0 = n2 + 1(分支的个数角度考虑)

满二叉树:深度为k且有2^ - 1 个结点的二叉树

特点
  1. 每一层结点数都达到最大
  2. 叶子结点全部在最底层
  3. 每一位置都有元素

完全二叉树

定义:深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号为1 ~n的节点一一对应

特点:
  1. 叶子结点只能分布在层次最大的俩层上
  2. 对任一结点,如果其右子树的最大层次为i,则其左子树最大层次最大层次必为 i 或者 i + 1
性质
  1. 具有n个结点的完全二叉树的深度为[log?n] + 1
  2. 如果结点i > 1 ,则双亲结点为[i / 2]
  3. 若2i > n ,则为叶子结点,否则左孩子结点为2i
  4. 若2i + 1 > n ,则无右孩子,否则右孩子结点为2i + 1
顺序存储

实现:按照满二叉树的结点层次编号,依次存放二叉树中的数据元素

链式存储
二叉链表的结点形式
typedef struct node
{
    int data;
    struct node  *lchild , *rchild;
}Node , * BiTree;

二叉链表存储特点:n个结点的二叉链表,有n+1个空指针域

三叉链表
typedef struct node
{
    int data;
    struct node  *lchild , *rchild , *father;
}Node , * BiTree;

遍历二叉树

递归前序遍历
void PreTraversal (BiTree t){
    if (t == NULL) return;
    printf("%c ",t->data);
    PreTraversal(t->lchild);
    PreTraversal(t->rchild);
}
非递归前序遍历

用栈来实现二叉树的前序遍历

void PreTraversal (BiTree t){
    stack<BiTree>temp;
    while (t || temp.size()){
        if (t){
            printf("%c ",t->data);
            temp.push(t);
            t = t->lchild;
        }
        else{
            t = temp.top();
            temp.pop();
            t = t->rchild;
        }
    }
}
递归实现中序遍历
void MidTraversal (BiTree T){
    if (!T) return;
    MidTraversal(T->lchild);
    printf("%c ",T->data);
    MidTraversal(T->rchild);
}
非递归实现中序遍历
void MidTraversal(BiTree t){
    stack<BiTree>temp;
    //if (t == NULL) return;
    while (t || temp.size()){
        if (t) {
            temp.push(t);
            t = t->lchild;
        }
        else {
            t = temp.top();
            temp.pop();
            printf("%c",t->data);
            t = t->rchild;
        }
    }
}
递归实现后序遍历

特点:遵循 右子树 -> 根结点 ->左子树 的遍历顺序

递归实现后序遍历

void PostTraversal (Bitree T){
    if (!T);
    PostTraversal(T->lchild);
    PostTraversal(T->rchild);
    printf("%c",T->data);
}
非递归后序遍历二叉树

二叉树的层次遍历

二叉树实现层次遍历,与bfs(宽度优先搜索)的思路是一致的。用队列来实现功能。

void LevTraversal(BiTree t){
    queue<BiTree>q;
    BiTree f;
    q.push(t);
    while (q.size()){
        f = q.front();
        q.pop();
        printf("%c ",f->data);
        if (f->lchild) q.push(f->lchild);
        if (f->rchild) q.push(f->rchild);
    }
}

建立二叉树

前序递归建立
void CreateBitree (BiTree * T){
    char ch ;
    scanf("%c",&ch);
    if (ch == '.'){
        *T = NULL;
    }
    else {
        *T = (BiTree)malloc(sizeof(Node));
        (*T)->data = ch;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        CreateBitree(&((*T)->lchild));
        CreateBitree(&((*T)->rchild));
    }
    return ;
}
  1. 建立二叉树的思路与遍历二叉树的思路是相同的
  2. 特别要注意的是,二叉树有多少指针域,只有将指针域全部赋值完后,递归才会结束,因为我们建立的是拓展二叉树,所以指针域都需要赋值
二叉树的复制
int  CopyTree(BiTree t , BiTree *newT){ 
    if (!t) return 0;
    *newT = (BiTree)malloc(sizeof(Node));
    (*newT)->data = t->data;
    CopyTree(t->lchild ,(&(*newT)->lchild));
    CopyTree(t->rchild,(&(*newT)->rchild));
}
树的深度的计算

基本思路是分别计算左右子树的深度,返回较大的深度。因为二叉树具有递归的结构,所以说用递归来计算深度

int TreeDeep(BiTree t){
    int n ,m;
    if (!t) return 0;
    m = TreeDeep(t->lchild);
    n = TreeDeep(t->rchild);
    if (n > m) return n + 1;
    else return m + 1;
}
树的结点数的计算
int nodeNumber(BiTree t){
    if (!t) return 0;
    return nodeNumber(t->lchild) + nodeNumber(t->rchild) + 1;
}
计算叶子结点数
int leafNode (BiTree t){
    if (!t) return 0;
    else if (t->lchild == NULL && t->rchild == NULL) return 1;
    else return leafNode(t->lchild) + leafNode(t->rchild);
}

return nodeNumber(t->lchild) + nodeNumber(t->rchild) + 1;
}


##### 计算叶子结点数

int leafNode (BiTree t){
if (!t) return 0;
else if (t->lchild == NULL && t->rchild == NULL) return 1;
else return leafNode(t->lchild) + leafNode(t->rchild);
}


  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-19 08:13:59  更:2021-09-19 08:15:37 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 2:28:11-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码