C++ 二叉树(建立、销毁、前中后序遍历和层次遍历,寻找双亲结点等)

这篇具有很好参考价值的文章主要介绍了C++ 二叉树(建立、销毁、前中后序遍历和层次遍历,寻找双亲结点等)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C++ 二叉树(建立、销毁、前中后序遍历和层次遍历,寻找双亲结点等),c++,数据结构,开发语言文章来源地址https://www.toymoban.com/news/detail-649460.html

(1)结构体和类定义

struct BTreeNode {
	T data;
	BTreeNode* left, * right;
	BTreeNode() :data(0), left(nullptr), right(nullptr) {}
	BTreeNode(T val, BTreeNode<T>* leftChild = nullptr, BTreeNode<T>* rightChild = nullptr)
		:data(val), left(leftChild), right(rightChild) {}

};

template<class T>
class BTree {
public:
	BTree() :root(nullptr) {}										      // 构造函数
	BTree(string str);                                                    // 重载

	void createTree(BTreeNode<T>*& bt, string str);                       // 创建二次树
	~BTree();														      // 析构函数
	bool IsEmpty();													      // 判二叉树空否?
	int Size(BTreeNode<T>* cur);                                          // 计算结点个数
	int getSize();                                                        // 获取结点个数
	BTreeNode<T>* getData(T& item, BTreeNode<T>* cur);	                  // 取得结点数据
	bool Find(T& item);		                                              // 判断item是否在树中
	int Height(BTreeNode<T>* bt);                                         // 求树高度
	int getHeight();                                                      // 获取树高度
	BTreeNode<T>* getRoot();	                                          // 取根

	void preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);          // 前序遍历
	void inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);		      // 中序遍历
	void postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);         // 后序遍历
	void levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);        // 层序遍历

	vector<T> preOrder();						                          // 调用前序遍历,返回vector
	vector<T> inOrder();											      // 调用中序遍历,返回vector
	vector<T> postOrder();											      // 调用后序遍历,返回vector
	vector<T> levelOrder();                                               // 调用层序遍历,返回vector

	void CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot);           // 二叉树复制
	void Copy(BTreeNode<T>*& copyRoot);                                   // 调用二叉树复制
	void destroyCopyTree(BTreeNode<T>*& copyRoot);                        // 销毁复制二叉树


	BTreeNode<T>* FindParent(BTreeNode<T>* root, BTreeNode<T>* node);     // 寻找双亲
	BTreeNode<T>* LeftChild(BTreeNode<T>* node) {                         //求结点 node 的左孩子
		return (node != nullptr) ? node->left : nullptr;
	}
	BTreeNode<T>* RightChild(BTreeNode<T>* node) {                        //求结点 node 的右孩子
		return (node != nullptr) ? node->right : nullptr;
	}

protected:
	BTreeNode<T>* root;
	void destroyTree(BTreeNode<T>* node);                                // 销毁二叉树
};

(2)创建二叉树

template<class T>
BTree<T>::BTree(string str) {
	createTree(root, str);
	cout << "报告:创建一颗二叉树,完成!!!" << endl;
}

template<class T>
void BTree<T>::createTree(BTreeNode<T>*& bt, string str) {
	static int i = 0;
	char ch = ' ';
	ch = str[i++];

	if (ch == '#') bt = nullptr;
	else {
		bt = new BTreeNode<T>(ch);
		createTree(bt->left, str);
		createTree(bt->right, str);
	}
};

(3)前中后序遍历和层序遍历

// 前序遍历
template<class T>
void BTree<T>::preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr)
		return;
	vec.push_back(cur->data);           // 中
	preOrderTraversal(cur->left, vec);  // 左
	preOrderTraversal(cur->right, vec); // 右
}

// 调用前序遍历,返回vector
template<class T>
vector<T> BTree<T>::preOrder() {
	cout << "获取前序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	preOrderTraversal(root, resVec);
	return resVec;
}

// 中序遍历
template<class T>
void BTree<T>::inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr)
		return;
	inOrderTraversal(cur->left, vec);  // 左
	vec.push_back(cur->data);          // 中
	inOrderTraversal(cur->right, vec); // 右
}

// 调用中序遍历,返回vector
template<class T>
vector<T> BTree<T>::inOrder() {
	cout << "获取中序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	inOrderTraversal(root, resVec);
	return resVec;
}

// 后序遍历
template<class T>
void BTree<T>::postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr)
		return;
	postOrderTraversal(cur->left, vec);  // 左
	postOrderTraversal(cur->right, vec); // 右
	vec.push_back(cur->data);            // 中
}

// 调用后序遍历,返回vector
template<class T>
vector<T> BTree<T>::postOrder() {
	cout << "获取后序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	postOrderTraversal(root, resVec);
	return resVec;
}

// 层序遍历
template<class T>
void BTree<T>::levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr) return;
	queue<BTreeNode<T>*> Queue;
	BTreeNode<T>* p;
	Queue.push(cur); // 根结点入队列
	while (!Queue.empty()) {
		p = Queue.front();
		//cout << p->data << " ";//输出出队结点的数据
		vec.push_back(p->data);
		Queue.pop();
		if (p->left != nullptr) {
			Queue.push(p->left);
		}
		if (p->right != nullptr) {
			Queue.push(p->right);
		}
	}
}

// 调用层序遍历,返回vector
template<class T>
vector<T> BTree<T>::levelOrder() {
	cout << "获取层序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	levelOrderTraversal(root, resVec);
	return resVec;
}

(4)复制二叉树

template<class T>
void BTree<T>::CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot) {
	if (!root) {
		copyRoot = nullptr;
	}
	else {
		copyRoot = new BTreeNode<T>;
		copyRoot->data = root->data;           //复制根节点
		CopyTree(root->left, copyRoot->left);  //递归复制左子树
		CopyTree(root->right, copyRoot->right);//递归复制左子树
	}
}

template<class T>
void BTree<T>::Copy(BTreeNode<T>*& copyRoot) {
	CopyTree(root, copyRoot);
}

(5)销毁二叉树

template<class T>
void BTree<T>::destroyCopyTree(BTreeNode<T>*& copyRoot) {
	destroyTree(copyRoot);
	cout << "报告,复制二叉树已销毁完毕!!!" << endl;
}

// 销毁二叉树 
template<class T>
void BTree<T>::destroyTree(BTreeNode<T>* bt) {
	// 后序遍历删除根为subTree的子树;
	if (bt != nullptr) {
		destroyTree(bt->left);    //删除左子树
		destroyTree(bt->right);   //删除右子树
		delete bt; 			      //删除根结点
	}
}

(6)析构函数

// 析构函数
template<class T>
BTree<T>::~BTree<T>() {
	//cout << "调用析构函数" << endl;
	destroyTree(root);
	cout << "报告,这棵树已经销毁完毕!!!" << endl;
}

(7)求树的高度

// 求树高度
template<class T>
int BTree<T>::Height(BTreeNode<T>* bt) {
	if (bt == nullptr) return 0;
	else {
		int leftH = Height(bt->left);
		int rightH = Height(bt->right);
		return (leftH > rightH) ? leftH + 1 : rightH + 1;
	}
}

// 获取树高度
template<class T>
int BTree<T>::getHeight() {
	return Height(root);
}

(8)获取结点,判断其是否在二叉树中

// 取得结点数据
template<class T>
BTreeNode<T>* BTree<T>::getData(T& item, BTreeNode<T>* cur) {
	if (cur == nullptr) return nullptr;
	if (cur->data == item) return cur;
	return getData(item, cur->left) != nullptr ? getData(item, cur->left) : getData(item, cur->right);
}

// 判断item是否在树中
template<class T>
bool BTree<T>::Find(T& item) {
	if (this->getData(item, root) == nullptr) return false;
	else return true;

(9)计算结点个数和获取结点个数

// 计算结点个数
template<class T>
int BTree<T>::Size(BTreeNode<T>* cur) {
	if (cur == nullptr)
		return 0;
	else
		return 1 + Size(cur->left) + Size(cur->right);
}

// 获取结点个数
template<class T>
int BTree<T>::getSize() {
	return Size(root);
}

(10)二叉树判空

// 判二叉树空否?
template<class T>
bool BTree<T>::IsEmpty() {
	return (root == nullptr) ? true : false;
}

(11)获取根结点

// 获取根 
template<class T>
BTreeNode<T>* BTree<T>::getRoot() {
	if (!root) return nullptr;
	else {
		return this->root;
	}
}

源代码:

btree.h
#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

template<class T>
struct BTreeNode {
	T data;
	BTreeNode* left, * right;
	BTreeNode() :data(0), left(nullptr), right(nullptr) {}
	BTreeNode(T val, BTreeNode<T>* leftChild = nullptr, BTreeNode<T>* rightChild = nullptr)
		:data(val), left(leftChild), right(rightChild) {}

};

template<class T>
class BTree {
public:
	BTree() :root(nullptr) {}										      // 构造函数
	BTree(string str);                                                    // 重载

	void createTree(BTreeNode<T>*& bt, string str);                       // 创建二次树
	~BTree();														      // 析构函数
	bool IsEmpty();													      // 判二叉树空否?
	int Size(BTreeNode<T>* cur);                                          // 计算结点个数
	int getSize();                                                        // 获取结点个数
	BTreeNode<T>* getData(T& item, BTreeNode<T>* cur);	                  // 取得结点数据
	bool Find(T& item);		                                              // 判断item是否在树中
	int Height(BTreeNode<T>* bt);                                         // 求树高度
	int getHeight();                                                      // 获取树高度
	BTreeNode<T>* getRoot();	                                          // 取根

	void preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);          // 前序遍历
	void inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);		      // 中序遍历
	void postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);         // 后序遍历
	void levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);        // 层序遍历

	vector<T> preOrder();						                          // 调用前序遍历,返回vector
	vector<T> inOrder();											      // 调用中序遍历,返回vector
	vector<T> postOrder();											      // 调用后序遍历,返回vector
	vector<T> levelOrder();                                               // 调用层序遍历,返回vector

	void CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot);           // 二叉树复制
	void Copy(BTreeNode<T>*& copyRoot);                                   // 调用二叉树复制
	void destroyCopyTree(BTreeNode<T>*& copyRoot);                        // 销毁复制二叉树


	BTreeNode<T>* FindParent(BTreeNode<T>* root, BTreeNode<T>* node);     // 寻找双亲
	BTreeNode<T>* LeftChild(BTreeNode<T>* node) {                         //求结点 node 的左孩子
		return (node != nullptr) ? node->left : nullptr;
	}
	BTreeNode<T>* RightChild(BTreeNode<T>* node) {                        //求结点 node 的右孩子
		return (node != nullptr) ? node->right : nullptr;
	}

protected:
	BTreeNode<T>* root;
	void destroyTree(BTreeNode<T>* node);                                // 销毁二叉树
};
btree.cpp
// 每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!
// 1.确定递归函数的参数的返回值
// 2.确定终止条件
// 3.确定单层递归的逻辑

#include "btree.h"

template<class T>
BTree<T>::BTree(string str) {
	createTree(root, str);
	cout << "报告:创建一颗二叉树,完成!!!" << endl;
}

template<class T>
void BTree<T>::createTree(BTreeNode<T>*& bt, string str) {
	static int i = 0;
	char ch = ' ';
	ch = str[i++];

	if (ch == '#') bt = nullptr;
	else {
		bt = new BTreeNode<T>(ch);
		createTree(bt->left, str);
		createTree(bt->right, str);
	}
};

// 判二叉树空否?
template<class T>
bool BTree<T>::IsEmpty() {
	return (root == nullptr) ? true : false;
}

// 计算结点个数
template<class T>
int BTree<T>::Size(BTreeNode<T>* cur) {
	if (cur == nullptr)
		return 0;
	else
		return 1 + Size(cur->left) + Size(cur->right);
}

// 获取结点个数
template<class T>
int BTree<T>::getSize() {
	return Size(root);
}

// 取得结点数据
template<class T>
BTreeNode<T>* BTree<T>::getData(T& item, BTreeNode<T>* cur) {
	if (cur == nullptr) return nullptr;
	if (cur->data == item) return cur;
	return getData(item, cur->left) != nullptr ? getData(item, cur->left) : getData(item, cur->right);
}

// 判断item是否在树中
template<class T>
bool BTree<T>::Find(T& item) {
	if (this->getData(item, root) == nullptr) return false;
	else return true;
}

// 求树高度
template<class T>
int BTree<T>::Height(BTreeNode<T>* bt) {
	if (bt == nullptr) return 0;
	else {
		int leftH = Height(bt->left);
		int rightH = Height(bt->right);
		return (leftH > rightH) ? leftH + 1 : rightH + 1;
	}
}

// 获取树高度
template<class T>
int BTree<T>::getHeight() {
	return Height(root);
}

// 获取根 
template<class T>
BTreeNode<T>* BTree<T>::getRoot() {
	if (!root) return nullptr;
	else {
		return this->root;
	}
}

// 析构函数
template<class T>
BTree<T>::~BTree<T>() {
	//cout << "调用析构函数" << endl;
	destroyTree(root);
	cout << "报告,这棵树已经销毁完毕!!!" << endl;
}

// 销毁二叉树 
template<class T>
void BTree<T>::destroyTree(BTreeNode<T>* bt) {
	// 后序遍历删除根为subTree的子树;
	if (bt != nullptr) {
		destroyTree(bt->left);    //删除左子树
		destroyTree(bt->right);   //删除右子树
		delete bt; 			      //删除根结点
	}
}

// 前序遍历
template<class T>
void BTree<T>::preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr)
		return;
	vec.push_back(cur->data);           // 中
	preOrderTraversal(cur->left, vec);  // 左
	preOrderTraversal(cur->right, vec); // 右
}

// 调用前序遍历,返回vector
template<class T>
vector<T> BTree<T>::preOrder() {
	cout << "获取前序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	preOrderTraversal(root, resVec);
	return resVec;
}

// 中序遍历
template<class T>
void BTree<T>::inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr)
		return;
	inOrderTraversal(cur->left, vec);  // 左
	vec.push_back(cur->data);          // 中
	inOrderTraversal(cur->right, vec); // 右
}

// 调用中序遍历,返回vector
template<class T>
vector<T> BTree<T>::inOrder() {
	cout << "获取中序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	inOrderTraversal(root, resVec);
	return resVec;
}

// 后序遍历
template<class T>
void BTree<T>::postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr)
		return;
	postOrderTraversal(cur->left, vec);  // 左
	postOrderTraversal(cur->right, vec); // 右
	vec.push_back(cur->data);            // 中
}

// 调用后序遍历,返回vector
template<class T>
vector<T> BTree<T>::postOrder() {
	cout << "获取后序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	postOrderTraversal(root, resVec);
	return resVec;
}

// 层序遍历
template<class T>
void BTree<T>::levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
	if (cur == nullptr) return;
	queue<BTreeNode<T>*> Queue;
	BTreeNode<T>* p;
	Queue.push(cur); // 根结点入队列
	while (!Queue.empty()) {
		p = Queue.front();
		//cout << p->data << " ";//输出出队结点的数据
		vec.push_back(p->data);
		Queue.pop();
		if (p->left != nullptr) {
			Queue.push(p->left);
		}
		if (p->right != nullptr) {
			Queue.push(p->right);
		}
	}
}

// 调用层序遍历,返回vector
template<class T>
vector<T> BTree<T>::levelOrder() {
	cout << "获取层序遍历数组...." << endl;
	cout << ">>>>";
	vector<T> resVec;
	levelOrderTraversal(root, resVec);
	return resVec;
}

template<class T>
void BTree<T>::CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot) {
	if (!root) {
		copyRoot = nullptr;
	}
	else {
		copyRoot = new BTreeNode<T>;
		copyRoot->data = root->data;           //复制根节点
		CopyTree(root->left, copyRoot->left);  //递归复制左子树
		CopyTree(root->right, copyRoot->right);//递归复制左子树
	}
}

template<class T>
void BTree<T>::Copy(BTreeNode<T>*& copyRoot) {
	CopyTree(root, copyRoot);
}

template<class T>
void BTree<T>::destroyCopyTree(BTreeNode<T>*& copyRoot) {
	destroyTree(copyRoot);
	cout << "报告,复制二叉树已销毁完毕!!!" << endl;
}

template<class T>
BTreeNode<T>* BTree<T>::FindParent(BTreeNode<T>* root, BTreeNode<T>* node) {

	if (root == nullptr) return nullptr;
	if (root->left == node || root->right == node)
		return root;	     //找到, 返回父结点地址
	BTreeNode <T>* p;
	if ((p = FindParent(root->left, node)) != nullptr)
		return p;	         //递归在左子树中搜索
	else return FindParent(root->right, node);
}
test.cpp
#include "btree.h"
#include "btree.cpp"
//#include <iostream>
//using namespace std;
int main() {
	cout << "-------------------------Start--------------------------" << endl;
	cout << "---------------------创建原始二叉树---------------------" << endl;
	string str = "ABD#G##E##CF###";
	BTree<int>* T = new BTree<int>(str);
	BTreeNode<int>* root = T->getRoot();
	cout << "这棵树有 " << T->getSize() << " 个结点" << endl;

	int zifu = 'G';
	if (T->Find(zifu)) {
		cout << "这棵树有 " << (char)zifu << " 结点" << endl;
	}
	else {
		cout << "这棵树无 " << (char)zifu << " 结点" << endl;
	}
	BTreeNode<int>* node = T->getData(zifu, root);
	if (node) {
		cout << (char)node->data << endl;
		BTreeNode<int>* nodeParent = T->FindParent(root, node);
		if (!nodeParent) {
			cout << "找不到父亲结点" << endl;
		}
		else {
			cout << "结点 " << (char)zifu << " 的父亲结点是: " << (char)nodeParent->data << " 结点" << endl;
			if (nodeParent->left) cout << "我的左孩子是: " << (char)nodeParent->left->data << endl;
			else cout << "我没有左孩子..." << endl;
			if (nodeParent->right) cout << "我的右孩子是: " << (char)nodeParent->right->data << endl;
			else cout << "我没有右孩子..." << endl;
		}
	}
	cout << "这棵树的高度为: " << T->getHeight() << endl;

	vector<int> vec = T->preOrder();
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;

	vec.clear();
	vec = T->inOrder();
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;

	vec.clear();
	vec = T->postOrder();
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;

	vec.clear();
	vec = T->levelOrder();
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;


	cout << "-----------------------复制二叉树-----------------------" << endl;
	// 复制二叉树
	//vector<int> vec;
	//BTreeNode<int>* root = T->getRoot();
	BTreeNode<int>* copyRoot = new BTreeNode<int>;
	//T->Copy(copyRoot);          // 方法一
	T->CopyTree(root, copyRoot);  // 方法二

	vec.clear();
	cout << "获取前序遍历数组...." << endl;
	cout << ">>>>";
	T->preOrderTraversal(copyRoot, vec);
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;

	vec.clear();
	cout << "获取中序遍历数组...." << endl;
	cout << ">>>>";
	T->inOrderTraversal(copyRoot, vec);
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;

	vec.clear();
	cout << "获取后序遍历数组...." << endl;
	cout << ">>>>";
	T->postOrderTraversal(copyRoot, vec);
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;

	vec.clear();
	cout << "获取层序遍历数组...." << endl;
	cout << ">>>>";
	T->levelOrderTraversal(copyRoot, vec);
	for (auto i : vec) {
		cout << (char)i;
	}
	cout << endl;
	cout << "---------------------销毁复制二叉树---------------------" << endl;
	T->destroyCopyTree(copyRoot);
	cout << "---------------------销毁原始二叉树---------------------" << endl;
	T->~BTree();
	cout << "--------------------------End---------------------------" << endl;
	return 0;
}
>>测试结果 
-------------------------Start--------------------------
---------------------创建原始二叉树---------------------
报告:创建一颗二叉树,完成!!!
这棵树有 7 个结点
这棵树有 G 结点
G
结点 G 的父亲结点是: D 结点
我没有左孩子...
我的右孩子是: G
这棵树的高度为: 4
获取前序遍历数组....
>>>>ABDGECF
获取中序遍历数组....
>>>>DGBEAFC
获取后序遍历数组....
>>>>GDEBFCA
获取层序遍历数组....
>>>>ABCDEFG
-----------------------复制二叉树-----------------------
获取前序遍历数组....
>>>>ABDGECF
获取中序遍历数组....
>>>>DGBEAFC
获取后序遍历数组....
>>>>GDEBFCA
获取层序遍历数组....
>>>>ABCDEFG
---------------------销毁复制二叉树---------------------
报告,复制二叉树已销毁完毕!!!
---------------------销毁原始二叉树---------------------
报告,这棵树已经销毁完毕!!!
--------------------------End---------------------------

到了这里,关于C++ 二叉树(建立、销毁、前中后序遍历和层次遍历,寻找双亲结点等)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树的前中后序遍历(C语言)

    [二叉树] 顾名思义就是有 两个分支节点的树,不仅如此,除了叶子外的所有节点都具有两个分支节点; 由于结构像一棵倒立的树,顾名思义为二叉树 ; 如下图所示,该图即为一棵 野生的二叉树 ; 既然二叉树为树,固然有着和树一样的部分( 叶子、根、分支… ) 这些也成为

    2024年02月17日
    浏览(44)
  • 数据结构 | 二叉树的概念及前中后序遍历

    下面内容来自百度百科 二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能

    2024年02月05日
    浏览(37)
  • 【数据结构】二叉树的·深度优先遍历(前中后序遍历)and·广度优先(层序遍历)

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 (1) 先序遍历 的过

    2024年01月24日
    浏览(45)
  • (“树” 之 前中后序遍历 ) 94. 二叉树的中序遍历 ——【Leetcode每日一题】

    层次遍历顺序:[1 2 3 4 5 6] 前序遍历顺序:[1 2 4 5 3 6] 中序遍历顺序:[4 2 5 1 3 6] 后序遍历顺序:[4 5 2 6 3 1] 层次遍历使用 BFS 实现,利用的就是 BFS 一层一层遍历的特性;而前序、中序、后序遍历利用了 DFS 实现。 前序、中序、后序遍只是在对节点访问的顺序有一点不同,其它

    2023年04月23日
    浏览(49)
  • 【Java数据结构】二叉树的前中后序遍历(递归和非递归)

    二叉树遍历是二叉树的一种重要操作 必须要掌握 二叉树的遍历可以用递归和非递归两种做法来实现 前序遍历的遍历方式是 先根节点 在左节点 在右节点 述这棵树前序遍历的结果是: A B D E C F G 递归的思想就是把问题拆分成一个个小问题来解决 treeNode是一个内部类 具体实现

    2023年04月26日
    浏览(52)
  • 【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历

    除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。 一个深度为k的有n个节点的二叉树,对树中的节点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全

    2024年02月13日
    浏览(34)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(46)
  • 二叉树前中后序的非递归实现

    前言  :  递归我们会有一些问题的 为什么有递归就一定有非递归呢??首先递归是有一定缺陷的 递归真正的缺陷是,每一个程序运行起来呢都是一个线程的形式,但是每一个线程都会有独立的栈空间,但是栈空间是很小的,当递归的深度太深容易栈溢出!!        只要

    2024年02月13日
    浏览(47)
  • 【数据结构】前中后层序遍历 --二叉树的结构特点与遍历方式

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月09日
    浏览(84)
  • 数据结构——二叉树的先中后序遍历

    ——本节内容为Bilibili王道考研《数据结构》P43~P45视频内容笔记。 目录 一、二叉树的先中后序遍历 1.先中后序遍历 2.举例  3.先中后序遍历和前中后缀的关系 4.代码实现 5.求遍历序列 6.应用:求树的深度 二、二叉树的层次遍历 1.层次遍历 2.算法思想: 3.算法演示: 4.代码实

    2024年02月12日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包