C++二叉树的创建与遍历

最近学习了二叉树的一点知识，感觉数据结构真的很难啊，所以学习过程中的笔记还是要记录一下。

一、二叉树

在我们使用的数据结构中，一对一的线性结构是我们经常所使用到的，但是现实中却有着许多一对多的情况，这也就产生了“树”这一概念。二叉树则是“树”这一概念中的一种特殊情况，其定义为：“是n(n>=0)个结点的有限集合。该集合或者为空集(称为空二叉树)。或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。”
二叉树的特点：
(1)每个节点最多有两个子树，所以二叉树的节点的度均小于等于2。
(2)左子树和右子树是有顺序的，千万不能对其进行任意颠倒。
…(其特点还有很多，就不一一叙述了)
总的来说，如果说我之前使用的vector和list是一维结构的话，那二叉树就是二维结构。

二、实现代码

Node.h

#ifndef _NODE_
#define _NODE_
#include<string>
using namespace std;

class Node
{
public:
	string data;
	Node* lchild=nullptr;
	Node* rchild=nullptr;
	Node(string);
	~Node();
};

#endif // _NODE_

Node.cpp

#include "Node.h"
Node::Node(string data)
	:data(data)
{
}

Node::~Node()
{
}

BinaryTree.h

#ifndef _BINATYTREE_
#define _BINATYTREE_
#include"Node.h"
#include<queue>
#include<iostream>
using namespace std;

class BinaryTree
{
public:
	Node* root = nullptr;
	BinaryTree();
	void Add(string data);	//添加节点，创建二叉树使用层次遍历
	void PreOrder(const Node* node);	//先序遍历
	void InOrder(const Node* node);		//中序遍历
	void PostOrder(const Node* node);	//后序遍历
	~BinaryTree();	//销毁二叉树

private:
	void DestoryBinaryTree(Node *tree);
};

#endif // !_BINATYTREE_

BinaryTree.cpp

#include "BinaryTree.h"


BinaryTree::BinaryTree()
{
}

void BinaryTree::Add(string data)
{
	Node* node=new Node(data);	//创建节点
	queue<Node*> queue;
	queue.push(root);		//将节点压入队列
	if (!this->root)
	{
		root = node;
		return;
	}
	while (!queue.empty())
	{
		Node* curNode =queue.front();
		queue.pop();
		if (!curNode->lchild)		//如果该节点没有左孩子，则把节点赋给它
		{
			curNode->lchild = node;
			return;
		}
		else
		{
			queue.push(curNode->lchild);	//如果有则压入队列中
		}
		if (!curNode->rchild)
		{
			curNode->rchild = node;
			return;
		}
		else
		{
			queue.push(curNode->rchild);
		}
	}

}

void BinaryTree::PreOrder(const Node* node)
{
	if (!node)
	{
		return;
	}
	cout << node->data << " ";
	PreOrder(node->lchild);
	PreOrder(node->rchild);
}

void BinaryTree::InOrder(const Node * node)
{
	if (!node)
	{
		return;
	}
	InOrder(node->lchild);
	cout << node->data << " ";
	InOrder(node->rchild);
}

void BinaryTree::PostOrder(const Node * node)
{
	if (!node)
	{
		return;
	}
	PostOrder(node->lchild);
	PostOrder(node->rchild);
	cout << node->data << " ";
}

void BinaryTree::DestoryBinaryTree(Node * node)
{
	if (node)	//如果有节点
	{
		if (node->lchild)	//如果存在左孩子
		{
			DestoryBinaryTree(node->lchild);	//销毁二叉树的左子树
		}
		if (node->rchild)
		{
			DestoryBinaryTree(node->rchild);	//销毁二叉树的右子树
		}
	}
	delete node;	//销毁节点
	node = nullptr;	
}

BinaryTree::~BinaryTree()
{
	//遍历销毁
	DestoryBinaryTree(root);
}

main.cpp

#include<iostream>
#include"BinaryTree.h"

using namespace std;

int main()
{
	BinaryTree tree;
	tree.Add("A");
	tree.Add("B");
	tree.Add("C");
	tree.Add("D");
	tree.Add("E");
	tree.Add("F");
	tree.Add("G");
	//tree.Add("1");
	//tree.Add("2");
	//tree.Add("3");
	//tree.Add("4");
	//tree.Add("5");
	cout << "先序遍历：";
	tree.PreOrder(tree.root);
	cout << endl << "中序遍历：";
	tree.InOrder(tree.root);
	cout << endl << "后序遍历：";
	tree.PostOrder(tree.root);
	cout << endl;

	system("pause");
	return 0;
}

三、运行效果

四、小结

在整个过程中，要注意以下几点：
(1)你怎么对二叉树进行遍历，你就可以使用这种遍历方式来创建二叉树。因此二叉树的创建方式有很多种，我选择的是层次创建(与其相对应的是层次遍历，也叫广度优先遍历)。
(2)二叉树的销毁也可以使用其特定的遍历方式进行销毁。
(3)因为层次遍历的过程很适合队列这种结构，所以可以使用queue来实现该遍历过程。

参考书籍：《大话数据结构》