本篇文章主要是介绍,c语言实现二叉树的构建,以及常用的二叉树的搜索方法。
二、二叉树的定义首先给出比较直观的定义:
二叉树就理论上是类似上图的结点—连接的结构。每个结点有两个子节点(子节点:就是某一结点来说的下面连接的两个结点),有区分,分左节点和右节点,若没有一边的结点则可说某结点为空。
三、二叉树结构的c语言构造(首先要声明,下述设计的二叉树是根据逻辑结构设计的非线性二叉树,这并非是唯一的二叉树的构造方法)
由二叉树的定义,可以轻松的得知二叉树可以看成一些基本结构(结点)的集合,因此我们只需构造出结点就完成了一大半。
3.1结点的构造
typedef struct node{ int data; node* lchild; node* rchild; }Node;
这样就构造出来结点结构,分别为存放值的data,以及指向左右节点的指针 lchild, rchild。
下一步,定义二叉树
3.2二叉树的构造
typedef struct bintree{ Node root; }BinTree;
由于本次定义的二叉树在数据结构上不是线性,因此不便在bintree结构体中将所有的结点都存储进来,因此暂时只存储二叉树的根节点。
3.3二叉树值的插入
在二叉树中插入值前,首先要想好自己所构建的二叉树的形式。本文预构建的一个二叉树如 下:
我们可以先构建出八个结点记为A->H,分别对应每一层按顺序遍历的结点。
int main(){ Node a,b,c,d,e,f,g,h; //给结点赋值 a.data = 8; b.data = 3; c.data = 2; d.data = 6; e.data = 1; f.data = 7; g.data = 4; h.data = 5; //这是给结点之间连接 a.lchild = &b; a.rchild = &c; b.rchild = &d; c.lchild = &e; c.rchild = &f; d.lchild = &g; f.lchild = &h; //接下来看看能否查到结点g的数据,由于f是a的左节点的右节点的左节点 printf("%d",a.lchild->rchild->lchild->data); }结果没有问题就是:4
当然这种输入结点的方式一点也不优雅,如何只输入要要排列是数据就自动给我生成一个二叉树呢?
要实现这方面功能得考虑以下几个问题,如何在输入的数据中表名二叉树中结点与结点位置的关系以及没有结点的情况如何表示?在此给出二叉树的顺序表示,如
则表示为【 8 , 3 , 2 , x ,6 , 1 ,7 , x ,x , 4 , x , x , x , 5】及将最后一个结点前的结点为空的的点都使用 x 来表示。这样就能将二叉树结点的位置关系以及结点为空的境况给表示清楚。
(不想写了QAQ,先这样吧)
四、二叉树的使用在运用二叉树这种结构的时候,一般是在结点里放置数据,并且只存储根节点的信息,因此根据根节点的信息来取得所有节点的信息便是至关重要的