烟台网站排名优化,一级造价工程师报名时间,网站权重等级,ui培训费用目录 一.链式结构的实现
1.二叉树结点基本结构#xff0c;初始化与销毁#xff1a;
二.链式结构二叉树的几种遍历算法
1.几种算法的简单区分#xff1a;
2.前序遍历#xff1a;
3.中序遍历#xff1a;
4.后序遍历#xff1a;
5.层序遍历#xff08;广度优先遍历B…目录 一.链式结构的实现
1.二叉树结点基本结构初始化与销毁
二.链式结构二叉树的几种遍历算法
1.几种算法的简单区分
2.前序遍历
3.中序遍历
4.后序遍历
5.层序遍历广度优先遍历BFS
三.链式二叉树的几种使用
1.计算树的结点个数
2.计算树的叶子结点个数
3.计算树的第k层结点个数
4.计算树的深度 5.查找结点为X的结点
6.判断二叉树是否为完全二叉树 一.链式结构的实现 1.二叉树结点基本结构初始化与销毁 1⽤链表来表示⼀棵⼆叉树即⽤链来指示元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩子和右孩子所在的链结点的存储地址 其结构如下 2二叉树结点的初始化与树的创建 #includeTree.h
//结点的初始化
BTNode* buyNode(char x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));node-data x;node-left node-right NULL;return node;
}
//树结构的创建
BTNode* creatBinaryTree()
{BTNode* nodeA buyNode(A);BTNode* nodeB buyNode(B);BTNode* nodeC buyNode(C);BTNode* nodeD buyNode(D);BTNode* nodeE buyNode(E);BTNode* nodeF buyNode(F);nodeA-left nodeB;nodeA-right nodeC;nodeB-left nodeD;nodeC-right nodeE;nodeC-right nodeF;
} 3链式二叉树的销毁 使用后序遍历我在下文会写出具体操作 void BinaryTreeDestory(BTNode** root)
{//这里因为要改变根节点应该传入的是根节点的地址所以得拿二级指针接收//递归出口if ((*root) NULL){return;}//自叶向根方向的释放//如果先释放的话就找不到叶子节点了BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
} 二.链式结构二叉树的几种遍历算法 1.几种算法的简单区分 举一个普遍的例子具体说明一下如图 2.前序遍历 简单说明一下前序遍历的基本逻辑 假设一个树 A / \ B C / \ D E 那么其遍历过程为 访问根节点 A 。 递归遍历左子树以 B 为根 访问 B 递归遍历左子树以 D 为根 访问 D 递归遍历右子树以 E 为根 访问 E 递归遍历右子树以 C 为根 访问 C //前序遍历
void preOrder(BTNode* root)
{//头 左 右//递归出口if (root NULL){printf(NULL);return;}printf(%c,root-data);preOrder(root-left);preOrder(root-right);
}
3.中序遍历
void inOrder(BTNode* root)
{//左 头 右//递归出口if (root NULL){printf(NULL);return;}inOrder(root-left); //注意别调用错了调用中序的printf(%c, root-data);inOrder(root-right);
}
4.后序遍历
void postOrder(BTNode* root)
{//递归出口if (root NULL){printf(NULL);return;}postOrder(root-left);postOrder(root-right);printf(%c, root-data);
} 总结如上述所示前中后序遍历的代码共同点也是相当明显了主要就是递归顺序左右子树的顺序不同而影响的代码输出顺序不同其根本上来说就是函数栈帧的不断进行嵌套式的创建与销毁如果挨个遍历可能会显得比较复杂但通过代码所示的这种递归算法前中后序的遍历实现也显得十分简洁明了 但还有一点尤其需要注意就是不同于层序遍历我上面所说的三种遍历都属于深度优先遍历DFS而层序遍历却属于广度优先遍历关于这两大类遍历的优劣我会在实现层序遍历后作详细介绍 5.层序遍历广度优先遍历BFS 思路 借助数据结构队列先通过根节点入队列再循环判断队列是否为空不为空则取队头然后出队头并将队头结点的左右孩子入队列 (由于后续层序遍历的实现需要用到好些队列的知识所有我先将队列的一些简单用法附在下面需要的可以稍微看看) //定义结点结构
typedef int QDataTpe;
typedef struct QueueNode
{struct QueneNode* next;QDataTpe data;
}QueueNode;//定义队列的结构
typedef struct Queue
{QueueNode* phead;//队头QueueNode* ptail;//队尾int size;
}Queue;BTNode* buyNode(char x);//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;
}//入队从队尾入
void QueuePush(Queue* pq, QDataTpe x)
{assert(pq);//申请一个结点QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc failed);exit(1);}newnode-data x;newnode-next NULL;//队列为空newnode是对头也是队尾if (pq-phead NULL){pq-phead pq-ptail newnode;}else //队列非空尾插{pq-ptail-next newnode;pq-ptail pq-ptail-next;}pq-size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead 0;
}//出队从队头出
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//只有一个结点的情况下要把队尾和队头的两个指针都考虑到if (pq-phead pq-ptail){free(pq-ptail);pq-phead pq-ptail NULL;}QueueNode* next pq-phead-next;free(pq-phead);pq-phead next; pq-size--;
}//取队头数据
QDataTpe QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq-phead-data;
}
//取队尾数据
QDataTpe QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq-ptail-data;
}//队列的销毁
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;
}//取队列元素个数
int QueueSize(Queue* pq)
{return pq-size;
}//层序遍历
void LeveIOrder(BTNode* root)
{Queue q;//创建一个队列QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){//取队头出队头打印结点值BTNode* top QueueFront(q);QueuePop(q);printf(%c, top-data);//将队头结点的非空左右孩子结点入队列if (top-left){QueuePush(q, top-left);}if (top-right){QueuePush(q, top-right);}QueuDestroy(q);}} 小结 DFS 优点深度优先遍历 节点少时效率高节省内存 适合需要“全探索”或“找到任意解即可”的场景如迷宫路径 DFS 缺点 可能陷入无限循环需记录已访问节点 不保证最短路径除非剪枝优化 BFS 优点 广度优先遍历 保证找到最短路径无权图中 层级分明易于理解 BFS 缺点 内存占用大需存储整个层级节点 不适合大规模数据或深层结构如树深度极大 三.链式二叉树的几种使用 1.计算树的结点个数 法一把size作为一个函数的形参然后把这个树遍历一遍每遍历一个节点就size节点个数加一但需要注意的是需要传入size的地址才能改变size的值 void BinaryTreeSize(BTNode* root,int* size)
{if (root NULL){return;}(*size);BinaryTreeSize(root-left,size);BinaryTreeSize(root-right, size);
} 法二递归 节点个数左子树节点个数右子树节点个数所以我们以此为基础递归就可以了 int BinaryTreeSize(BTNode* root)
{//节点个数左子树节点个数右子树节点个数//递归出口if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
} 2.计算树的叶子结点个数 叶子结点即没有左右孩子结点的结点4 int BinaryTreeLeafSize(BTNode* root)
{//递归出口if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
} 3.计算树的第k层结点个数 如上图当k1时就是最底层结点因此从最底层往上嵌套遍历就可以实现 int BinaryTreeLeafSize(BTNode* root)
{//递归出口if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
} 4.计算树的深度 int BinaryTreeDeep(BTNode* root)
{//计算树的深度if (root NULL){return 0;}int lefDep BinaryTreeDeep(root-left);int rigDep BinaryTreeDeep(root-right);return 1 (lefDep rigDep ? lefDep : rigDep);
} 5.查找结点为X的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//递归出口if (root NULL){return 0;}if (root-data x){return root;}//代码走到这里证明根节点并不是我们要找的结点//接下来是左右子树各自分开递归搜查BTNode* left BinaryTreeFind(root-left, x);if (left)//由于函数最后返回NULL所以如果这个if条件可以进入就足以说明找到了需要的结点{return root;}BTNode* right BinaryTreeFind(root-right, x);if (right){return root;}return NULL;
}
6.判断二叉树是否为完全二叉树 // 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){//取队头出队头BTNode* top QueueFront(q);QueuePop(q);if (top NULL){break;}//队头结点的左右孩子入队列QueuePush(q, top-left);QueuePush(q, top-right);}//队列不为空继续取队头出队头//1队头存在非空结点----非完全二叉树//2队头不存在非空结点----完全二叉树while (!QueueEmpty(q)){BTNode* top QueueFront(q);QueuePop(q);if (top ! NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} 第一个while是为了验证根结点如果根结点为空直接返回false如果根结点不为空就将树里的结点循环入队列然后继续将子结点入队列并且判断其是否为空同样的第一次循环的的结束条件是当出现空为止因此当来到第二次循环时树的结点里说明已经第一次循环出了空结点而当树是完全二叉树时第二次循环之后队列里应该全是空结点因此只要当第二次循环里出现非空结点时就可以判断其时非完全二叉树这题思路比较复杂可以多想一会 欧克本次关于链式二叉树的知识点就到此为止了相关的题目我也会在未来附上
ok全文终
