《数据结构》--二叉树【上】

news/2024/11/13 3:21:38/

🌳树的基础内容

树的定义：

树是一种数据结构，它是由n(n>=1)个有限节点组成的一个具有层次关系的集合。把它叫做"树"是因为它看起来像一颗倒挂着的树，也就是说它是根在上，叶在下的。

树的特点：

1.每个节点具有零个或多个子节点

2.没有父节点的节点称为根节点

3.每一个非根节点 有且只有一个父节点

4.除了根节点外，每个子节点可以分为多个不相交的子树

树的术语：

孩子节点：该节点的后继节点均是该节点的孩子节点

父亲节点：该节点的前驱节点就是该节点的父亲节点

兄弟节点：拥有同一个父亲节点的节点之间互为兄弟节点

堂兄弟节点：在同一层次，但父亲节点不同的节点之间互为堂兄弟节点。

祖先：一个节点到根节点的路径上，除了该节点本身之外的节点，均为祖先。

节点的度：节点拥有的子树的数目。

叶子：度为零的节点。（没有子树的节点为叶子节点）

分支节点：度不为零的节点。（不是叶子节点就是分支节点）

树的度：树中节点的最大的度。（ d[tree] = max(d[node1],d[node2],d[node3],...,dn) ）

层次：根节点的层次为1，其余节点的层次等于该节点的父亲节点的层次加1。

树的高度：树中节点的最大层次。

无序树：如果树中节点的各个子节点之间的次序是不重要的,可以交换位置。(只用于表示父子关系)

有序树：如果树中节点的各个子节点之间的次序是重要的,不可以交换位置。(次序有特殊意义)

森林：0个或多个不相交的树组成。对所有的森林加上一个根，森林就成了树；删除树的根，就成了森林。

🌴二叉树

二叉树的定义：

树的每个节点的度最小为0、最大为2，则该树为二叉树。即二叉树的度最大为2。

二叉树的性质：

1.二叉树第i层的节点数目最多为2^{i-1}。( i >= 1)

2.深度为k的二叉树最多有2^{k}-1个节点。(k >= 1)

3.包含n个节点的二叉树的高度至少为log以2为底，n+1的对数：log2 (n+1)。

4.在任何一颗二叉树中，若叶子节点的个数为n0，度为2的节点数为n2，则n0=n2+1

特殊的二叉树：

满二叉树：

如果一颗二叉树的每一层的节点的个数都达到了最大值，那么这棵树就是满二叉树。

 完全二叉树：

一颗二叉树中，只有最下面的两层节点的度可以小于2，并且最下一层的叶子节点几种在靠左的若干位置上。这样的二叉树称为完全二叉树。如下图：

特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一颗满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

 二叉搜索树：

二叉搜索树又叫二叉查找树，其中每个节点都有一个键标识该节点唯一，并且每个键大于左子树上任意节点的键，小于右子树上任意节点的键。

特点：

1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。

2.任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

3.任意节点的左、右子树也分别为二叉搜索树。

4.没有键值相等的节点 (no duplicate nodes)。

二叉搜索树的节点：

struct Node{int key;Node* left;Node* right;Node(int val):key(val),left(nullptr),right(nullptr){}
}；

二叉搜索树的定义：

class BiTree{
public:Node* root;//树根BiTree();BiTree(std::vector<int> vec);
};

创建二叉树的流程：

现在需要将数组{7 5 4 6 11 9 10}插入到一颗空树上（也就是以数组创建一颗树）

 

 

代码示例：

BiTree::BiTree(){root=nullptr;
}BiTree::BiTree(vector<int> vec){root=new Node(vec[0]);int n=vec.size();for(int i=1;i<n;i++){Node* node = new Node(vec[i]);//使用vi创建新节点Node* p =root;//p每次还原到根节点while(1){if(p->val < vec[i]){if(!p->right){p->right=node;break;}p=p->right;}if(p->val > vec[i]){if(!p->left){p->left=node;break;}p=p->left;}if(p->val == vec[i]) break;}}}

🎄二叉树的遍历

二叉树节点的声明定义：

template<typename T>
struct TreeNode {T val;TreeNode *lchild, *rchild;TreeNode():val(0),lchild(nullptr),rchild(nullptr){}TreeNode(const T& _val):val(_val),lchild(nullptr),rchild(nullptr){}	TreeNode(const TreeNode<T>& other) {val = other.val;lchild = nullptr;rchild = nullptr;		}
};
typedef int T;//下面就不定义模板的Tree类了，写起来怪麻烦的，把思路给大家，这块自行拓展就ok了
typedef TreeNode<T> Node;

层序遍历：

层序遍历的结果是，将第一层的根节点输出，然后依次输出树的下一层，从左往右依次输出。对于这种形式其实是广度优先搜索(BFS)的形式，这样的话，我们就可以使用队列这一数据结构来实现该算法了。

算法流程：

1. 创建一个队列记为que，将根节点放入队列。

2. 每次从队列中弹出一个节点，记为front。

3. 看这个front有没有左右孩子，有的话依次放入，没有的话就不放。

4. 重复步骤2和3，直到队列为空。

void Tree::levelTraverse() {res = {};//遍历前将数组清空queue<Node*> que;Node* cur = root;que.push(cur);while (!que.empty()) {Node* front = que.front();que.pop();res.push_back(front->val);if (front->lchild)que.push(front->lchild);if (front->rchild)que.push(front->rchild);}
}

代码分析：

第一步，将存储输出结果的数组res清空，创建一个存储节点指针的队列que，并将root根节点入队。

第二步，定义一个遍历的节点指针cur，首先指向根节点root。

第三步，循环，当队列不空，那么我就接着遍历，直到队列为空，说明我最后一层的所有元素都遍历过了，此时我再结束循环，退出程序。

第四步，循环体的内容：先将队头节点记录下来，避免弹出后找不到该节点，弹出队头并将存下来的队头节点的值输出到结果数组res中。如果弹出的这个队头节点有左孩子，就将左孩子节点入队，同理右孩子同样的方法。这样的话就准备开始下一层的循环了。

通过上面的演示过程，我们可以发现，每一次都将每一层的节点从左往右依次弹出，弹出时检测它是否还有孩子，有的话就依次入队尾，这样循环往复，直到节点没有孩子，那么就不入队，但每次都会弹出元素，所以循环会终止。

先序遍历：

非递归实现：

算法流程：

1.先申请一个栈，记为stk。

2.然后将根节点压入栈中。

3.每次从stk中弹出栈顶系欸但，记为top，然后输出top的值。如果top的右孩子不空，将右孩子压入栈中，如果左孩子不空，将左孩子压入栈中。

4.不断重复步骤3，直到stk为空，循环结束。

void Tree::prevOrder() {res = {};//遍历前将数组清空stack<Node*>stk;stk.push(root);while (!stk.empty()) {Node* top = stk.top();stk.pop();res.push_back(top->val);if (top->rchild)stk.push(top->rchild);if (top->lchild)stk.push(top->lchild);}
}

递归实现：

void toolTree::prevOrder(const Node* tree) {if (tree == nullptr)return;res.push_back(tree->val);prevOrder(tree->lchild);prevOrder(tree->rchild);
}

中序遍历：

非递归实现：

算法流程：

1.申请一个栈记为stk，申请一个变量cur初始化为root

2.先将cur节点压入栈中，对 以cur节点为根的整个子树，依次把整棵树的左边界压入栈中，不断执行：stk.push(cur),cur=cur->lchild；直到cur为空，左边界到头了停止循环

3.上面的循环停止后，弹出栈顶节点，记录为top，输出top的值，并且让cur=top->rchild；重复步骤2。

4.直到stk为空，并且cur也为空时（遍历到了右边界，遍历完了），停止整个循环

void Tree::inOrder() {res = {};//遍历前将数组清空stack<Node*> stk;Node* cur = root;while (!stk.empty() || cur) {while (cur) {stk.push(cur);cur = cur->lchild;}//一路向左，遇到的压入栈中，直到遇到结尾(nullptr)Node* top = stk.top();//将栈顶元素保存下来stk.pop();//弹出栈顶元素res.push_back(top->val);//将弹出的元素的值存入结果数组cur = top->rchild;//cur = 弹出的元素的右子树，因为左面已经一路向左走到底了，所以不会有左孩子}
}

递归实现：

void toolTree::inOrder(const Node* tree) {if (tree == nullptr)return;inOrder(tree->lchild);res.push_back(tree->val);inOrder(tree->rchild);
}

后序遍历：

非递归实现：

方法一：双栈法

算法流程：

1.申请两个栈，记为s1和s2，然后将头节点压入s1中

2.从s1中弹出的节点记为cur，然后先把cur的左子树压入s1，然后把cur的右子树压入s1中。

3.上一步的整个过程中，每一个s1弹出的节点都放入s2中。

4.不断重复步骤2、3，直到s1为空，整个过程结束。

void toolTree::postOrder(){stack<Node*> s1,s2;s1.push(root);while(s1.size()){Node* cur=s1.top();s1.pop();s2.push(cur);if(cur->lchild)s1.push(cur->lchild);if(cur->rchild)s2.push(cur->rchild);}while(!s2.empty()){res.push_back(s2.top()->val);s2.pop();}
}

这个方法有种先序遍历的倒着来的感觉🤔 。

方法二：标记法

void Tree::postOrder() {res = {};//遍历前将数组清空stack<Node*>stk;Node* cur = root;Node* pre = nullptr;while (!stk.empty() || cur) {while (cur) {stk.push(cur);cur = cur->lchild;}Node* top = stk.top();if (top->rchild == nullptr || top->rchild == pre) {//前者代表cur是叶子节点，后者代表cur->rchild右孩子已经遍历过了res.push_back(top->val);//cout << top->val;stk.pop();pre = top;//cur = nullptr;}else {cur = top->rchild;}}
}

方法三：

这个是我自己倒腾的，不知道对不对，也不晓得优劣什么的，试验了一下，一些基本的树的输出结果没什么问题。建议采用一、二。

void Tree::postOrder() {res = {};stack<Node*> stk;stk.push(root);Node* pre = nullptr;//用来标记访问过的节点while (stk.size()) {Node* top = stk.top();bool check1 = (!top->lchild && !top->rchild);//情况一：叶子节点，无左右子树了bool check2 = pre && (top->rchild == pre || top->lchild == pre);//情况二：左右子树有被标记过的情况，这就说明访问过了子树。前提是pre不能是初始空标记if (check1 || check2) {//有任何一种情况，都将输出节点，弹出节点，标记新节点res.push_back(top->val);stk.pop();pre = top;}else {if (top->rchild)stk.push(top->rchild);if (top->lchild)stk.push(top->lchild);}}
}

递归实现：

void toolTree::postOrder(const Node* tree) {if (tree == nullptr)return;postOrder(tree->lchild);postOrder(tree->rchild);res.push_back(tree->val);
}

通过以上的递归实现遍历，我们可以发现，代码形式上都差不多，无非是输出节点值的所在位置是在前中后哪个位置。但是虽然如此，我们还是不能硬记代码，要理解递归的整个过程。而且建议先学习非递归实现，然后再理解递归，应该会容易些。因为非递归的实现本质是利用栈结构来模拟递归过程的，我们需要搞清楚什么时候入栈，什么时候出栈，这样的话，对于我们理解递归的递进过程和回归过程有很大帮助。 

感谢大家


http://www.ppmy.cn/news/1545925.html

相关文章

openresty入门教程：init_by_lua_block

openresty入门教程：init_by_lua_block

init_by_lua_block 是 Nginx 配置中用于在 Nginx 启动时执行 Lua 脚本的一个指令。这个指令通常用于初始化全局变量、设置共享内存&#xff0c;或者执行一些需要在服务器启动时完成的准备工作。 以下是一个简单的 init_by_lua_block 使用示例&#xff1a; 1. 安装 Nginx 和 L…
阅读更多...
从0开始学习机器学习--Day20--优化算法的思路

从0开始学习机器学习--Day20--优化算法的思路

确定执行的优先级(Prioritizing what to work on : Spam classification example) 在建立学习系统前&#xff0c;我们不仅要梳理框架&#xff0c;更重要的是我们要弄清楚有哪些事情是要优先做的&#xff0c;这可以帮我们节约大量的时间。 以垃圾邮件为例&#xff0c;按照之前…
阅读更多...
实时计算 Flash – 兼容 Flink 的新一代向量化流计算引擎

实时计算 Flash – 兼容 Flink 的新一代向量化流计算引擎

摘要&#xff1a;本文整理自阿里云智能集团研究员、开源大数据平台负责人王峰&#xff08;莫问&#xff09;老师在云栖大会的开源大数据专场上的分享。主要有以下几个内容&#xff1a; 1. Apache Flink 已经成为业界流计算事实标准 2. Flash 向量化流计算引擎核心技术解读 3. F…
阅读更多...
24.11.6 PySimpleGUI库和pymsql 库以及人脸识别小项目

24.11.6 PySimpleGUI库和pymsql 库以及人脸识别小项目

PySimpleGUI 库 PySimpleGUI 是一个用于简化 GUI 编程的 Python 包&#xff0c;它封装了多种底层 GUI 框架&#xff08;如 tkinter、Qt、WxPython 等&#xff09;&#xff0c;提供了简单易用的 API。PySimpleGUI 包含了大量的控件&#xff08;也称为小部件或组件&#xff09;&…
阅读更多...
Kafka中如何做到数据唯一，即数据去重？

Kafka中如何做到数据唯一，即数据去重？

数据传递语义 至少一次&#xff08;At Least Once&#xff09; ACK级别设置为-1 分区副本大于等于2 ISR里应答的最小副本数量大于等于2 可以保障数据可靠 • 最多一次&#xff08;At Most Once&#xff09; ACK级别设置为0 • 总结&#xff1a; At Least Once可以保证数据不…
阅读更多...
Linux---进程间通信之共享内存

Linux---进程间通信之共享内存

前言 我们前面学习了管道&#xff0c;今天我们学习另一种进程间通信方式--->共享内存。管道通信本质是基于文件系统的&#xff0c;并不关操作系统什么事&#xff0c;而system V IPC是操作系统特地设计的一种通信方式。但他们的目的都是一样的&#xff0c;就是让不同的进程看…
阅读更多...
分布式数据库技术深度解析与代码实践

分布式数据库技术深度解析与代码实践

分布式数据库技术深度解析与代码实践 随着大数据和云计算的快速发展，分布式数据库作为一种高性能、高可用性和可扩展性的数据存储解决方案，被广泛应用于各种业务场景中。本文将深入探讨分布式数据库的核心技术、架构设计及其实践应用，并通过具体代码示例展示如何在实际项目…
阅读更多...
jmeter 性能测试步骤是什么？

jmeter 性能测试步骤是什么？

JMeter是一款流行的开源性能测试工具&#xff0c;用于测试各种服务器和网络应用的性能。在进行JMeter性能测试时&#xff0c;通常需要遵循以下步骤&#xff1a; 确定测试目标&#xff1a;首先&#xff0c;明确性能测试的目标。这可以是测试一个网站的负载能力、测试一个API的响…
阅读更多...
最新文章

Copyright @ 2022~2023