为什么要建设网站,手机智能建网站,如何建单页网站栏目,新竹自助建站系统#x1f525;Go for it!#x1f525; #x1f4dd;个人主页#xff1a;按键难防 #x1f4eb; 如果文章知识点有错误的地方#xff0c;请指正#xff01;和大家一起学习#xff0c;一起进步#x1f440; #x1f4d6;系列专栏#xff1a;数据结构与算法 #x1f52… Go for it! 个人主页按键难防 如果文章知识点有错误的地方请指正和大家一起学习一起进步 系列专栏数据结构与算法 如果感觉博主的文章还不错的话还请 点赞收藏⭐️ 留言支持 一下博主哦 目录
树
二叉树
二叉树定义方法链式存储
层次建树实战 ①辅助队列链式存储实现
②建树源码
二叉树的遍历
①前序遍历
②中序遍历 ③后序遍历
④层次遍历
汇总 树
树是nn ≥ 0个节点的有限集。当n 0时称为空树。在任意一棵非空树中应满足
1有且仅有一个特定的结点的称为根的结点。
2当n 1时其余节点可分为mm 0个 互不相交的有限集T1, T2,…, Tm其中每个集合 本身又是一棵树并且称为根的子树。 特点
树作为一种逻辑结构同时也是一种分层结构具 有以下两个特点
1树的根结点没有前驱除根结点外的所有结点有且只有一个前驱。
2树中所有结点可以有零个或多个后继。
二叉树
二叉树是另一种树形结构其特点是每个结点至多只有两棵子树 即二叉树中不存在度大于2的结点并且二叉树的子树有左右之分其次序不能任意颠倒。 与树相似二叉树也以递归的形式定义。二叉树是nn ≥ 0个 结点的有限集合
① 或者为空二叉树即n 0。
② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
满二叉树在一颗二叉树中如果所有分支结点都有左子结点和右子结点并且叶结点都集中在二叉树的最底层这样的二叉树称为满二叉树。 完全二叉树
完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值完全二叉树仅要求除最后一层外的节点数达到最大值也就是说最后一层可以不满。但是最后一层从左往右不能有中断。 二叉树定义方法链式存储
typedef char BiElemType;
typedef struct BiTNode{BiElemType c;//c就是书籍上的datastruct BiTNode *lchild;//该二叉树的左孩子struct BiTNode *rchild;//该二叉树的右孩子
}BiTNode, *BiTree;
解释typedef重命名了两个数据类型
分别是将struct BiTNode重命名为BiTNode将struct BiTNode*重命名为BiTree
前者是个结构体后者是个指向该结构体的指针
用BiTNode创建变量就是创建一个结构体树的结点
用BiTree创建变量就是指向这个结构体的指针用于接受动态内存开辟返回的指针
层次建树实战
将abcdefghij用二叉树的方式存起来。 ①辅助队列链式存储实现
每多一个分支就当做一个元素入队每当一个结点都有左右孩子出队该节点。 所以只要满3个结点就说明有一个树的结点存满两个分支这样就需要删除第一个结点。
保证第一个结点始终不满两个分支。 实现
typedef struct LinkNode//LinkNode结构体是辅助队列的结点
{BiTree p;//数据域存放树的结点的地址值struct LinkNode *next;//指针域辅助队列中下一个结点
}LinkNode;
typedef struct//结构体用于存放辅助队列头结点和队列尾结点的指针
{ LinkNode* front, *rear;
}LinkQueue;
void InitQueue(LinkQueue Q) //初始化头尾指针就是创建头结点然后头尾指针都指向这一头结点
{Q.front Q.rear (LinkNode*)malloc(sizeof(LinkNode));//为辅助队列头结点申请空间//初始化时头尾指针都指向这一头结点Q.front-next NULL;//头结点的next指针为NULL
}
void EnQueue(LinkQueueQ, BiTree x)//入队尾部插入法
{LinkNode *s (LinkNode *)malloc(sizeof(LinkNode));//为入队的元素申请空间s-p x; s-next NULL;//新申请的结点作为最后一个结点Q.rear-next s;//先让前一结点Q.rear的指针域指向新插入的结点Q.rear s;//然后再让Q.rear变为指向尾部的那个结点
}
//出队 头部删除法
bool DeQueueF(LinkQueue Q)
{//front始终指向头结点但头结点什么都没存LinkNode *q Q.front-next;//将第一个节点存入qQ.front-next q-next;//断链保留第一个结点的指针域让头节点指向第二个结点free(q);return true;
} ②建树源码
注释的很详细
#include stdio.h
#include stdlib.h
typedef char BiElemType;
typedef struct BiTNode{BiElemType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode, *BiTree;
typedef struct LinkNode//LinkNode结构体是辅助队列的结点
{BiTree p;//树的某一个结点的地址值不是数值struct LinkNode *next;//辅助队列中下一个结点
}LinkNode;
typedef struct //结构体用于存放辅助队列头结点和队列尾结点的指针
{ LinkNode* front, *rear;
}LinkQueue;
void InitQueue(LinkQueue Q) //初始化头尾指针就是创建头结点然后头尾指针都指向这一头结点
{Q.front Q.rear (LinkNode*)malloc(sizeof(LinkNode));//为辅助队列头结点申请空间//初始化时头尾指针都指向这一头结点Q.front-next NULL;//头结点的next指针为NULL
}
void EnQueue(LinkQueueQ, BiTree x)//入队尾部插入法
{LinkNode *s (LinkNode *)malloc(sizeof(LinkNode));//为入队的元素申请空间s-p x; s-next NULL;//新申请的结点作为最后一个结点Q.rear-next s;//先让前一结点Q.rear的指针域指向新插入的结点Q.rear s;//然后再让Q.rear变为指向尾部的那个结点
}
//出队 头部删除法
bool DeQueueF(LinkQueue Q)
{//front始终指向头结点但头结点什么都没存LinkNode *q Q.front-next;//将第一个节点存入qQ.front-next q-next;//断链保留第一个结点的指针域让头节点指向第二个结点free(q);return true;
}
int main()//二叉树的建树层次建树
{LinkQueue Q;//创建辅助队列头尾指针InitQueue(Q);//初始化头尾指针BiTree pnew;//用来指向新申请的树结点的指针BiTree tree NULL;//树根的指针char c;//输入内容为 abcdefghijwhile (scanf(%c, c)){if (c \n){break;}pnew (BiTree)calloc(1, sizeof(BiTNode));//calloc申请空间并对空间进行初始化赋值为0pnew-data c;//数据放进去EnQueue(Q, pnew);//将新创建的树的结点的地址入队辅助队列//下面是建树的过程if (NULL tree)//空树{tree pnew; //tree指向树的根节点continue;//该节点为树的第一个节点//直接跳到循环的判断部分}else {if (NULL Q.front-next-p-lchild)//如何把新结点放入树{//Q.front-next为辅助队列第一个结点Q.front-next-p-lchild pnew;//把新结点放到要插入结点的左边}else if (NULL Q.front-next-p-lchild){Q.front-next-p-rchild pnew;//把新结点放到要插入结点的右边DeQueue(Q);//左右都放了结点后辅助队列该删除第一个节点了//该函数只用于出队不保存出队结点的数据}}}return 0;
} 二叉树的遍历
①前序遍历
首先前序遍历是先打印自身再打印左子树再打印右子树我们通 过 PreOrder 函数来实现 //递归实现
//abdhiejcfg 前序遍历前序遍历就是深度优先遍历
void PreOrder(BiTree p)
{if (p ! NULL){putchar(p-data);PreOrder(p-lchild);PreOrder(p-rchild);}
} ②中序遍历
中序遍历是先打印左子树再打印当前结点再打印右子树我 们通过 InOrder 函数来实现。 //中序遍历 hdibjeafcg
void InOrder(BiTree p)
{if (p ! NULL){InOrder(p-lchild);putchar(p-data);InOrder(p-rchild);}
} ③后序遍历
后序遍历是先打印左子树再打印右子树最后打印当前结点 我们通过 PostOrder 函数来实现。 //hidjebfgca 后序遍历
void PostOrder(BiTree p)
{if (p ! NULL){PostOrder(p-lchild);PostOrder(p-rchild);putchar(p-data);}
} ④层次遍历
二叉树的层次遍历 顾名思义就是指从二叉树的第一层根节点开始从上至下逐层遍历在同一层中则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中按从顶层到底层的次序访问树中元素在同一层中从左到右进行访问。
树根的地址作为辅助队列的第一个结点的数据域然后删除第一个结点保留数据域然后借助树根的地址让自己的左孩子(b)和右孩子(c)分别入队然后打印左孩子数据域(b)再入队左孩子的两个分支(de)然后打印右孩子的数据域入队右孩子的两个分支(fg)然后一直这样循环。就可以把树连根拔起。 void LevelOrder(BiTree T)
{LinkQueue Q1;//辅助队列InitQueue(Q1);//初始化队列BiTree p;//存储出队的结点EnQueue(Q1, T);//树根入队while (!IsEmpty(Q1))//是逻辑反操作{//队列不是空循环继续DeQueue(Q1,p);//出队当前结点//p是出队结点的数据域借助它找到出队结点指向的树的结点的左右孩子putchar(p-data);//打印数据域if (p-lchild ! NULL) //入队左孩子{EnQueue(Q1, p-lchild);}if (p-rchild ! NULL) //入队右孩子{EnQueue(Q1, p-rchild);}}汇总
#include stdio.h
#include stdlib.h
typedef char BiElemType;
typedef struct BiTNode{BiElemType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode, *BiTree;
typedef struct LinkNode//LinkNode结构体是辅助队列的结点
{BiTree p;//树的某一个结点的地址值不是数值struct LinkNode *next;//辅助队列中下一个结点
}LinkNode;
typedef struct //结构体用于存放辅助队列头结点和队列尾结点的指针
{ LinkNode* front, *rear;
}LinkQueue;
void InitQueue(LinkQueue Q) //初始化头尾指针就是创建头结点然后头尾指针都指向这一头结点
{Q.front Q.rear (LinkNode*)malloc(sizeof(LinkNode));//为辅助队列头结点申请空间//初始化时头尾指针都指向这一头结点Q.front-next NULL;//头结点的next指针为NULL
}
bool IsEmpty(LinkQueue Q)
{if (Q.front Q.rear)return true;elsereturn false;
}
void EnQueue(LinkQueueQ, BiTree x)//入队尾部插入法
{LinkNode *s (LinkNode *)malloc(sizeof(LinkNode));//为入队的元素申请空间s-p x; s-next NULL;//新申请的结点作为最后一个结点Q.rear-next s;//先让前一结点Q.rear的指针域指向新插入的结点Q.rear s;//然后再让Q.rear变为指向尾部的那个结点
}
//出队 头部删除法
bool DeQueueF(LinkQueue Q)
{//不保存删除结点数据域//front始终指向头结点但头结点什么都没存LinkNode *q Q.front-next;//将第一个节点存入qQ.front-next q-next;//断链保留第一个结点的指针域让头节点指向第二个结点free(q);return true;
}
bool DeQueue(LinkQueue Q, BiTree x)//出队
{//x用于保存删除结点的数据域if (Q.front Q.rear){return false;}//队列为空//front始终指向头结点但头结点什么都没存LinkNode *q Q.front-next;//将第一个节点存入qx q-p;//获取要出队结点存储的值Q.front-next q-next;//断链保留第一个结点的指针域让头节点指向第二个结点if (Q.rear q)//删除的是最后一个元素{Q.rear Q.front;//队列置为空}free(q);return true;
}
// 递归实现
//abdhiejcfg 前序遍历前序遍历就是深度优先遍历
void PreOrder(BiTree p)
{if (p ! NULL){putchar(p-data);PreOrder(p-lchild);PreOrder(p-rchild);}
}
//中序遍历 hdibjeafcg
void InOrder(BiTree p)
{if (p ! NULL){InOrder(p-lchild);putchar(p-data);InOrder(p-rchild);}
}
//hidjebfgca 后序遍历
void PostOrder(BiTree p)
{if (p ! NULL){PostOrder(p-lchild);PostOrder(p-rchild);putchar(p-data);}
}
void LevelOrder(BiTree T)
{LinkQueue Q1;//辅助队列InitQueue(Q1);//初始化队列BiTree p;//存储出队的结点EnQueue(Q1, T);//树根入队while (!IsEmpty(Q1))//是逻辑反操作{//队列不是空循环继续DeQueue(Q1,p);//出队当前结点//p是出队结点的数据域借助它找到出队结点指向的树的结点的左右孩子putchar(p-data);//打印数据域if (p-lchild ! NULL) //入队左孩子{EnQueue(Q1, p-lchild);}if (p-rchild ! NULL) //入队右孩子{EnQueue(Q1, p-rchild);}}
int main()//二叉树的建树层次建树
{LinkQueue Q;//创建辅助队列头尾指针InitQueue(Q);//初始化头尾指针BiTree pnew;//用来指向新申请的树结点的指针BiTree tree NULL;//树根的指针BiTree de;//char c;//输入内容为 abcdefghijwhile (scanf(%c, c)){if (c \n){break;}pnew (BiTree)calloc(1, sizeof(BiTNode));//calloc申请空间并对空间进行初始化赋值为0pnew-data c;//数据放进去EnQueue(Q, pnew);//将新创建的树的结点的地址入队辅助队列//下面是建树的过程if (NULL tree)//空树{tree pnew; //tree指向树的根节点continue;//该节点为树的第一个节点//直接跳到循环的判断部分}else {if (NULL Q.front-next-p-lchild)//如何把新结点放入树{//Q.front-next为辅助队列第一个结点Q.front-next-p-lchild pnew;//把新结点放到要插入结点的左边}else if (NULL Q.front-next-p-rchild){Q.front-next-p-rchild pnew;//把新结点放到要插入结点的右边DeQueueF(Q);//左右都放了结点后辅助队列该删除第一个节点了//该函数只用于出队不保存出队结点的数据}}}printf(--------前序遍历----------\n);//也叫先序遍历先打印当前结点打印左孩子打印右孩子PreOrder(tree);printf(\n--------中序遍历------------\n);//先打印左孩子打印父亲打印右孩子InOrder(tree);printf(\n--------后序遍历------------\n);//先打印左孩子打印右孩子最后打印父亲PostOrder(tree);printf(\n--------层次遍历-----------\n);LevelOrder(tree);printf(\n);return 0;
} 效果 希望这篇文章能对你有所帮助
