数据结构 - 树与二叉树
一.普通有序树的定义
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);elsebreak;}
}⑤.先序非递归遍历算法
/*** @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);}}
}