二叉树的创建以及基础遍历算法(c++)
一、二叉树的创建
1.树结构定义
二叉树是树结构的一种特殊结构,每一个节点最多有左孩子和右孩子两个子节点。所以在定义树结构的时候可以定义根节点ID、左右子节点的ID、以及指向左右子节点的指针。定义如下:
class TreeNode
{
public:
TreeNode* m_pLeftChild, * m_pRightChild;
int m_nRootId; //根节点ID
int m_nLeftId; //子孩子节点ID
int m_nRightId; //右孩子节点ID
int m_nChildCount; //子孩子个数
};
2. 二叉树的创建
给定一组数据,在创建的二叉树的时候按照左节点小于根节点,右节点大于根节点的原则进行创建,下面一组数据创建的二叉树结构应如图所示。
int data[9] = { 6, 7, 2, 9, 3, 1, 8, 2, 4 };
创建逻辑如下:
TreeNode *BinaryTree::CreateNode(int data)
{
TreeNode* node = new TreeNode;
node->m_nRootId = data;
node->m_pLeftChild = NULL;
node->m_pRightChild = NULL;
node->m_nChildCount = 0;
node->m_nLeftId = NULL;
node->m_nRightId = NULL;
return node;
}
void BinaryTree::InsertNode(int data)
{
TreeNode* node = CreateNode(data);
if (m_pTreeNode == NULL) {
m_pTreeNode = node;
}
else {
TreeNode* pChild = m_pTreeNode;
while (pChild != NULL) {
if (pChild->m_nRootId > data) { //小于就进左儿子
if (pChild->m_pLeftChild == NULL) {
pChild->m_pLeftChild = node;
pChild->m_nLeftId = data;
pChild->m_nChildCount++;
return;
}
else {
pChild = pChild->m_pLeftChild;
}
}
else {
if (pChild->m_pRightChild == NULL) {
pChild->m_pRightChild = node;
pChild->m_nRightId = data;
pChild->m_nChildCount++;
return;
}
else {
pChild = pChild->m_pRightChild;
}
}
}
}
}
二、二叉树的遍历
二叉树的遍历分为深度优先遍历和广度优先遍历,其中深度优先遍历分为前序遍历、中序遍历和后序遍历;广度优先则是对每一层进行遍历;
深度遍历:
前序遍历:根左右。先打印,再遍历左子树,再遍历右子树;
中序遍历:左根右。先遍历左子树,再打印,再遍历右子树;
后序遍历:左右根。先遍历左子树,再遍历右子树,再打印。
深度优先遍历可以用递归算法和非递归算法实现
1. 递归遍历
1)前序遍历
void BinaryTree::PreorderTraversal(TreeNode *node)
{
if (node == NULL)
return;
cout << node->m_nRootId << " ";
PreorderTraversal(node->m_pLeftChild);
PreorderTraversal(node->m_pRightChild);
}
2)中序遍历
void BinaryTree::InorderTraversal(TreeNode* node)
{
if (node == NULL)
return;
InorderTraversal(node->m_pLeftChild);
cout << node->m_nRootId << " ";
InorderTraversal(node->m_pRightChild);
}
3)后序遍历
void BinaryTree::PostSequenceTraversal(TreeNode* node)
{
if (node == NULL)
return;
PostSequenceTraversal(node->m_pLeftChild);
PostSequenceTraversal(node->m_pRightChild);
cout << node->m_nRootId << " ";
}
2. 非递归遍历
1)前序遍历
void BinaryTree::PreorderTraversal()
{
if (m_pTreeNode == NULL)
return;
stack<TreeNode*> TreeStack;
TreeNode* p = NULL;
TreeStack.push(m_pTreeNode);
while (!TreeStack.empty()) {
p = TreeStack.top();
TreeStack.pop();
cout << p->m_nRootId << " ";
if (p->m_pRightChild != NULL)
TreeStack.push(p->m_pRightChild);
if (p->m_pLeftChild != NULL)
TreeStack.push(p->m_pLeftChild);
}
}
2)中序遍历
void BinaryTree::InorderTraversal()
{
if (m_pTreeNode == NULL)
return;
stack<TreeNode*> TreeStack;
TreeNode* p = NULL;
TreeStack.push(m_pTreeNode);
while (!TreeStack.empty()) {
while ((p = TreeStack.top()) && p) {
TreeStack.push(p->m_pLeftChild); //将节点左孩子放入栈中
}
TreeStack.pop();
if (!TreeStack.empty()) {
p = TreeStack.top();
TreeStack.pop();
cout << p->m_nRootId << " ";
TreeStack.push(p->m_pRightChild);
}
}
}
3)后序遍历
void BinaryTree::PostSequenceTraversal()
{
if (m_pTreeNode == NULL)
return;
stack<TreeNode*> TreeStack1, TreeStack2;
TreeNode* p = NULL;
TreeStack1.push(m_pTreeNode);
while (!TreeStack1.empty()) {
p = TreeStack1.top();
TreeStack1.pop();
TreeStack2.push(p);
if (p->m_pLeftChild != NULL)
TreeStack1.push(p->m_pLeftChild);
if (p->m_pRightChild != NULL)
TreeStack1.push(p->m_pRightChild);
}
while (!TreeStack2.empty()) {
cout << TreeStack2.top()->m_nRootId << " ";
TreeStack2.pop();
}
}
4)广度优先遍历
void BinaryTree::levelOrderTraversal()
{
if (m_pTreeNode == NULL)
return;
queue<TreeNode*> TreeStack;
TreeNode* p = NULL;
TreeStack.push(m_pTreeNode);
while (!TreeStack.empty()) {
p = TreeStack.front();
TreeStack.pop();
if (p->m_pLeftChild != NULL)
TreeStack.push(p->m_pLeftChild);
if (p->m_pRightChild != NULL)
TreeStack.push(p->m_pRightChild);
cout << p->m_nRootId << " ";
}
}
三、完整代码
首先是BinaryTreeNode.h头文件
#pragma once
#include <vector>
using namespace std;
class TreeNode
{
public:
TreeNode* m_pLeftChild, * m_pRightChild;
int m_nRootId; //根节点ID
int m_nLeftId; //子孩子节点ID
int m_nRightId; //右孩子节点ID
int m_nChildCount; //子孩子个数
};
class BinaryTree
{
public:
BinaryTree();
~BinaryTree();
public:
//生成二叉树
void InsertNode(int data);
/*递归算法*/
//前序遍历
void PreorderTraversal(TreeNode* node);
//中序遍历
void InorderTraversal(TreeNode* node);
//后序遍历
void PostSequenceTraversal(TreeNode* node);
/*非递归算法*/
void PreorderTraversal();
void InorderTraversal();
void PostSequenceTraversal();
//广度优先遍历
void levelOrderTraversal();
protected:
TreeNode* CreateNode(int data);
public:
TreeNode* m_pTreeNode;
};
下面是BinaryTreeNode.cpp文件
#include "BinaryTreeNode.h"
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
BinaryTree::BinaryTree()
{
m_pTreeNode = NULL;
}
BinaryTree::~BinaryTree()
{
delete m_pTreeNode;
}
TreeNode *BinaryTree::CreateNode(int data)
{
TreeNode* node = new TreeNode;
node->m_nRootId = data;
node->m_pLeftChild = NULL;
node->m_pRightChild = NULL;
node->m_nChildCount = 0;
node->m_nLeftId = NULL;
node->m_nRightId = NULL;
return node;
}
void BinaryTree::InsertNode(int data)
{
TreeNode* node = CreateNode(data);
if (m_pTreeNode == NULL) {
m_pTreeNode = node;
}
else {
TreeNode* pChild = m_pTreeNode;
while (pChild != NULL) {
if (pChild->m_nRootId > data) { //小于就进左儿子
if (pChild->m_pLeftChild == NULL) {
pChild->m_pLeftChild = node;
pChild->m_nLeftId = data;
pChild->m_nChildCount++;
return;
}
else {
pChild = pChild->m_pLeftChild;
}
}
else {
if (pChild->m_pRightChild == NULL) {
pChild->m_pRightChild = node;
pChild->m_nRightId = data;
pChild->m_nChildCount++;
return;
}
else {
pChild = pChild->m_pRightChild;
}
}
}
}
}
void BinaryTree::PreorderTraversal(TreeNode *node)
{
if (node == NULL)
return;
cout << node->m_nRootId << " ";
PreorderTraversal(node->m_pLeftChild);
PreorderTraversal(node->m_pRightChild);
}
void BinaryTree::InorderTraversal(TreeNode* node)
{
if (node == NULL)
return;
InorderTraversal(node->m_pLeftChild);
cout << node->m_nRootId << " ";
InorderTraversal(node->m_pRightChild);
}
void BinaryTree::PostSequenceTraversal(TreeNode* node)
{
if (node == NULL)
return;
PostSequenceTraversal(node->m_pLeftChild);
PostSequenceTraversal(node->m_pRightChild);
cout << node->m_nRootId << " ";
}
void BinaryTree::PreorderTraversal()
{
if (m_pTreeNode == NULL)
return;
stack<TreeNode*> TreeStack;
TreeNode* p = NULL;
TreeStack.push(m_pTreeNode);
while (!TreeStack.empty()) {
p = TreeStack.top();
TreeStack.pop();
cout << p->m_nRootId << " ";
if (p->m_pRightChild != NULL)
TreeStack.push(p->m_pRightChild);
if (p->m_pLeftChild != NULL)
TreeStack.push(p->m_pLeftChild);
}
}
void BinaryTree::InorderTraversal()
{
if (m_pTreeNode == NULL)
return;
stack<TreeNode*> TreeStack;
TreeNode* p = NULL;
TreeStack.push(m_pTreeNode);
while (!TreeStack.empty()) {
while ((p = TreeStack.top()) && p) {
TreeStack.push(p->m_pLeftChild); //将节点左孩子放入栈中
}
TreeStack.pop();
if (!TreeStack.empty()) {
p = TreeStack.top();
TreeStack.pop();
cout << p->m_nRootId << " ";
TreeStack.push(p->m_pRightChild);
}
}
}
void BinaryTree::PostSequenceTraversal()
{
if (m_pTreeNode == NULL)
return;
stack<TreeNode*> TreeStack1, TreeStack2;
TreeNode* p = NULL;
TreeStack1.push(m_pTreeNode);
while (!TreeStack1.empty()) {
p = TreeStack1.top();
TreeStack1.pop();
TreeStack2.push(p);
if (p->m_pLeftChild != NULL)
TreeStack1.push(p->m_pLeftChild);
if (p->m_pRightChild != NULL)
TreeStack1.push(p->m_pRightChild);
}
while (!TreeStack2.empty()) {
cout << TreeStack2.top()->m_nRootId << " ";
TreeStack2.pop();
}
}
//广度优先遍历
void BinaryTree::levelOrderTraversal()
{
if (m_pTreeNode == NULL)
return;
queue<TreeNode*> TreeStack;
TreeNode* p = NULL;
TreeStack.push(m_pTreeNode);
while (!TreeStack.empty()) {
p = TreeStack.front();
TreeStack.pop();
if (p->m_pLeftChild != NULL)
TreeStack.push(p->m_pLeftChild);
if (p->m_pRightChild != NULL)
TreeStack.push(p->m_pRightChild);
cout << p->m_nRootId << " ";
}
}
下面是main.cpp文件
#include <iostream>
#include "BinaryTreeNode.h"
using namespace std;
int main()
{
int data[9] = { 6, 7, 2, 9, 3, 1, 8, 2, 4 };
BinaryTree bt;
for (int i = 0; i < 9; i++)
bt.InsertNode(data[i]);
cout << "*******递归算法********" << endl;
cout << "前序遍历结果是:" << endl;
bt.PreorderTraversal(bt.m_pTreeNode);
cout << endl;
cout << "中序遍历结果是:" << endl;
bt.InorderTraversal(bt.m_pTreeNode);
cout << endl;
cout << "后序遍历结果是:" << endl;
bt.PostSequenceTraversal(bt.m_pTreeNode);
cout << endl;
cout << endl;
cout << "*******非递归算法********" << endl;
cout << "前序遍历结果是:" << endl;
bt.PreorderTraversal();
cout << endl;
cout << "中序遍历结果是:" << endl;
bt.InorderTraversal();
cout << endl;
cout << "后序遍历结果是:" << endl;
bt.PostSequenceTraversal();
cout << endl;
cout << "广度优先遍历结果是:" << endl;
bt.levelOrderTraversal();
system("pause");
return 0;
}