养老网站建设方案,wordpress首页分类调用,做网站有什么作用,大连城市建设管理局网站一、二叉树
1.1 树
说到树#xff0c;我们暂时忘记学习#xff0c;来看一下大自然的树#xff1a; 哈哈 以上照片是自己拍的#xff0c;大家凑合看看
回归正题#xff0c;那么在数据结构中#xff0c;树是什么呢#xff0c;通过上面的图片大家也可以理解
树是一种非…一、二叉树
1.1 树
说到树我们暂时忘记学习来看一下大自然的树 哈哈 以上照片是自己拍的大家凑合看看
回归正题那么在数据结构中树是什么呢通过上面的图片大家也可以理解
树是一种非线性的数据结构 像这样 有多个节点组成的有一定层次关系的结构像是一颗相对于天空逆生长的一颗树节点像是一片片树叶黑色的线条像是树枝而最顶上的那个节点像是树根因此得名 树
2.2 二叉树
二叉树长什么样子呢 来看一下大自然的 “二叉树” 百度出来的图 是不是下面这个样子
从根开始开始分叉每次只分两个叉就这样一直分下去 二叉树有什么特点呢 1.最顶上的那个节点叫做整棵树的 根节点 2.根据根节点可以将整棵树划分为 左右子树 3.叶子节点像最末端的 8~15 没有继续分叉的就是叶子节点了只要还继续有分叉的不被叫做叶子节点叶子没法分叉了对吧 4.Parents 双亲节点(父母节点) 像 1 就是 2 、3 的 双亲节点有时候也叫父节点或者说相对于 4 5 来说2 就像是根节点一样 5. 左孩子、右孩子 像 4 就是 2 的左孩子节点、5 是 2 的右孩子节点 6.层4 层 7.树的高度每加一层 代表树的高度 1 像上图树的高度就是 4 8.节点的度 这里的度指的是 “出度” 就是 一个 双亲节点 有几个 孩子节点 像 节点 2 的 度就是 2而像之前说的 不是二叉树的树像这样节点 1 的出度就是 4 大概了解了二叉树的特点之后我们再来看一下下面这两个比较特殊的二叉树
2.2.1 满二叉树
也就是每一层的节点数都达到最大值满满的没有空缺的除了最后一层的叶子节点外所有的节点都拥有两个孩子节点就是下面这个样子
2.2.2 完全二叉树
完全二叉树就是在满二叉树的基础上允许每个节点不一定分两个叉也就是说 满二叉树除了叶子节点其他的所有节点的度都是 2 完全二叉树并不是所有的节点的度都是 2 但是 这一特定仅限定于倒数第二层的节点例如
允许 节点 9 的 度 为 1 每个节点的子节点(左孩子、右孩子必须严格按照现有左再有右的顺序 不允许 1.没有左孩子节点但是有右孩子节点例如
2.从上至下按层往下除了最后一层其他层未达到最大节点数例如 总结 满二叉树 从上到下从左至右从 0 ~ n 中间 不间断 完全二叉树每一层(根节点为第 0 层)的节点数都满足 2^n 个
二、顺序存储构建二叉树
例如给定一个vector 包含若干个元素要求按照元素的顺序构建出一颗二叉树 刚开始可能没有思路那我们先看一下二叉树的特点 1.需要存储当前节点的值 2.通过该节点可以找到左孩子、右孩子 通过上述两个特点我们可以想象出二叉树每个节点的大概结构 1.data 存储节点的值 2.left 指针 访问该节点的左孩子节点 3.right 指针访问该节点的右孩子节点 代码则为
struct TreeNode
{int val;TreeNode* left;TreeNode* right;
};二叉树的节点类型确定了那么我们如何将数组中的元素构建成一个逻辑上的树形结构呢 我们来分析一下数组元素下标与构建成功之后的二叉树的下标关系 通过分析二叉树中元素下标我们可以总结一下规律 设 当前节点的元素下标为 n 那么该节点的左孩子 节点元素下标为 2n 1,右孩子节点元素下标为 2n2; 例如 现在将节点和数组元素的关系理清之后接下来需要考虑如何将数组中的元素逐个按照二叉树中从上至下从左至右构建。
这里我们需要用到队列来控制从上至下、从左至右顺序 通过入队(根、左、右)、取队头、出队保持顺序通过元素下标控制节点的值 TreeNode* MakeBinaryTree(vectorint vctTemp){if (vctTemp.empty()){cout vector is empty endl;return nullptr;}else{//先将根节点入队TreeNode* root new TreeNode();root-val vctTemp[0];root-left nullptr;root-right nullptr;queueTreeNode* quTemp;quTemp.push(root);//元素下标int n 0;while (!quTemp.empty()){ //先取出队头元素TreeNode* nodeTemp quTemp.front();quTemp.pop();//计算左孩子节点下标int leftIndex 2 * n 1;if (leftIndex vctTemp.size() - 1){//构建左孩子节点TreeNode* leftnode new TreeNode();leftnode-val vctTemp[leftIndex];leftnode-left nullptr;leftnode-right nullptr;nodeTemp-left leftnode;quTemp.push(leftnode);}//计算右孩子节点下标int rightIndex 2 * n 2;if (rightIndex vctTemp.size() - 1){//构建右孩子节点TreeNode* rightnode new TreeNode();rightnode-val vctTemp[rightIndex];rightnode-left nullptr;rightnode-right nullptr;nodeTemp-right rightnode;quTemp.push(rightnode);}//下标 1,每次仅出队一个元素n;}return root;}}三、常规遍历方法
3.1 广度优先遍历
广度优先遍历 英文简称为BFS (Breadth-First-Search) 广度优先从上至下从左至右依次进行遍历这里是不是想到了我们构建的时候也是按照从上至下从左至右的构建顺序没错这种方法就是 BFS 广度优先遍历 按照构建的思路我们同样需要一个队列来辅助我们进行顺序控制
图示 直到最后一个叶子节点 7 pop 出去queue 为空循环结束整个二叉树也遍历完成
代码示例 void BFS(TreeNode* root){if (root nullptr){cout root is empty endl;}else{vectorint vctResult;queueTreeNode* quTemp;//先将根节点入队quTemp.push(root);vctResult.push_back(root-val);while (!quTemp.empty()){//取队头TreeNode* nodeTemp quTemp.front();quTemp.pop();//左孩子不为空先将左孩子入队if (nodeTemp-left ! nullptr){quTemp.push(nodeTemp-left);vctResult.push_back(nodeTemp-left-val);}//右孩子不为空再将右孩子入队if (nodeTemp-right ! nullptr){quTemp.push(nodeTemp-right);vctResult.push_back(nodeTemp-right-val);}}//打印元素Print(vctResult);}}运行
3.2 深度优先遍历
深度优先遍历不同于广度优先那样一层一层、从左至右遍历而是按照前序或中序、或后序那样从根节点不断的向下遍历并将整棵树分左右子树先将一颗子树遍历完达到该子树的叶子节点)再去遍历另一棵树因此被称为深度优先遍历。 深度优先遍历顺序又分为一下三种遍历方法
以下是我整理的一篇二叉树的 前/中/后序 逻辑图形示例不清楚逻辑的可以先看一下 二叉树的前序/中序/后序遍历新手入门介绍
图示 3.2.1前序遍历
前序遍历遍历顺序(先根、再左、再右) DLR
递归遍历代码为 void DLR(TreeNode* root){if (root nullptr){return;}cout root-val ;DLR(root-left);DLR(root-right);}关于递归的思想我们这里以前序遍历做详细的步骤分析帮助大家理解递归的思路和思想
关于递归大家可以有时候想不到递归函数如何去写可以考虑以下三个方面来思考递归怎么写 1.函数调用自身 2.函数终止条件 3.向终止条件前进的执行动作 例如 //递归函数本身void DLR(TreeNode* root){//终止条件if (root nullptr){return;}cout root-val ;//不断向叶子节点遍历逼近 root nullptr 条件//调用函数自身DLR(root-left);DLR(root-right);}3.2.2 中序遍历
中序遍历遍历顺序(先左、再根、再右) 递归遍历代码为 void LDR(TreeNode* root){if (root nullptr){return;}LDR(root-left);cout root-val ;LDR(root-right);}3.2.3后序遍历
后序遍历遍历顺序(先左、再右、再根) 递归遍历代码为 //后序遍历void LRD(TreeNode* root){if (root nullptr){return;}LRD(root-left);LRD(root-right);cout root-val ;}完整测试代码如下 BinaryTree.h
#pragma once
#includeiostream
#includevector
#includequeue
using namespace std;struct TreeNode
{int val;TreeNode* left;TreeNode* right;
};class BinaryTree
{
public:BinaryTree(){}~BinaryTree(){}TreeNode* MakeBinaryTree(vectorint vctTemp){if (vctTemp.empty()){cout vector is empty endl;return nullptr;}else{TreeNode* root new TreeNode();root-val vctTemp[0];root-left nullptr;root-right nullptr;queueTreeNode* quTemp;quTemp.push(root);int n 0;while (!quTemp.empty()){TreeNode* nodeTemp quTemp.front();quTemp.pop();int leftIndex 2 * n 1;if (leftIndex vctTemp.size() - 1){TreeNode* leftnode new TreeNode();leftnode-val vctTemp[leftIndex];leftnode-left nullptr;leftnode-right nullptr;nodeTemp-left leftnode;quTemp.push(leftnode);}int rightIndex 2 * n 2;if (rightIndex vctTemp.size() - 1){TreeNode* rightnode new TreeNode();rightnode-val vctTemp[rightIndex];rightnode-left nullptr;rightnode-right nullptr;nodeTemp-right rightnode;quTemp.push(rightnode);}n;}return root;}}void BFS(TreeNode* root){if (root nullptr){cout root is empty endl;}else{vectorint vctResult;queueTreeNode* quTemp;quTemp.push(root);vctResult.push_back(root-val);while (!quTemp.empty()){TreeNode* nodeTemp quTemp.front();quTemp.pop();if (nodeTemp-left ! nullptr){quTemp.push(nodeTemp-left);vctResult.push_back(nodeTemp-left-val);}if (nodeTemp-right ! nullptr){quTemp.push(nodeTemp-right);vctResult.push_back(nodeTemp-right-val);}}cout BFS BinaryTree Result is: endl;Print(vctResult);}}//前序遍历void DLR(TreeNode* root){if (root nullptr){return;}cout root-val ;DLR(root-left);DLR(root-right);}//中序遍历void LDR(TreeNode* root){if (root nullptr){return;}LDR(root-left);cout root-val ;LDR(root-right);}//后序遍历void LRD(TreeNode* root){if (root nullptr){return;}LRD(root-left);LRD(root-right);cout root-val ;}void Print(vectorint vctTemp){for (auto a : vctTemp){cout a ;a;}cout endl;}
private:vectorint m_vector;};BinaryTree.cpp
#includeBinaryTree.h
int main()
{cout please input 10 numbers endl;int n 0;vectorint vctTemp;while (n ! 10){int a;cin a;vctTemp.push_back(a);n;}BinaryTree test;TreeNode* root test.MakeBinaryTree(vctTemp);test.BFS(root);cout 前序遍历结果为: endl;test.DLR(root);cout endl;cout 中序遍历结果为: endl;test.LDR(root);cout endl;cout 后序遍历结果为: endl;test.LRD(root);cout endl;return 0;
}
