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

C++关于二叉树的具体实现

article 2024/12/3 0:19:21

目录

1.二叉树的结构

2.创建一棵二叉树

3.二叉树的先序遍历

1.借助栈的先序遍历

2.利用递归的先序遍历

4.二叉树的中序遍历

5.二叉树的后序遍历

1.借助栈的后序遍历

2.利用递归的后序遍历

6.二叉树的层序遍历

7.tree.h

8.tree.cpp

9.main.cpp

1.二叉树的结构

对于二叉树来说，它是由无数个结点形成的一棵树，结点的表示如下图：包含两个指针分别指向左右孩子节点，和一个表示本身的值的数。

所以我们可以给出结点的代码为：

struct Node {
	int val;
	Node* left;//指向左孩子节点的指针
	Node* right;//指向右孩子节点的指针
	Node(int val) {
		this->val = val;
		left = nullptr;
		right = nullptr;
	}
};

2.创建一棵二叉树

思路：把数组中的第一个元素作为根节点，比它小的放在它的左子树上，比它大的放在右子树上面

tree::tree(vector<int>& vec) {
	if (vec.size() == 0) {
		root = nullptr;
		return;
	}
	root = new Node(vec[0]);
	for (int i = 1; i < vec.size(); i++) {
		//先创建结点
		Node* node = new Node(vec[i]);
		Node* p = root;
		while (1) {
			if (node->val > p->val)
			{
				if (p->right == nullptr) {
					p->right = node;
					break;
				}
				p = p->right;
			}
			if (node->val < p->val) {
				if (p->left == nullptr) {
					p->left = node;
					break;
				}
				p = p->left;
			}
			if (p->val == node->val)break;
		}
	}
}

        首先把v[0]这个元素作为根节点，然后遍历后面的元素，先创建值为v[i]的节点，然后找它应该放的位置。如果这个节点 的值大于当前比较的那个节点，就往它的右子树找，如果它的右子树为空，直接放到这个位置上即可。如果它的右子树不为空，那么就将右子树上那个节点作为比较节点，然后又进行比较，重复此过程，直至找到这个节点的位置。

例如给定数组v[]={7,5,4,6,11,9,10}

它的构建过程如下：

1.先创建根节点

2.找5的位置，因为5与7进行比较，比它小，而且7的左孩子为空，直接将5放在7的左孩子上。

3.找4的位置，4比7小，而7的左孩子已经有了，所以往下找，4比5小，而且5的左孩子为空，所以4放到5的左孩子节点上。

4.找6的位置，6比7小，并且7的左孩子节点存在，所以往下找，6比5大，且5的右孩子节点不存在，所以6放到5的右孩子节点上。

5.找11的位置，11比7大，而且7的右孩子节点为空，所以直接放到7的右孩子节点上。

6.找9的位置，9比7大，往右找，比11小，而且11的左孩子节点为空，所以9放到11的左孩子节点上。

7.找10的位置，10比7大，往后找，比11小，往左找，比9大，而且9的右孩子节点为空，所以10放到9的右孩子节点上。

所以最终的二叉树如上图。

3.二叉树的先序遍历

1.借助栈的先序遍历

先序遍历是“根左右”，这里要借助栈来实现它的遍历操作，先将根节点压入到栈中，然后while循环，循环的条件是栈不为空，先弹出栈顶的元素，然后再将右孩子节点压入到栈中，再压左孩子节点。重复此操作。

//先序遍历
void tree::PreOrder(Node* root)
{
	if (!root)return;
	stack<Node*> stk;
	stk.push(root);
	while (!stk.empty()) {
		Node* top = stk.top();
		stk.pop();
		cout << top->val << " ";
		if (top->right)stk.push(top->right);
		if (top->left)stk.push(top->left);
	}
}

2.利用递归的先序遍历

//先序遍历（递归）
void tree::_PreOrder(Node* root) {
	if (!root) return;
	cout << root->val<<" ";
	_PreOrder(root->left);
	_PreOrder(root->right);

}

4.二叉树的中序遍历

1.借助栈的中序遍历

中序遍历是“左根右”，同样需要借助栈，先从根节点出发，把所有的左孩子节点全部压入到栈中，然后打印栈顶元素的值，同时cur要指向这个元素的右子树，因为下一次要压入这个右子树，然后移除栈顶元素。

//中序遍历
void tree::InOrder(Node* root) {
	if (!root)return;
	stack<Node*> stk;
	Node* cur = root;
	while (cur || !stk.empty()) {
		while (cur) {
			stk.push(cur);
			cur = cur->left;
		}
		Node* top = stk.top();
		stk.pop();
		cout << top->val<<" ";
		cur = top->right;

	}

}

2.利用递归的中序遍历

//中序遍历（递归）
void tree::_InOrder(Node* root) {
	if (!root) return;
	_InOrder(root->left);
	cout << root->val << " ";
	_InOrder(root->right);
}

5.二叉树的后序遍历

1.借助栈的后序遍历

后序遍历是“左右根”，这里需要用到两个栈，一个栈用作辅助，在栈s1中对遍历的节点的顺序进行调整，然后压入到栈s2中，遍历s2的顺序就是后序遍历的顺序。

//后序遍历
void tree::PostOrder(Node* root) {
	if (!root)return;
	stack<Node*> s1,s2;
	s1.push(root);
	while (!s1.empty()) {
		Node* top = s1.top();
		s1.pop();
		s2.push(top);
		if (top->left)s1.push(top->left);
		if (top->right)s1.push(top->right);
	}
	while (!s2.empty()) {
		cout << s2.top()->val << " ";
		s2.pop();
	}
}

2.利用递归的后序遍历

//后序遍历（递归）
void tree::_PostOrder(Node * root) {
	if (!root) return;
	_PostOrder(root->left);
	_PostOrder(root->right);
	cout << root->val << " ";
}

6.二叉树的层序遍历

利用队列先进先出的特点，先将根节点加入到队列中，然后循环，循环的条件是队列不为空，每次取出队首的元素，同时判断是否有左右孩子，有的话就将其加入到队列尾部。

//层序遍历
void tree::levelOrder(Node* root) {
	if (root == nullptr)
		return ;
	queue<Node*> q;
	q.push(root);
	Node* node;	
	while (!q.empty()) {				
			node = q.front();
			q.pop();
			cout << node->val<<" ";
			if (node->left)
				q.push(node->left);
			if (node->right)
				q.push(node->right);		
	}	
}

我们可以将二叉树形成一个类，在tree.h中对其结构进行声明以及函数的声明，在tree.cpp中对它的函数进行实现，在主函数中对其进行测试，以实现“低耦合高类聚”的特点。下面给出这几个文件的代码。

7.tree.h

#pragma once
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
struct Node {
	int val;
	Node* left;
	Node* right;
	Node(int val) {
		this->val = val;
		left = nullptr;
		right = nullptr;
	}
}; 
class tree
{
	Node* root;
public:
	tree():root(nullptr){}//无参构造函数
	tree(vector<int>& vec); //有参构造函数
	Node* getroot()const {
		return root;
	}
	void PreOrder(Node* root); //先序遍历
	void PostOrder(Node* root);//后序遍历
	void InOrder(Node* root);//中序遍历
	void _PreOrder(Node* root);//先序遍历（递归）
	void _PostOrder(Node* root);//后序遍历（递归）
	void _InOrder(Node* root);//中序遍历（递归）
	void levelOrder(Node* root);//层序遍历

};

8.tree.cpp

#include "tree.h"
tree::tree(vector<int>& vec) {
	if (vec.size() == 0) {
		root = nullptr;
		return;
	}
	root = new Node(vec[0]);
	for (int i = 1; i < vec.size(); i++) {
		//先创建结点
		Node* node = new Node(vec[i]);
		Node* p = root;
		while (1) {
			if (node->val > p->val)
			{
				if (p->right == nullptr) {
					p->right = node;
					break;
				}
				p = p->right;
			}
			if (node->val < p->val) {
				if (p->left == nullptr) {
					p->left = node;
					break;
				}
				p = p->left;
			}
			if (p->val == node->val)break;
		}
	}
}

//先序遍历
void tree::PreOrder(Node* root)
{
	if (!root)return;
	stack<Node*> stk;
	stk.push(root);
	while (!stk.empty()) {
		Node* top = stk.top();
		stk.pop();
		cout << top->val << " ";
		if (top->right)stk.push(top->right);
		if (top->left)stk.push(top->left);
	}
}
//后序遍历
void tree::PostOrder(Node* root) {
	if (!root)return;
	stack<Node*> s1,s2;
	s1.push(root);
	while (!s1.empty()) {
		Node* top = s1.top();
		s1.pop();
		s2.push(top);
		if (top->left)s1.push(top->left);
		if (top->right)s1.push(top->right);
	}
	while (!s2.empty()) {
		cout << s2.top()->val << " ";
		s2.pop();
	}
}
//中序遍历
void tree::InOrder(Node* root) {
	if (!root)return;
	stack<Node*> stk;
	Node* cur = root;
	while (cur || !stk.empty()) {
		while (cur) {
			stk.push(cur);
			cur = cur->left;
		}

		Node* top = stk.top();
		stk.pop();
		cout << top->val<<" ";
		cur = top->right;

	}

}
//先序遍历（递归）
void tree::_PreOrder(Node* root) {
	if (!root) return;
	cout << root->val<<" ";
	_PreOrder(root->left);
	_PreOrder(root->right);


}
//后序遍历（递归）
void tree::_PostOrder(Node * root) {
	if (!root) return;
	_PostOrder(root->left);
	_PostOrder(root->right);
	cout << root->val << " ";
}
//中序遍历（递归）
void tree::_InOrder(Node* root) {
	if (!root) return;
	_InOrder(root->left);
	cout << root->val << " ";
	_InOrder(root->right);
}
//层序遍历
void tree::levelOrder(Node* root) {
	if (root == nullptr)
		return ;
	queue<Node*> q;
	q.push(root);
	Node* node;	
	while (!q.empty()) {				
			node = q.front();
			q.pop();
			cout << node->val<<" ";
			if (node->left)
				q.push(node->left);
			if (node->right)
				q.push(node->right);		
	}	
}

9.main.cpp

#include"tree.h"
int main() { 
	vector<int> vec = { 7,5,4,6,11,9,10 };
	tree t(vec);
	cout << "先序遍历的结果：" << endl;
	t.PreOrder(t.getroot());
	cout << endl;
	cout << "先序遍历的结果：（递归）" << endl;
	t._PreOrder(t.getroot());
	cout << endl;
	cout << "中序遍历的结果：" << endl;
	t.InOrder(t.getroot());
	cout << endl;
	cout << "中序遍历的结果：（递归）" << endl;
	t._InOrder(t.getroot());
	cout << endl;
	cout << "后序遍历的结果：" << endl;
	t.PostOrder(t.getroot());
	cout << endl;
	cout << "后序遍历的结果：（递归）" << endl;
	t._PostOrder(t.getroot());
	cout << endl;
	cout << "层序遍历的结果：" << endl;
	t.levelOrder(t.getroot());	
	return 0;
}


http://www.kler.cn/a/419146.html

相关文章：

  • MOH: MULTI-HEAD ATTENTION AS MIXTURE-OFHEAD ATTENTION
  • docker安装hadoop环境
  • TiDB 无统计信息时执行计划如何生成
  • Shebang（Hashbang）是什么
  • Transformers在计算机视觉领域中的应用【第1篇：ViT——Transformer杀入CV界之开山之作】
  • 【工具推荐】dnsx——一个快速、多用途的 DNS 查询工具
  • （4）CHATGPT-3和GPT-4是生成式AI的一部分吗？
  • 【二分查找】力扣 2529. 正整数和负整数的最大计数
  • HTML CSS JS基础考试题与答案
  • springboot kafka在kafka server AUTH变动后consumer自动销毁
  • linux系统信号简介
  • Scala—列表（可变ListBuffer、不可变List）用法详解
  • FAT文件系统
  • 【ETCD】etcd简单入门之基础操作基于etcdctl进行操作
  • arkTS：持久化储存UI状态的基本用法（PersistentStorage）
  • 基于Java Springboot宠物医院微信小程序
  • UI设计-色彩、层级、字体、边距（二）
  • 民锋视角：数据分析如何助力金融决策
  • 【docker集群应用】Docker--harbor私有仓库部署与管理
  • C语言——管理系统
  • glog在vs2022 hello world中使用
  • MySQL Inception工具
  • 泷羽sec-shell（5）字符串运算符和逻辑运算符 学习笔记
  • 编程基础篇
  • 英语写作中以rationale 替代reason（理由）
  • node.js基础学习-querystring模块-查询字符串处理（三）