二叉树
结构描述:
#include <iostream>
#include <queue>
using namespace std;
typedef int DataType;
class Node {
private:
DataType data;
Node * left;
Node * right;
friend class BinaryTree;
};
typedef class BinaryTree {
private:
Node * root;
//前序遍历
void preOrderTraverse(const Node * root);
//中序遍历
void inOrderTraverse(const Node * root);
//后序遍历
void postOrderTraverse(const Node * root);
//层序遍历
void levelOrderTraverse(const Node * root);
public:
//初始化
BinaryTree() {
root = nullptr;
}
//分配节点
Node * buyNode(DataType x);
//手动构建
void createManual();
//前序遍历
void preOrderTraverse();
//中序遍历
void inOrderTraverse();
//后序遍历
void postOrderTraverse();
//层序遍历
void levelOrderTraverse();
}BT;
前序遍历
- 树空:返回空
- 非空:
- 处理根节点
- 处理左子树
- 处理右子树
void BT::preOrderTraverse(const Node * root) {
if (root == nullptr) {
return;
}
cout << root->data << " ";
preOrderTraverse(root->left);
preOrderTraverse(root->right);
}
中序遍历
- 树空:返回空
- 非空:
- 处理左子树
- 处理根节点
- 处理右子树
void BT::inOrderTraverse(const Node * root) {
if (root == nullptr) {
return;
}
inOrderTraverse(root->left);
cout << root->data << " ";
inOrderTraverse(root->right);
}
后序遍历
- 树空:返回空
- 非空:
- 处理左子树
- 处理右子树
- 处理根节点
void BT::postOrderTraverse(const Node * root) {
if (root == nullptr) {
return;
}
postOrderTraverse(root->left);
postOrderTraverse(root->right);
cout << root->data << " ";
}
层序遍历
- 树空:返回空
- 非空:
- 先把根节点入队,然后进入循环,对队列进行操作。
- 获取队头元素并输出;
- 判断节点的左右子节点是否存在,存在则入队;
- 把队头元素出队
- 重复2,3,4步操作,直至队空
void BT::levelOrderTraverse(const Node * root) {
if (root == nullptr) {
return;
}
//建立一个存放Node*型数据的队列
queue<const Node *> qn;
const Node * cur;
//根节点先进队列
qn.push(root);
//队列非空时持续循环
while (!qn.empty()) {
//获取队头指针
cur = qn.front();
//输出队头元素
cout << cur->data << " ";
//判断是否有子节点,有则入队
if (cur->left != nullptr) {
qn.push(cur->left);
}
if (cur->right != nullptr) {
qn.push(cur->right);
}
//把队头元素出队
qn.pop();
}
}
踩坑记录
在private和public中分别写上遍历函数,具体实现放在private中实现,用public中的函数调用即可。
但是名字是一样的时候,注意二者的参数。
标签:Node,遍历,const,void,nullptr,二叉树,数据结构,root From: https://www.cnblogs.com/codels/p/18322845