码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift

  • 数据结构树与二叉树的实现

    目录

    一、普通树的存储结构

    1、双亲表示法

    2.孩子表示法

    二、二叉树

    1.二叉树的顺序存储（必须是完全二叉树，否则很浪费空间）

    1）结构体

    2.二叉树的链式存储

    1）结构体

    2）操作

    1.创建一颗二叉树

    2.创建一个结点

    3.二叉树的前序遍历

    a.递归实现

    b.非递归，使用栈

    4.二叉树的中序遍历

    a.递归实现

    b.非递归实现

    5.二叉树的后序遍历

    a.递归实现

    b.非递归实现

    6.二叉树的层次遍历：使用队列

    三、线索二叉树

    1.先序线索化

    2.中序线索化

    3.后序线索化

    4.拓展，中序线索二叉树中

    1）找到以p为根，第一个为中序遍历的结点，其实就是最左边的叶节点

    2）找到p的后继

    3）能找到后继，就可以不使用递归来遍历了，能得到中序遍历结果

    4）找到以p为根结点，最后一个被中序遍历的结点，也就是p最右边的叶子结点

    5）找到p的前驱

    6）逆序中序遍历

    5.拓展，先序二叉树中

    1)寻找后继

    2）不能知道找到前驱，除非能直接找到父节点，然后再讨论

    6.拓展，后续二叉树中

    1）寻找前驱

    2）找不到后继，除非能找到父节点，再讨论

    四、二叉排序树

    1.结构体

    2.操作函数

    1）创建一颗二叉排序树

    2）创建一颗二叉排序结点

    3）查找关键值所对应结点

    a.递归

    b.非递归

    4）插入关键值

    5）构造一颗二叉排序树，其实就是不断插入的过程

    一、普通树的存储结构

    1、双亲表示法

    1. typedef  struct{
    2.     ElemType data;
    3.     int parent;
    4. }PTNode;
    5.  
    6. typedef  struct{
    7.     PTNode nodes[MAXSIZE];
    8.     int n;  //结点数
    9. }PTree;

    2.孩子表示法

    1. struct CTNode{
    2.     int child; //孩子在数组中的下标
    3.     CTNode *next;
    4. };
    5.  
    6. typedef  struct {
    7.     ElemType data;
    8.     CTNode *firstChild;
    9. }CTBox;
    10.  
    11. typedef  struct{
    12.     CTBox nodes[MAXSIZE];
    13.     int n,r;//结点数、根的下标
    14. }CTree;

    二、二叉树

    1.二叉树的顺序存储（必须是完全二叉树，否则很浪费空间）

    1）结构体

    1. struct TreeNode{
    2.     ElemType value;
    3.     bool isEmpty;
    4. };
    5.  
    6. TreeNode t[MAXSIZE]; //一般从下标为1开始存储，为了和下标对应起来，方便查找孩子
    7.  
    8. //顺序存储初始化将所有的isEmpty变为TRUE
    9.  
    10. //左孩子为2i 右孩子为2i+1  父节点为i/2
    11.  
    12. //i>n/2就是叶子结点

    2.二叉树的链式存储

    1）结构体

    1. //二叉树的链式存储
    2. typedef  struct BiTNode{
    3.     ElemType data;
    4.     BiTNode *lchild,*rchild;
    5. }BiTNode,*BTree;

    2）操作

    1.创建一颗二叉树

    1. BTree CreatBTree(ElemType rootdata)
    2. {
    3.     BiTNode *root = (BiTNode*)malloc(sizeof(BiTNode));
    4.     root->data=rootdata;
    5.     root->lchild=NULL;
    6.     root->rchild=NULL;
    7.     return  root;
    8. }

    2.创建一个结点

    1. BiTNode *CreatBiTNode(ElemType data)
    2. {
    3.     BiTNode* NewNode = (BiTNode*)malloc(sizeof(BiTNode));
    4.     NewNode->data=data;
    5.     NewNode->lchild=NULL;
    6.     NewNode->rchild=NULL;
    7.     return  NewNode;
    8. }

    3.二叉树的前序遍历

    a.递归实现
    1. void PreOrder(BTree T)
    2. {
    3.     if(T!=NULL){
    4.         visit(T);
    5.         PreOrder(T->lchild);
    6.         PreOrder(T->rchild);
    7.     }
    8. }
    b.非递归，使用栈
    1. //会使用栈
    2. void PreOrder1(BTree T)
    3. {
    4.     SqStack s;
    5.     InitStack(s);
    6.     BTree p =T;
    7.     while (p||!StackEmpty(s)) {
    8.         if(p){
    9.             visit(p);
    10.             push(s,p);
    11.             p=p->lchild;
    12.         }
    13.         else {
    14.             pop(s,p);
    15.             p=p->rchild;
    16.         }
    17.     }
    18. }

    4.二叉树的中序遍历

    a.递归实现
    1. void InOrder(BTree T)
    2. {
    3.     if(T!=NULL){
    4.         InOrder(T->lchild);
    5.         visit(T);
    6.         InOrder(T->rchild);
    7.     }
    8. }
    b.非递归实现
    1. void InOrder1(BTree T)
    2. {
    3.     SqStack s;
    4.     InitStack(s);
    5.     BTree p = T;
    6.     while (p||!StackEmpty(s)) {
    7.         if(p){
    8.             push(s,p);
    9.             p=p->lchild;
    10.         }
    11.         else {
    12.             pop(s,p);
    13.             visit(p);
    14.             p=p->rchild;
    15.         }
    16.     }
    17. }

    5.二叉树的后序遍历

    a.递归实现
    1. void PostOrder(BTree T)
    2. {
    3.     if(T!=NULL){
    4.         PostOrder(T->lchild);
    5.         PostOrder(T->rchild);
    6.         visit(T);
    7.     }
    8. }
    b.非递归实现
    1. void PostOrder1(BTree T)
    2. {
    3.     SqStack s;
    4.     InitStack(s);
    5.     BTree p = T;
    6.     BTree r=NULL;
    7.     while (p||!StackEmpty(s)) {
    8.         if(p){
    9.             push(s,p);
    10.             p=p->lchild;
    11.         }
    12.         else {
    13.           GetTop(s,p);
    14.           if(p->rchild!=r&&p->rchild)
    15.               p=p->rchild;
    16.           else {
    17.               pop(s,p);
    18.               visit(p);
    19.               r=p;
    20.               p=NULL;
    21.           }
    22.         }
    23.     }
    24. }

    6.二叉树的层次遍历：使用队列

    1.  
    2. void LevelOrder(BTree T)
    3. {
    4.     LinkQueue Q;
    5.     InitLinkQueue(Q);
    6.     BTree p;
    7.     EnLinkQueue(Q,T);
    8.     while (!LinkQueueEmpty(Q)) {
    9.         DeLinkQueue(Q,p);
    10.         visit(p);
    11.         if(p->lchild!=NULL)
    12.             EnLinkQueue(Q,p->lchild);
    13.         if(p->rchild!=NULL)
    14.             EnLinkQueue(Q,p->rchild);
    15.     }
    16. }

    三、线索二叉树

    1.先序线索化

    1. void PreThread(ThreadTree T, ThreadTree &pre)
    2. {
    3.     if(T!=NULL){
    4.         if(T->lchild==NULL){
    5.             T->lchild=pre;
    6.             T->ltag=1;
    7.         }
    8.         if(pre!=NULL and pre->rchild==NULL){
    9.             pre->rchild=T;
    10.             pre->rtag=1;
    11.         }
    12.         pre=T;
    13.         if(T->ltag==0)
    14.             PreThread(T->lchild,pre);
    15.         PreThread(T->rchild,pre);
    16.  
    17.     }
    18. }
    19.  
    20. void CreatPreThread(ThreadTree T)
    21. {
    22.     ThreadTree pre= NULL;
    23.     if(T!=NULL){
    24.         PreThread(T,pre);
    25.         pre->rchild=NULL;
    26.         pre->rtag=1;
    27.     }
    28. }

    2.中序线索化

    1. void InThread(ThreadTree T,ThreadTree &pre)
    2. {
    3.     if(T!=NULL){
    4.         InThread(T->lchild,pre);
    5.  
    6.         if(T->lchild==NULL){
    7.             T->lchild=pre;
    8.             T->ltag=1;
    9.         }
    10.         if(pre!=NULL and pre->rchild==NULL){
    11.             pre->rchild=T;
    12.             pre->rtag=1;
    13.         }
    14.         pre=T;
    15.  
    16.         InThread(T->rchild,pre);
    17.     }
    18.  
    19. }
    20.  
    21. void CreatInThread(ThreadTree T)
    22. {
    23.     ThreadTree pre= NULL;
    24.     if(T!=NULL){
    25.         InThread(T,pre);
    26.         pre->rchild=NULL;
    27.         pre->rtag=1;
    28.     }
    29. }

    3.后序线索化

    1. void PostThread(ThreadTree T, ThreadTree &pre)
    2. {
    3.     if(T!=NULL){
    4.     PostThread(T->lchild,pre);
    5.     PostThread(T->rchild,pre);
    6.  
    7.         if(T->lchild==NULL){
    8.             T->lchild=pre;
    9.             T->ltag=1;
    10.         }
    11.         if(pre!=NULL and pre->rchild==NULL){
    12.             pre->rchild=T;
    13.             pre->rtag=1;
    14.         }
    15.         pre=T;
    16.     }
    17. }
    18.  
    19. void CreatPostThread(ThreadTree T)
    20. {
    21.     ThreadTree pre= NULL;
    22.     if(T!=NULL){
    23.         PostThread(T,pre);
    24.         pre->rchild=NULL;
    25.         pre->rtag=1;
    26.     }
    27. }

    4.拓展，中序线索二叉树中

    1）找到以p为根，第一个为中序遍历的结点，其实就是最左边的叶节点

    1. ThreadNode *FirstNode(ThreadNode *p)
    2. {
    3.     //找到最左边叶节点
    4.     while (p->ltag==0) {
    5.         p=p->lchild;
    6.     }
    7.     return  p;
    8. }

    2）找到p的后继

    1. ThreadNode *NextNode(ThreadNode *p)
    2. {
    3.     if(p->rtag==0)
    4.         return FirstNode(p->rchild);
    5.     else {
    6.         return p->rchild;
    7.     }
    8. }

    3）能找到后继，就可以不使用递归来遍历了，能得到中序遍历结果

    1. void InOrder1(ThreadTree T)
    2. {
    3.     for(ThreadNode *p = FirstNode(T);p!=NULL;p=NextNode(p)){
    4.         visit_Thread(p);
    5.     }
    6. }

    4）找到以p为根结点，最后一个被中序遍历的结点，也就是p最右边的叶子结点

    1. ThreadNode *LastNode(ThreadNode *p)
    2. {
    3.     while (p->rtag==0) {
    4.         p=p->rchild;
    5.     }
    6.     return  p;
    7. }

    5）找到p的前驱

    1. ThreadNode *preNode(ThreadNode *p){
    2.     if (p->ltag==0) {
    3.         return LastNode(p->lchild);
    4.     }
    5.     else {
    6.         return p->lchild;
    7.     }
    8. }

    6）逆序中序遍历

    1. void RevInOrder(ThreadTree T)
    2. {
    3.     for(ThreadNode *p = LastNode(T);p!=NULL;p=preNode(p)){
    4.         visit_Thread(p);
    5.     }
    6. }

    5.拓展，先序二叉树中

    1)寻找后继

    1. ThreadNode *NextNode_pre(ThreadNode *p)
    2. {
    3.     if(p->rtag==0){
    4.         if(p->lchild!=NULL)
    5.             return p->lchild;
    6.         if(p->rchild!=NULL)
    7.             return p->rchild;
    8.     }
    9.     else {
    10.         return p->rchild;
    11.     }
    12. }

    2）不能知道找到前驱，除非能直接找到父节点，然后再讨论

    6.拓展，后续二叉树中

    1）寻找前驱

    1. ThreadNode *preNode_post(ThreadNode *p)
    2. {
    3.     if(p->ltag==1){
    4.         return p->lchild;
    5.     }
    6.     else {
    7.         if(p->rchild!=NULL)
    8.             return p->rchild;
    9.         else {
    10.             return p->lchild;
    11.         }
    12.     }
    13. }

    2）找不到后继，除非能找到父节点，再讨论

    四、二叉排序树

    1.结构体

    1. typedef  struct BSTNode{
    2.     ElemType data;
    3.     BSTNode *lchild,*rchild;
    4. }BSTNode,*BSTree;

    2.操作函数

    1）创建一颗二叉排序树

    1. BSTree CreatBSTree(ElemType rootdata)
    2. {
    3.     BSTNode *NewNode = (BSTNode*)malloc(sizeof (BSTNode));
    4.     NewNode->data=rootdata;
    5.     NewNode->lchild=NULL;
    6.     NewNode->rchild=NULL;
    7.     return  NewNode;
    8. }

    2）创建一颗二叉排序结点

    1. BSTNode *CreatBSTNode(ElemType data)
    2. {
    3.     BSTNode *NewNode = (BSTNode*)malloc(sizeof (BSTNode));
    4.     NewNode->data=data;
    5.     NewNode->lchild=NULL;
    6.     NewNode->rchild=NULL;
    7.     return  NewNode;
    8. }

    3）查找关键值所对应结点

    a.递归
    1. BSTNode *BSTSearch(BSTree bt, ElemTpye key)
    2. {
    3.     if(bt==NULL)
    4.         return  NULL;
    5.     if(bt->data==key)
    6.         return bt;
    7.     else if (bt->data>key) {
    8.         return BSTSearch(bt->lchild,key);
    9.     }
    10.     else {
    11.         return  BSTSearch(bt->rchild,key);
    12.     }
    13. }
    b.非递归
    1. BSTNode *BSTSearch(BSTree bt, ElemType key)
    2. {
    3.     while(bt!=NULL and key!=bt->data){
    4.         if(keydata)
    5.             bt=bt->lchild;
    6.         else {
    7.             bt=bt->rchild;
    8.         }
    9.     }
    10.     return bt;
    11. }

    4）插入关键值

    1. bool BSTInsert(BSTree &bt, ElemType key)
    2. {
    3.     if(bt==NULL){
    4.         BSTNode *Newnode = CreatBSTNode(key);
    5.         bt=Newnode;
    6.         return true;
    7.     }
    8.     if(bt->data==key){
    9.         return false;
    10.     }
    11.     else if(bt->data>key){
    12.         return BSTInsert(bt->lchild,key);
    13.     }
    14.     else {
    15.         return BSTInsert(bt->rchild,key);
    16.     }
    17.  
    18. }

    5）构造一颗二叉排序树，其实就是不断插入的过程

    1. void CreatBST(BSTree &bt, int key[], int n)//key[] 关键字数组，n 关键字数组长度
    2. {
    3.     bt = NULL;
    4.     for (int i=0;i
    5.         BSTInsert(bt,key[i]);
    6.     }
    7. }

  • 相关阅读:
    解决“error #147 declaration is incompatible with xxx xxx (declared at line xx)”问题
    ssh远程连接不了虚拟机ubuntu
    Unity技术手册-UGUI零基础详细教程-Button按钮
    使用Docker Compose运行Elasticsearch
    实验（六）：定时器实验
    LeetCode 69.x的平方根
    IDEA2021配置Maven
    Spring是什么？
    Docker创建Spring容器【方便服务迁移】
    【Java 进阶篇】深入了解 Bootstrap 按钮和图标
  • 原文地址：https://blog.csdn.net/z1zyy/article/details/134438911
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常，环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧！！！
    奉劝各位学弟学妹们，该打造你的技术影响力了！
    五年了，我在 CSDN 的两个一百万。
    Java俄罗斯方块，老程序员花了一个周末，连接中学年代！
    面试官都震惊，你这网络基础可以啊！
    你真的会用百度吗？我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候，用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难，连憨憨学妹都学会了！
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图，Python爬虫120例，再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号