数据结构 - 树与二叉树
一.普通有序树的定义
1.树的概念及特性
二.二叉树的定义
1.二叉树的性质
2.二叉树的分类
①.满二叉树
每一层的结点数都为最大值
②.完全二叉树
完全二叉树是由满二叉树，从下向上，从右向左依次擦除若干个结点
3.二叉树的结构
三.链式二叉树的创建
1.链式二叉树的结构体定义
typedef int data_t;
typedef struct btreenode
{
data_t data; //数据域
struct btreenode *lchild,*rchild; //左结点与右结点的指针
}btree_node_t;2.二叉树的创建
/**
* @description: 使用键盘输入，创建一个二叉树
* @param : 无
* @return : 创建的二叉树的根结点指针
*/
btree_node_t *Btree_Create(void)
{
data_t ch; //存储键盘输入的数据
btree_node_t *new; //指向新创建的结点
/* 1.键盘输入要创建的结点的 data域 的值 */
scanf("%c",&ch);
if('#' == ch)
return NULL;
else
{
/* 2.创建根结点 */
new = (btree_node_t *)malloc(sizeof(btree_node_t));
if(NULL == new)
{
perror("malloc error");
return NULL;
}
/* 3.为根结点填充数据 */
new->data = ch;
/* 4.用相同的方法创建左子树 */
new->lchild = Btree_Create();
/* 5.用相同的办法创建右子树 */
new->rchild = Btree_Create();
}
/* 6.返回根结点指针 */
return new;
}四.二叉树的遍历
1.先序序列、中序序列、后序序列
①.先序序列：
第一次经过结点的时候，去访问这个结点
②.中序序列：
第二次经过结点的时候，去访问这个结点
③.后续序列：
第三次经过结点的时候，去访问这个结点
④.层次遍历
2.遍历算法
①.先序递归遍历算法
/**
* @description: 二叉树的先序遍历递归算法
* @param - t : 要遍历二叉树的指针
* @return : 无
*/
void Pre_order(btree_node_t *t)
{
/* 树不为空 */
if(NULL != t)
{
/* 1.访问根结点 */
printf("%c ",t->data);
/* 2.先序遍历左子树 */
Pre_order(t->lchild);
/* 3.先序遍历右子树 */
Pre_order(t->rchild);
}
}②.中序递归遍历算法
/**
* @description: 二叉树的中序遍历递归算法
* @param - t : 要遍历的二叉树的指针
* @return : 无
*/
void Mid_order(btree_node_t *t)
{
/* 树不为空 */
if(NULL != t)
{
/* 1.中序遍历左子树 */
Mid_order(t->lchild);
/* 2.访问根结点 */
printf("%c ",t->data);
/* 3.中序遍历右子树 */
Mid_order(t->rchild);
}
}③.后序递归遍历算法啊
/**
* @description: 二叉树的后序遍历递归算法
* @param - t : 要遍历的二叉树的指针
* @return : 无
*/
void Post_order(btree_node_t *t)
{
/* 树不为空 */
if(NULL != t)
{
/* 1.后序遍历左子树 */
Post_order(t->lchild);
/* 2.后序遍历右子树 */
Post_order(t->rchild);
/* 3.访问根结点 */
printf("%c ",t->data);
}
}
④.层次遍历算法
/**
* @description: 二叉树的层次遍历算法
* @param - t : 要遍历的二叉树的指针
* @return : 无
*/
void Level_order(btree_node_t *t)
{
linkqueue_t *q; //链式队列
/* 一.初始化一个链式队列 */
q = Linkqueue_Create();
/* 二.开始层次遍历 */
while(t != NULL)
{
/* 1.访问 t 指向的结点数据 */
printf("%c ",t->data);
/* 2.若 t 的左指针不为空 ， 则入队 */
if(t->lchild != NULL)
{
Linkqueue_In(q,t->lchild);
}
/* 3.当 t 的右指针不为空 ， 则入队 */
if(t->rchild != NULL)
{
Linkqueue_In(q,t->rchild);
}
/* 4.队列不为空 ， 则出队 */
if(!Linkqueue_is_empty(q))
Linkqueue_Out(q,&t);
else
break;
}
}⑤.先序非递归遍历算法
/**
* @description: 二叉树的先序遍历非递归方法
* @param - t : 要操作的二叉树的指针
* @return : 无
*/
void Unpre_order(btree_node_t *t)
{
/* 一.创建一个空栈 */
linkstack_t *s;
s = Linkstack_Create();
if(NULL == s)
{
printf("create stack error!\n");
return ;
}
/* 二.先序遍历非递归算法,循环遍历 */
/* 根结点是否为空，不为空则访问该结点。 为空且栈不为空，则出栈以访问右结点 */
while(t != NULL || !Linkstack_Empty(s))
{
/* 1.若根结点不为空，则访问根结点 */
if(t != NULL)
{
printf("%c ",t->data);
/* 2.若该根结点的右结点不为空 ， 则右结点的指针进栈 */
if(NULL != t->rchild)
{
Linkstack_Push(s,t->rchild);
}
/* 3.下一次遍历该结点的左子结点 */
t = t->lchild;
}
/* 4.若该结点为空且栈内有右结点时 ， 出栈以访问右结点 */
else
{
t = Linkstack_Pop(s);
}
}
} 原文地址：https://blog.csdn.net/kaneki_lh/article/details/142302777
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！