学校网站建设介绍范文,蛋糕设计网站,肇庆网站建设方案优化,网站设计师如何让客户信任你目录
一#xff0c;层序遍历算法
1-1#xff0c;队列结构的设立
1-2#xff0c;逻辑分析
二#xff0c;判断单值二叉树
三#xff0c;求二叉树的最大深度 一#xff0c;层序遍历算法 二叉树的层序遍历是一层一层的从左到右遍历#xff0c;现在问题是二叉树不支持随…目录
一层序遍历算法
1-1队列结构的设立
1-2逻辑分析
二判断单值二叉树
三求二叉树的最大深度 一层序遍历算法 二叉树的层序遍历是一层一层的从左到右遍历现在问题是二叉树不支持随机访问因此我们需要借助其它结构来实现这一功能。通常对于这种遍历算法我们要借助队结构的概念。 补充树的层序遍历也叫做广度优先遍历而广度优先遍历通常要借助队列的结构实现。
1-1队列结构的设立 队列的结构相信大家都已非常熟悉了如果队列结构不清楚的可以观看本人以前讲解队列的文章本文在这里就不做过多说明了。我们可定义一个头文件将队列的基础算法写进去其中要注意的是队列中的元素是树中的结点因为往队列中装数据装的是树的结点不可直接装树结点的数据否则设置此结构几乎没用下文分析时会详细说明在这里我们只需先构造队列中的基础算法即可。如下
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef struct Tree DataType;
typedef struct Node {DataType* val;struct Node* next;
}Node;
typedef struct Queue {Node* head;Node* tail;
}Queue;
void QueueInit(Queue* Q) {Q-head Q-tail 0;
}
void QueuePush(Queue* Q, DataType* x) {Node* node (Node*)malloc(sizeof(Node));if (!node) {return;}node-val x;node-next 0;if (!Q-head) {Q-head Q-tail node;}else {Q-tail-next node;Q-tail node;}
}
void QueuePop(Queue* Q) {if (!Q-head) {return;}Node* node Q-head-next;free(Q-head);Q-head node;
}
bool QueueEmpty(Queue* Q) {return Q-head NULL;
}
void QueueDestroy(Queue* Q) {if (!Q-head) {return;}Node* node Q-head-next;while (Q-head ! Q-tail) {free(Q-head);Q-head node;node node-next;}free(Q-head);free(Q);
}
1-2逻辑分析 队列结构设置完后我们要考虑的是如何将每一层的数据从左到右放入队列中。如果直接将树结点中的数据直接导入很显然这跟用不用队列结构没多大关系相当于直接层序遍历二叉树。因此我们要考虑将树中结点导入然后利用结点间相连问题进行层序导入队列中。具体步骤和说明如下 首先要将根结点导入队列然后输出队列中首结点的数据并先将此结点的左孩子导入进队列再将右孩子导入进队列最后删除首结点以此类推不断进行循环当队列为空时相当于已层序遍历完整个二叉树。至于原因是因为我们输出首结点的元素后删除了首结点所以当进行下一次循环将首结点的左右孩子导入时相当于从树的下一层开始从左到右导入数据。
代码如下
void LevelOrder(Tree* root) {//空树直接退出if (!root) {return;}//建立队列结构Queue* Q (Queue*)malloc(sizeof(Queue));QueueInit(Q);//先把根结点推入进去QueuePush(Q, root);//进行遍历先将数据输出导入队列左右孩子后要出队即删除当队为空时已遍历完。while (!QueueEmpty(Q)) {fprintf(stdout, %d , Q-head-val-val);if (Q-head-val-leftchild) {QueuePush(Q, Q-head-val-leftchild);}if (Q-head-val-rightchild) {QueuePush(Q, Q-head-val-rightchild);}QueuePop(Q);}
}
算法演示
//设定队列结构和必要的头文件
#include Queue.h
typedef struct Tree {int val;//数据struct Tree* leftchild;//左孩子结点struct Tree* rightchild;//右孩子结点
}Tree;
//创建二叉树数据为x的结点
Tree* CreatNode(int x) {Tree* node (Tree*)malloc(sizeof(Tree));node-val x;node-leftchild 0;node-rightchild 0;return node;
}
//二叉树的销毁
void TreeDestroy(Tree* root) {if (!root) {return;}TreeDestroy(root-leftchild);TreeDestroy(root-rightchild);free(root);
}
//层序遍历算法(广度优先遍历)
void LevelOrder(Tree* root) {//空树直接退出if (!root) {return;}//建立队列结构Queue* Q (Queue*)malloc(sizeof(Queue));QueueInit(Q);//先把根结点推入进去QueuePush(Q, root);//进行遍历先将数据输出导入队列左右孩子后要出队即删除当队为空时已遍历完。while (!QueueEmpty(Q)) {fprintf(stdout, %d , Q-head-val-val);if (Q-head-val-leftchild) {QueuePush(Q, Q-head-val-leftchild);}if (Q-head-val-rightchild) {QueuePush(Q, Q-head-val-rightchild);}QueuePop(Q);}
}
int main()
{//手动构建二叉树Tree* node1 CreatNode(1);Tree* node2 CreatNode(2);Tree* node3 CreatNode(3);Tree* node4 CreatNode(4);Tree* node5 CreatNode(5);Tree* node6 CreatNode(6);Tree* node7 CreatNode(7);Tree* node8 CreatNode(8);Tree* node9 CreatNode(9);Tree* node10 CreatNode(10);Tree* node11 CreatNode(11);Tree* node12 CreatNode(12);Tree* node13 CreatNode(13);Tree* node14 CreatNode(14);Tree* node15 CreatNode(15);//结点的连接node1-leftchild node2;node1-rightchild node4;node2-leftchild node3;node4-leftchild node5;node4-rightchild node6;node2-rightchild node7;node3-leftchild node8;node3-rightchild node9;node7-leftchild node10;node7-rightchild node11;node5-leftchild node12;node5-rightchild node13;node6-leftchild node14;node6-rightchild node15;LevelOrder(node1);TreeDestroy(node1);return 0;
} 接下来我们用经典题型来进行解说二叉树的运用。
二判断单值二叉树
单值二叉树二叉树的每个结点都具有相同的值。
分析 我们可遍历二叉树并且每一个节点值都和根节点的值进行比对如果不等于根节点的值则不是单值树。
代码如下
/**以下是二叉树的结构式* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool JudgeTree(struct TreeNode* root, int x) {if (!root) {return true;} if (root-val ! x) {return false;}//当有一个不满足条件时一直返回的是false最终结果也是false return JudgeTree(root-left, x) JudgeTree(root-right, x);
}bool isUnivalTree(struct TreeNode* root) {if (!root) {return true;}return JudgeTree(root, root-val);
}举一反三 当我们遇到像bool类型的二叉树算法时可以像上述题型一样系统给定函数的类型和参数与我们遍历思路不同时可再创建一个返回类型和参数都令我们满意的函数。如以上题中系统给定的函数是bool isUnivalTree(struct TreeNode* root)参数令我们不满意我们可创建一个函数bool JudgeTree(struct TreeNode* root, int x)有个参数x以便后面我们比较。 还有像bool类型的函数一般不好在其中递归遍历所以当递归遍历时经常在返回值中运用
逻辑运算符连接遍历。如以上题中return JudgeTree(root-left, x) JudgeTree(root-right, x)。在此函数中用符号连接进行遍历。 三求二叉树的最大深度
题解二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
分析 显然本题也需要我们运用二叉树基础算法中的遍历算法。求解最大深度我们可在递归遍历时记录在此函数中以root为根结点左右孩子的总共数量大的一方就是以此函数中root为根结点的子二叉树的最大深度即当最终返回时返回的是二叉树的最大深度。
代码如下
/** * 二叉树的结构* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int maxDepth(struct TreeNode* root){if (!root) {return 0;}//记录左孩子的数量int leftsize maxDepth(root-left) 1;//记录右孩子的数量int rightsize maxDepth(root-right) 1;//返回以此递归函数中的子二叉树的最大深度return (leftsize rightsize) ? leftsize : rightsize;
} 对于本题没有什么好扩充的知识讲解此题的目的是让我们更好的运用递归理清其中的逻辑该如何控制递归的走向。 学习建议二叉树的运用是建立在二叉树基础算法之上在学习到这一方面必须要把二叉树的基本算法理解明白之后再上手。否则根基不稳后面会很吃亏。
