C语言数据结构之二叉链表创建二叉树

目录
  • 一、思想(先序思想创建)
  • 二、创建二叉树
    • (1)传一级参数方法
    • (2)传二级参数方法

一、思想(先序思想创建)

第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右边子树,原理和根节点左边创建左右子树相同

二、创建二叉树

二叉树的操作通常使用递归方法,如果递归不太明白,建议去对此进行一下学习和练习。二叉树的操作可以分为两类,一类是需要改变二叉树的结构的,比如二叉树的创建、节点删除等等,这类操作,传入的二叉树的节点参数为二叉树指针的地址,这种参入传入,便于更改二叉树结构体的指针(即地址)。这里稍微有一点点绕,可能需要多思考一下

如下是二叉数创建的函数,这里我规定,节点值为整数,如果输入的数为-1,则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树

二叉树结构体初始化:

为了更方便的使用二叉树结构体,可以使用 typedef 对结构体进行命名

typedef struct Tree{
 
 int data;                    //    存放数据域
 struct Tree *lchild;            //    遍历左子树指针
 struct Tree *rchild;            //    遍历右子树指针
 
}Tree,*BitTree;

这里展示两种传参类型的创建方法,其中深意可多次参考理解,加深指针理解

(1)传一级参数方法

BitTree CreateLink()
{
    int data;
    int temp;
    BitTree T;
    
    scanf("%d",&data);        //    输入数据
    temp=getchar();            //    吸收空格
    
    if(data == -1){            //    输入-1 代表此节点下子树不存数据,也就是不继续递归创建
        
        return NULL;

    }else{
        T = (BitTree)malloc(sizeof(Tree));            //        分配内存空间
        T->data = data;                                //        把当前输入的数据存入当前节点指针的数据域中
        
        printf("请输入%d的左子树: ",data);        
        T->lchild = CreateLink();                    //        开始递归创建左子树
        printf("请输入%d的右子树: ",data);            
        T->rchild = CreateLink();                    //        开始到上一级节点的右边递归创建左右子树
        return T;                            //        返回根节点
    }    
    
}

(2)传二级参数方法

BitTree CreateLink(BitTree *T)        //    次数 T为指向根节点的指针的地址
{
    int data;    
    
    scanf("%d",&data);

    
    if(data == -1){
        
        *T=NULL;                //    结束递归时,让指针当前节点的指针地址的 指针 指向NULL

    }else{
        
        *T = (BitTree)malloc(sizeof(Tree));        //    对指向节点指针地址的指针 分配内存
    
        if(!(*T) ){            //    *T = NULL  表示分配内存失败,也就是结束递归创建了
            printf("内存分配失败\n");
            exit(-1);
        }
        
        
        (*T)->data = data;        //    给节点指针地址内的数据域,存入数据
        
        printf("请输入%d的左子树: ",data);
        CreateLink(&(*T)->lchild);        //    开始遍历左子树
        printf("请输入%d的右子树: ",data);
        CreateLink(&(*T)->rchild);        //    开始遍历右子树,遍历的思想文章开头处解释
            
    }    
    
}

(1)一级参数完整例子:

#include<stdio.h>
#include<stdlib.h>

typedef struct Tree{
 
 int data;                    //    存放数据域
 struct Tree *lchild;            //    遍历左子树指针
 struct Tree *rchild;            //    遍历右子树指针
 
}Tree,*BitTree;

BitTree CreateLink()
{
    int data;
    int temp;
    BitTree T;
    
    scanf("%d",&data);        //    输入数据
    temp=getchar();            //    吸收空格
    
    if(data == -1){            //    输入-1 代表此节点下子树不存数据,也就是不继续递归创建
        
        return NULL;

    }else{
        T = (BitTree)malloc(sizeof(Tree));            //        分配内存空间
        T->data = data;                                //        把当前输入的数据存入当前节点指针的数据域中
        
        printf("请输入%d的左子树: ",data);        
        T->lchild = CreateLink();                    //        开始递归创建左子树
        printf("请输入%d的右子树: ",data);            
        T->rchild = CreateLink();                    //        开始到上一级节点的右边递归创建左右子树
        return T;                            //        返回根节点
    }    
    
}

void ShowXianXu(BitTree T)            //        先序遍历二叉树
{
    if(T==NULL)
    {
        return;
    }
    printf("%d ",T->data);
    ShowXianXu(T->lchild);            //    递归遍历左子树
    ShowXianXu(T->rchild);            //    递归遍历右子树
}

int main()
{
    BitTree S;
    printf("请输入第一个节点的数据:\n");
    S = CreateLink();            //        接受创建二叉树完成的根节点
    ShowXianXu(S);                //        先序遍历二叉树
    
    return 0;    
} 

(2)二级参数完整例子

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
    
    int data;
    struct Tree *lchild;
    struct Tree *rchild;
}Tree,*BitTree;

BitTree CreateLink(BitTree *T)        //    次数 T为指向根节点的指针的地址
{
    int data;    
    
    scanf("%d",&data);

    
    if(data == -1){
        
        *T=NULL;                //    结束递归时,让指针当前节点的指针地址的 指针 指向NULL

    }else{
        
        *T = (BitTree)malloc(sizeof(Tree));        //    对指向节点指针地址的指针 分配内存
    
        if(!(*T) ){            //    *T = NULL  表示分配内存失败,也就是结束递归创建了
            printf("内存分配失败\n");
            exit(-1);
        }
        
        
        (*T)->data = data;        //    给节点指针地址内的数据域,存入数据
        
        printf("请输入%d的左子树: ",data);
        CreateLink(&(*T)->lchild);        //    开始遍历左子树
        printf("请输入%d的右子树: ",data);
        CreateLink(&(*T)->rchild);        //    开始遍历右子树,遍历的思想文章开头处解释
            
    }    
    
}

void ShowXianXu(BitTree T)        //    先序遍历二叉树
{
    if(T==NULL)
    {
        return;
    }
    printf("%d ",T->data);
    ShowXianXu(T->lchild);        //    遍历左子树
    ShowXianXu(T->rchild);        //    遍历右子树
}

int main()
{
    BitTree *S;            //    创建指向这个结构体指针地址 的指针
    printf("请输入第一个节点的数据:\n");
    CreateLink(&S);        //    传二级指针地址
    ShowXianXu(S);        
    
    return 0;    
} 

到此这篇关于C语言数据结构之 二叉链表创建二叉树的文章就介绍到这了,更多相关C语言 二叉链表创建二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现线索二叉树的定义与遍历示例

    本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

  • C语言中二叉树的后序遍历详解

    目录 一.二叉树的后序遍历.(递归) 二.二叉树的后序遍历(迭代) 总结 首先我们从两个方面讲解二叉树的后序遍历(递归+迭代) 一.二叉树的后序遍历.(递归) 思想: 首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,②开始遍历其右孩子,如果其为NULL则访问该节点的值域,并返回其双亲节点重复第二步的操作,如果其不为NULL则以该节点为根节点重复第一步的操作.直到访问完所有节点时结束递归. 代码: void BTreePost

  • C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

  • C语言递归实现线索二叉树

    本文实例为大家分享了C语言递归实现线索二叉树的具体代码,供大家参考,具体内容如下 描述:将二叉树中结点的空左孩子指针域指向前驱结点,将空的右孩子指针域指向后继结点. code: #pragma warning(disable:4996) #include<stdio.h> #include<stdlib.h> typedef struct TreeNode { char data; struct TreeNode *lchild, *rchild; int ltag, rtag;

  • C语言实现二叉树层次遍历介绍

    目录 什么是层次遍历? 那我们如何来实现这个算法呢? 主体代码: 总结 什么是层次遍历? 对于一颗二叉树来说,从根节点开始,按从上到下.从左到右的顺序访问每一个结点. 注:每一个结点有且访问一次. 那我们如何来实现这个算法呢? 实现原理: 对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下.从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历. 这里我们需要引用队列来实现. 主体代码: BiTree

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言数据结构之二叉链表创建二叉树

    目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右

  • C语言实现二叉链表存储

    利用二叉链表存储,并且利用递归的方法实现二叉树的遍历(前序遍历.中序遍历和后续遍历)操作. c语言具体实现代码如下: #include<stdio.h> #include<stdlib.h> #include<malloc.h> typedef int ElemType;//数据类型 //定义二叉树结构,与单链表相似,多了一个右孩子结点 typedef struct BiTNode { ElemType data; struct BiTNode *lChild,*rCh

  • C语言数据结构与算法之链表(二)

    目录 引入 模拟链表介绍 插入代码实现 代码实现   引入 在上一节的学习中我们介绍了C语言如何实现链表,但是,在这一章,我们将抛开令人头秃的指针和结构体,我们将另外使用一种数组来实现的方式,叫做模拟链表.让我们一起来看看. 模拟链表介绍 链表中的每一个结点都只有两个部分. 我们可以使用一个数组date来储存每序列中的每一个数.那每一个数右边的数是谁,这一点该如何解决呢?在上一章的内容中我们是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了.具体要怎么

  • C语言数据结构与算法之链表(一)

    目录 引言 链表的相关思考 链表结点结构 建立链表 实现插入操作 完整代码 引言 在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子: 有一串已经排序好的数 2,3,5,8,9 ,10 如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位 这样操作显然很耗费时间,如果使用链表的话则会快很多.那么什么是链表呢?请看下图: 此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪. 链表的

  • C语言数据结构实例讲解单链表的实现

    目录 1.单链表 2.单链表的实现 头文件 函数的实现 (1)打印链表 (2)动态申请结点 (3)尾插 (4)头插 (5)尾删 (6)头删 (7)查找 (8)在pos之前插入 (9)删除pos (10)在pos之后插入 (11)在pos后删除 (12)最后用完记得销毁 3.各功能的测试 这里我们来简单实现单链表的增删查找. 1.单链表 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 . (链表和我们生活中最接近的就是火车了.) 2.单链

  • Java数据结构之二叉搜索树详解

    目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数

  • Java深入了解数据结构之二叉搜索树增 插 删 创详解

    目录 ①概念 ②操作-查找 ③操作-插入 ④操作-删除 1. cur.left == null 2. cur.right == null 3. cur.left != null && cur.right != null ⑤性能分析 ⑥完整代码 ①概念 二叉搜索树又称二叉排序树,它或者是一棵空树**,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 ②操作-查找

  • C语言实例实现二叉搜索树详解

    目录 有些算法题里有了这个概念,因为不知道这是什么蒙圈了很久. 先序遍历: root——>left——>right 中序遍历: left—— root ——>right 后序遍历 :left ——right——>root 先弄一个只有四个节点的小型二叉树,实际上这种小型二叉树应用不大. 二叉树的真正应用是二叉搜索树,处理海量的数据. 代码很简单,两种遍历的代码也差不多 #include<stdio.h> #include<stdlib.h> typedef

  • C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • javascript数据结构之二叉搜索树实现方法

    本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

随机推荐