首页 > 代码库 > 数据结构之---二叉树C实现
数据结构之---二叉树C实现
学过数据结构的都知道树。那么什么是树?
树(tree)是包括n(n>0)个结点的有穷集。当中:
(1)每一个元素称为结点(node);
(2)有一个特定的结点被称为根结点或树根(root)。
(3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,当中每个集合Ti(1<=i<=m)本身也是一棵树。被称作原树的子树(subtree)。
树也能够这样定义:树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。
在这样的层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或称为树根。
我们能够形式地给出树的递归定义例如以下:
单个结点是一棵树,树根就是该结点本身。
设T1,T2,..,Tk是树,它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲。则得到一棵新树,结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点,它们都是结点n的子结点。
我们还称T1,T2,..,Tk为结点n的子树。
空集合也是树。称为空树。空树中没有结点。
那么常见树的种类有:满二叉树,全然二叉树,二叉树,红黑树,无序树,哈夫曼树等等。
今天我们主要是来了解二叉树,
1、每一个节点最多有两个子节点的树形结构
2、当中起始节点叫做根节点,除了根节点之外,每一个节点有且仅仅有一个父节点
3、没有不论什么子节点的节点 叫做叶子节点,除了叶子节点之外。每一个节点都能够有两个子节点
4、除了根节点和叶子节点之外。剩下的节点叫枝节点,枝节点有父节点也有子节点
5、二叉树中每层节点均达到最大值,而且除了叶子节点之外每一个节点都有两个子节点。叫做满二叉树
6、二叉树中除了最后一层之外。每层节点数均达到最大值。而且最后一层的节点连续集中在左边,叫全然二叉树
对于二叉树的处理採用递归的方法:
处理(二叉树)
{
if(二叉树为空) 直接处理;
else
{
处理根节点;
处理左子树;=> 递归
处理右子树;=> 递归
}
}
二叉树的存储结构
(1)顺序存储结构
从上到下,从左到右,依次存储每一个节点
(2)链式存储结构
每一个节点中除了存储数据元素本身之外,还须要两指针
如:
typedef struct Node { int data;//数据内容 struct Node* left;//指向左子树 struct Node* right;//指向右子树 }Node;遍历方式
(1)先序遍历 => 根 左子树 右子树
(2)中序遍历 => 左子树 根 右子树
(3)后序遍历 => 左子树 右子树 根
有序二叉树
左子树节点 <= 根节点 <= 右子树节点
主要搜索和查找数据的功能中
接下来我们来看看二叉树的各类操作的实现:
//实现有序二叉树的各种操作 #include <stdio.h> #include <stdlib.h> //定义节点的数据类型 typedef struct Node { int data;//存储数据内容 struct Node* left;//左子树的地址 struct Node* right;//右子树的地址 }Node; //定义有序二叉树的数据类型 typedef struct { Node* root;//记录根节点的地址 int cnt;//记录节点的个数 }Tree; //实现向有序二叉树中插入新节点的操作 void insert_data(Tree* pt,int data); //插入新节点的递归函数 void insert(Node** pRoot,Node* pn); //採用中序遍历方法进行遍历 void travel_data(Tree* pt); //遍历的递归函数 void travel(Node* pRoot); //实现创建新节点 Node* create_node(int data); //实现清空树中的全部节点 void clear_data(Tree* pt); //实现清空的递归函数 void clear(Node** pRoot); //实现查找一个指定的节点 Node** find_data(Tree* pt,int data); //查找的递归函数 Node** find(Node** pRoot,int data); //实现删除指定的节点 void del_data(Tree* pt,int data); //改动指定元素的操作 void modify(Tree* pt,int data,int new_data); //推断二叉树是否为空 int empty(Tree* pt); //推断二叉树是否为满 int full(Tree* pt); //计算二叉树中节点的个数 int size(Tree* pt); //获取根节点的元素值 int get_root(Tree* pt); int main(void) { //创建有序二叉树,而且进行初始化 Tree tree; tree.root = NULL; tree.cnt = 0; //插入新节点,进行遍历 insert_data(&tree,50); travel_data(&tree);//50 insert_data(&tree,70); travel_data(&tree);//50 70 insert_data(&tree,20); travel_data(&tree);//20 50 70 insert_data(&tree,60); travel_data(&tree);//20 50 60 70 printf("------------------\n"); //clear_data(&tree); travel_data(&tree);//20 50 60 70 del_data(&tree,50); travel_data(&tree);//20 60 70 del_data(&tree,30);//删除失败 travel_data(&tree);//20 60 70 del_data(&tree,20); travel_data(&tree);//60 70 printf("--------------------\n"); modify(&tree,10,20);//插入20 travel_data(&tree);//20 60 70 printf("二叉树中根节点的元素是:%d\n",get_root(&tree));//70 printf("二叉树中节点的个数是:%d\n",size(&tree));//3 printf("%s\n",empty(&tree)?"二叉树为空":"二叉树不为空"); printf("%s\n",full(&tree)?"二叉树已满":"二叉树没有满"); return 0; } //改动指定元素的操作 //旧元素不存在时,直接插入新元素就可以 void modify(Tree* pt,int data,int new_data) { //1.删除旧元素 del_data(pt,data); //2.插入新元素 insert_data(pt,new_data); } //推断二叉树是否为空 int empty(Tree* pt) { return NULL == pt->root; } //推断二叉树是否为满 int full(Tree* pt) { return 0; } //计算二叉树中节点的个数 int size(Tree* pt) { return pt->cnt; } //获取根节点的元素值 int get_root(Tree* pt) { if(empty(pt)) { return -1;//表示失败(以后讲到) } return pt->root->data; } //实现删除指定的节点 void del_data(Tree* pt,int data) { //1.查找目标元素所在节点的地址 Node** pp = find_data(pt,data); //2.推断查找失败情况,不须要删除 if(NULL == *pp) { printf("目标元素不存在。删除失败\n"); return; } //3.合并左右子树,左子树插入到右子树中 if((*pp)->left != NULL) { //左子树不为空时。须要插入到右子树中 insert(&(*pp)->right,(*pp)->left); } //4.寻找指针记录要删除的节点地址 Node* q = *pp; //5.将原来指向要删除节点的指针 又一次指向 合并之后的右子树 *pp = (*pp)->right; //6.删除目标元素所在的节点 free(q); q = NULL; //7.节点个数减1 pt->cnt--; } //查找的递归函数 Node** find(Node** pRoot,int data) { //1.推断二叉树是否为空,为空直接返回 if(NULL == *pRoot) { return pRoot;//&pt->root; } //2.比較根节点元素和目标元素的大小,假设相等。直接返回 if(data =http://www.mamicode.com/= (*pRoot)->data)"%d ",pRoot->data); //3.遍历右子树 travel(pRoot->right); } } //採用中序遍历方法进行遍历 void travel_data(Tree* pt) { //调用递归函数进行遍历 travel(pt->root); //打印换行 printf("\n"); } //插入新节点的递归函数 void insert(Node** pRoot,Node* pn) { //1.推断二叉树是否为空,假设为空则让根节点指针直接指向新节点 if(NULL == *pRoot) { *pRoot = pn; return; } //2.假设二叉树非空,比較根节点和新节点大小 //2.1 假设根节点大于新节点,插入左子树 if((*pRoot)->data > pn->data) { insert(&(*pRoot)->left,pn); } //2.2 假设根节点小于等于新节点,插入右子树 else { insert(&(*pRoot)->right,pn); } } //实现向有序二叉树中插入新节点的操作 void insert_data(Tree* pt,int data) { //1.创建新节点。进行初始化 create_node //Node* pn = (Node*)malloc(sizeof(Node)); //pn->data = http://www.mamicode.com/data;>执行结果:
数据结构之---二叉树C实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。