学过数据结构的都知道树，那么什么是树？
树（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 == (*pRoot)->data)
{
return pRoot;//&pt->root;
}
//3.若目标元素小于根节点元素值,左子树查找
else if(data < (*pRoot)->data)
{
return find(&(*pRoot)->left,data);
}
//4.若目标元素大于根节点元素,去右子树查找
else
{
return find(&(*pRoot)->right,data);
}
}
//实现查找一个指定的节点
//返回 指向目标元素所在节点的指针 的地址
Node** find_data(Tree* pt,int data)
{
//调用递归函数实现查找
return find(&pt->root,data);
}
//实现清空的递归函数
void clear(Node** pRoot)
{
//判断二叉树是否为空
if(*pRoot != NULL)
{
//1.清空左子树
clear(&(*pRoot)->left);
//2.清空右子树
clear(&(*pRoot)->right);
//3.清空根节点
free(*pRoot);
*pRoot = NULL;
}
}
//实现清空树中的所有节点
void clear_data(Tree* pt)
{
//调用递归函数实现清空
clear(&pt->root);
//二叉树的节点个数清零
pt->cnt = 0;
}
//实现创建新节点
Node* create_node(int data)
{
Node* pn = (Node*)malloc(sizeof(Node));
pn->data = data;
pn->left = NULL;
pn->right = NULL;
return pn;
}
//遍历的递归函数
void travel(Node* pRoot)
{
//判断二叉树不为空时才需要遍历
if(pRoot != NULL)
{
//1.遍历左子树
travel(pRoot->left);
//2.遍历根节点
printf("%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 = data;
//pn->left = NULL;
//pn->right = NULL;
//2.插入新节点到二叉树中,调用递归函数
insert(&pt->root,create_node(data));
//3.二叉树中节点个数加1
pt->cnt++;
}
运行结果：