当前位置： 首页 > article >正文

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

article 2024/11/14 16:21:51

🌳树的基础内容

树的定义：

树是一种数据结构，它是由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.kler.cn/a/388599.html

相关文章：

  • 类别变量分析——卡方独立性检验卡方拟合优度检验
  • 并发基础：（淘宝笔试题）三个线程分别打印 A，B，C，要求这三个线程一起运行，打印 n 次，输出形如“ABCABCABC....”的字符串【举一反三】
  • 24/11/12 算法笔记＜强化学习＞ Policy Gradient策略梯度
  • Rust 建造者模式
  • 探索 HTTP 请求方法：GET、POST、PUT、DELETE 等的用法详解
  • LLM - 使用 LLaMA-Factory 微调大模型 Qwen2-VL SFT(LoRA) 图像数据集 教程 (2)
  • ubuntu下安装 git 及部署cosyvoice(2)
  • 【开源社区】ELK 磁盘异常占用解决及优化实践
  • 如何平滑切换Containerd数据目录
  • android 适应CA证书
  • spring-security(两种权限控制方式)
  • Qt 界面无边框 拖拽移动 问题处理：setMouseTracking(true)无法跟踪鼠标事件
  • ＜项目代码＞YOLOv8 玉米地杂草识别＜目标检测＞
  • unity3d————四元数，欧拉角的互相转换的初步了解
  • 【bayes-Transformer-GRU多维时序预测】多变量输入模型。matlab代码，2023b及其以上
  • Bert框架详解（上）
  • EM是什么？如何修复EM violation?
  • arm中内存读取延迟性能测试
  • goframe开发一个企业网站 rabbitmq队例15
  • 【网络面试篇】TCP 相关——重传机制、滑动窗口、流量控制、拥塞控制、Keep-Alive、KeepAlive
  • 优选算法 - 1 （ 双指针 移动窗口 8000 字详解 ）
  • SpringFramework
  • VMware调整窗口为可以缩小但不改变显示内容的大小
  • 如何基于redis记录调用大模型问答的统一注册服务
  • Vue3 实现拖拽小图片覆盖大图片并下载合并后的图片
  • Flutter运行App时出现“Running Gradle task ‘assembleDebug“问题解决