数据结构-树

简介

1. 树是由一个集合以及在该集合上定义的一种关系构成的，集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构，在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点。

树的一些基本定义

1. 树的结点——包含数据结构及若干指向其子树的分支
2. 结点的度——结点拥有的子树
3. 终端结点（叶子）——度为0的结点
4. 非终端结点（分支结点）——度不为0的结点
5. 树的度——树内各结点的度的最大值
6. 孩子——结点的子树
7. 兄弟——同一个双亲的孩子互相之间互称兄弟
8. 祖先——从根到该结点所经分支上的所有结点
9. 层次——从根开始定义起，根为第一层，根的孩子为第二层
10. 深度——树中结点的最大层次
11. 有序树——树中结点的各子数看成从左往右是有次序的
12. 森林——互不相交的树的集合
13. 二叉树——每个结点至多只有两个子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
14. 满二叉树——一颗深度为k且有2的k次方-1个结点的二叉树
15. 完全二叉树——深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树
16. 线索二叉树 ——对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树

二叉树的特点

1. 在二叉树的第 i 层上至多有 2^(i-1) 个结点
2. 深度为 k 的二叉树至多有 2^k-1 个节点
3. 对任何一颗二叉树T，如果其终端结点数n0,度为2的结点数为n2,则 n0=n2+1

二叉树的存储结构

1. 顺式存储
2. 链式存储

这里我们主要介绍链式存储结构

二叉树的代码实现

#include <iostream>
#include <queue>
using namespace std;

class TreeNode
{
public:
	int data;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
	//分别代表左子树和右子树
	TreeNode(int data) :data(data) {};
	~TreeNode() {};
};

class Tree
{
public:
	TreeNode* root = nullptr;
	Tree() {};
	void Add(int data);						//压入元素
	void PreOrder(const TreeNode* node);	//先序便利
	void InOrder(const TreeNode* node);		//中序遍历
	void PostOrder(const TreeNode* node);	//后序遍历
	void Level (TreeNode* node);	    	//层次遍历
    ~Tree();
private:
	void DestoryTree(const TreeNode* node);		//销毁树
};
void Tree::Add(int data) 
{
	TreeNode* node = new TreeNode(data);	//创建节点
	queue<TreeNode*> queue;
	queue.push(root);		//将节点压入队列
	if (!this->root)
	{
		root = node;
		return;
	}
	while (!queue.empty()) 
	{
		TreeNode* 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 Tree::PreOrder(const TreeNode* node) 
{
	if (!node) 
		return;
	cout << node->data << " ";
	PreOrder(node->lchild);
	PreOrder(node->rchild);
}

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

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

void Tree::Level(TreeNode* node) 
{
	if (!node) 
		return;
	queue<TreeNode*> q;
	q.push(node);
	while (!q.empty()) 
	{
		TreeNode* node = q.front();
		q.pop();
		cout << node->data << " ";
		if (node->lchild) q.push(node->lchild);
		if (node->rchild) q.push(node->rchild);
	}
}

void Tree::DestoryTree(const TreeNode* node) 
{
	if (node)
	{
		if (node->lchild)				//如果左节点存在
			DestoryTree(node->lchild);	//销毁左子树
		if (node->rchild)				//如果右节点存在
			DestoryTree(node->rchild);	//销毁右子树
	}
	delete node;
	node = nullptr;
}

Tree::~Tree()
{
	DestoryTree(root);
}

int main()
{
	Tree tree;
	tree.Add(1);
	tree.Add(2);
	tree.Add(3);
	tree.Add(21);
	tree.Add(22);
	tree.Add(31);
	tree.Add(32);
	cout << "先序遍历：";
	tree.PreOrder(tree.root);
	cout << endl << "中序遍历：";
	tree.InOrder(tree.root);
	cout << endl << "后序遍历：";
	tree.PostOrder(tree.root);
	cout << endl << "层次遍历：";
	tree.Level(tree.root);
	cout << endl;
	return 0;
}

输出为

先序遍历：1 2 21 22 3 31 32
中序遍历：21 2 22 1 31 3 32
后序遍历：21 22 2 31 32 3 1
层次遍历：1 2 3 21 22 31 32

例题

从上往下打印二叉树

二叉树的镜像

二叉树的深度

平衡二叉树

二叉树的镜像