数据结构探险-04树篇

数据结构探险之树篇-慕课网
C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l04_tree at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

课程从树的实现原理角度讲解了树的相关概念，着重讲解了二叉树三种遍历方式的原理，并通过编码实践，进一步说明二叉树使用数组和链表方式的编程技巧，以及前序遍历、中序遍历和后序遍历递归实现

1 树的基本概念

树是节点的有限集合。

1.1 基础概念

孩子：一个节点的直接子节点称为这个节点的孩子。
双亲：节点的父节点，称为这个节点的双亲。
度：一个节点的字节点的数量。
叶子：终端节点。
根：外界能访问到的这个树数据结构的入口节点。
祖先： 一个节点从父节点往上一直到跟节点之间的所有节点都是这个节点的祖先。
子孙： 一个节点从子节点往下一直到叶子节点都是它的子孙。

节点深度： 一个节点所在的层数。
树的深度： 一个树中深度最大的节点的深度就是这个树的深度。

森林：多个树的集合构成森林。

1.2 二叉树

描述：二叉树是一种特殊的树，它的所有节点的度都小于等于2。

1.2.1 二叉树遍历

前序遍历： 根 -> 左子 -> 右子。
中序遍历： 左子 -> 根 -> 右子
后序遍历： 左子 -> 右子 -> 根

1.3 用途

• 压缩软件：赫夫曼编码。
• 象棋、围棋等游戏软件

2 二叉树数组实现

2.1 原理

如果一个树是完全二叉树，就很容易转换为数组，反过来也可以将数组还原为二叉树。为了让所有二叉树都可以可以和数组相互转换，可以用一个“空”值填上二叉树中“缺失”的节点，从而构成一个完全二叉树。

例如，[3, 5, 8, 2, 6, 0, 7]，构建的树如下

这时，下标为 N 的父节点，左子节点为 N 2 + 1，右子节点下标为 N 2 + 2。

2.2 实现

C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l04_tree/0301_with_array at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

• 树的创建和销毁
• 树中节点的搜索
• 树中节点的添加和删除
• 树中节点的遍历

.
├── Tree.cpp
├── Tree.h
├── main.cpp
└── makefile

Tree.h

#ifndef TREE_H
#define TREE_H

class Tree
{
public:
	Tree(int size, int *pRoot); // 创建树
	~Tree(); // 销毁树
	int *SearchNode(int nodeIndex); // 根据索引寻找节点
	bool AddNode(int nodeIndex, int direction, int *pNode); // 添加节点
	bool DeleteNode(int nodeIndex, int *pNode); // 删除节点
	void TreeTraverse(); // 遍历节点
private:
	int *m_pTree;
	int m_iSize;
};

#endif

Tree.cpp

#include <iostream>
#include "Tree.h"
using namespace std;

Tree::Tree(int size, int *pRoot)
{
	m_iSize = size;
	m_pTree = new int[size];
	for(int i = 0; i < size; i++)
	{
		m_pTree[i] = 0;
	}
	m_pTree[0] = *pRoot;
}

Tree::~Tree()
{
	delete m_pTree;
	m_pTree = NULL;
}

int *Tree::SearchNode(int nodeIndex)
{
	// 下标不在有效范围内
	if(nodeIndex < 0 || nodeIndex >= m_iSize)
	{
		return NULL;
	}
	// 值为 0 代表没有节点
	if(m_pTree[nodeIndex] == 0)
	{
		return NULL;
	}
	return &m_pTree[nodeIndex];
}

/** param{int} nodeIndex 要插入哪个节点下面* param{int} direction 0 左节点，1 右节点* param{int *} pNode 要插入的节点的指针* return{bool} true 插入成功， false 插入失败*/
* param{int} nodeIndex 要插入哪个节点下面
* param{int} direction 0 左节点，1 右节点
* param{int *} pNode 要插入的节点的指针
* return{bool} true 插入成功， false 插入失败
*/
bool Tree::AddNode(int nodeIndex, int direction, int *pNode)
{
	// 下标不在有效范围内
	if(nodeIndex < 0 || nodeIndex >= m_iSize)
	{
		return false;
	}
	// 要插入的地方的父节点不存在
	if(m_pTree[nodeIndex] == 0)
	{
		return false;
	}

	// 如果作为左节点插入
	if(direction == 0)
	{
		int leftChildIndex = nodeIndex * 2 + 1;
		if(leftChildIndex >= m_iSize)
		{
			return false;
		}
		// 左子节点已经有数据了
		if(m_pTree[leftChildIndex] != 0)
		{
			return false;
		}
		m_pTree[leftChildIndex] = *pNode;
	}

	// 如果作为右节点插入
	if(direction == 1)
	{
		int rightChildIndex = nodeIndex * 2 + 2;
		if(rightChildIndex >= m_iSize)
		{
			return false;
		}
		// 左子节点已经有数据了
		if(m_pTree[rightChildIndex] != 0)
		{
			return false;
		}
		m_pTree[rightChildIndex] = *pNode;
	}
	return true;
}

bool Tree::DeleteNode(int nodeIndex, int *pNode)
{
	// 节点下标不在合法范围中
	if(nodeIndex < 0 || nodeIndex >= m_iSize)
	{
		return false;
	}
	// 没有这个节点
	if(m_pTree[nodeIndex] == 0)
	{
		return false;
	}
	*pNode = m_pTree[nodeIndex];
	m_pTree[nodeIndex] = 0;
	return true;
}

void Tree::TreeTraverse()
{
	for(int i = 0; i < m_iSize; i++)
	{
		cout << m_pTree[i] << " ";
	}
	cout << endl;
}

main.cpp

#include <iostream>
#include "Tree.h"
using namespace std;

int main(void){

	// 创建（构造器要设置好根节点）
	int root = 3;
	Tree *pTree = new Tree(10, &root);

	// 插入节点
	int node1 = 5;
	int node2 = 8;
	int node3 = 2;
	int node4 = 6;
	int node5 = 0;
	int node6 = 7;

	pTree->AddNode(0, 0, &node1);
	pTree->AddNode(0, 1, &node2);
	pTree->AddNode(1, 0, &node3);
	pTree->AddNode(1, 1, &node4);
	pTree->AddNode(2, 0, &node5);
	pTree->AddNode(2, 1, &node6);

	// 遍历
	pTree->TreeTraverse();

	// 搜索
	int *p = pTree->SearchNode(2);
	cout << "SearchNode:" << *p << endl;

	// 删除
	int node = 0;
	bool isDeleteSuccess = pTree->DeleteNode(0, &node);
	cout << (isDeleteSuccess ? "true" : "false") << endl;
	pTree->TreeTraverse();

	return 0;
}

3 二叉树链表实现

3.1 原理

说明： 和使用数组相比，使用链表来实现树存在以下区别

• 删除一个节点必须同时删除其子孙节点
• 清空树需要遍历整个树分别释放每个节点的内存
• 遍历方式分前序、中序、后序三种（数组实现只有一种，不是这三种的任何一种）

建议：不在树的第一个节点上放有意义的值。

3.1.1 节点要素

• 索引
• 数据
• 左孩子指针
• 右孩子指针

3.1.2 遍历

前序：根 -> 左子 -> 右子

中序：左子 -> 根 -> 右子

后序：右子 -> 左子 -> 根

3.2 实现

C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l04_tree/0401_with_list at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

.
├── main.cpp
├── Tree.h
├── Tree.cpp
├── Node.h
├── Node.cpp
└── makefile

main.cpp

#include <iostream>
#include "Tree.h"
using namespace std;


int main(void){

	/*	* 创建二叉树	*				0(0)	*	*		5(1)			8(2)	*	*	2(3)	6(4)	7(5)	9(6)	*/
	* 创建二叉树
	*				0(0)
	*
	*		5(1)			8(2)
	*
	*	2(3)	6(4)	7(5)	9(6)
	*/
	Tree *tree = new Tree();

	Node *node1 = new Node(1, 5);
	Node *node2 = new Node(2, 8);
	Node *node3 = new Node(3, 2);
	Node *node4 = new Node(4, 6);
	Node *node5 = new Node(5, 7);
	Node *node6 = new Node(6, 9);

	tree->AddNode(0, 0, node1);
	tree->AddNode(0, 1, node2);
	tree->AddNode(1, 0, node3);
	tree->AddNode(1, 1, node4);
	tree->AddNode(2, 0, node5);
	tree->AddNode(2, 1, node6);

	// 前序
	tree->PreorderTraversal(); // (0) 5(1) 2(3) 6(4) 8(2) 7(5) 9(6)
	// 中序
	tree->InorderTraversal(); // 2(3) 5(1) 6(4) 0(0) 7(5) 8(2) 9(6)
	// 后序
	tree->PostorderTraversal(); // 2(3) 6(4) 5(1) 7(5) 9(6) 8(2) 0(0)

	// 删除节点
	tree->DeleteNode(2, NULL);
	tree->PreorderTraversal();
	
	delete tree;
	tree = NULL;
	return 0;
}

Tree.h

#ifndef TREE_H
#define TREE_H
#include "Node.h"
class Tree
{
public:
	Tree(); // 创建树
	~Tree(); // 销毁树
	Node *SearchNode(int nodeIndex); // 搜索节点
	bool AddNode(int nodeIndex, int direction, Node *pNode); // 添加节点
	bool DeleteNode(int nodeIndex, Node *pNode); // 删除节点
	void PreorderTraversal(); // 前序遍历
	void InorderTraversal(); // 中序遍历
	void PostorderTraversal(); // 后序遍历
private:
	Node *m_pRoot;
};

#endif

Tree.cpp

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

using namespace std;

Tree::Tree()
{
	m_pRoot = new Node();
}

Tree::~Tree()
{
	// DeleteNode(0, NULL);
	m_pRoot->DeleteNode();
}
bool Tree::AddNode(int nodeIndex, int direction, Node *pNode)
{
	// 要挂载的位置不存在
	Node *temp = SearchNode(nodeIndex);
	if(temp == NULL)
	{
		return false;
	}
	// 创建挂载上去的节点
	Node *node = new Node();
	// 申请空间失败
	if(node == NULL)
	{
		return false;
	}
	node->index = pNode->index;
	node->data = pNode->data;
	node->pParent = temp;

	if(direction == 0)
	{
		temp->pLChild = node;
	}
	if(direction == 1)
	{
		temp->pRChild = node;
	}
	return true;
}

Node *Tree::SearchNode(int nodeIndex)
{
	return m_pRoot->SearchNode(nodeIndex);
}

bool Tree::DeleteNode(int nodeIndex, Node *pNode)
{
	Node *temp = SearchNode(nodeIndex);
	if(temp == NULL)
	{
		return false;
	}
	if(pNode != NULL)
	{
		pNode->data = temp->data;
	}
	temp->DeleteNode();	
	return true;
}

void Tree::PreorderTraversal()
{
	m_pRoot->PreorderTraversal();
	cout << endl;
}

void Tree::InorderTraversal()
{
	m_pRoot->InorderTraversal();
	cout << endl;
}

void Tree::PostorderTraversal()
{
	m_pRoot->PostorderTraversal();
	cout << endl;
}

Node.h

#ifndef NODE_H
#define NODE_H

class Node
{
public:
	Node(int index = 0, int data = 0);
	Node *SearchNode(int nodeIndex); // 递归寻找节点
	void DeleteNode(); // 递归删除节点
	void PreorderTraversal(); // 后序
	void InorderTraversal(); // 中序
	void PostorderTraversal(); // 后序
	int index;
	int data;
	Node *pLChild;
	Node *pRChild;
	Node *pParent;
};

#endif

Node.cpp

#include <iostream>
#include "Node.h"
using namespace std;
Node::Node(int index, int data)
{
	this->index = index;
	this->data = data;
	pLChild = NULL;
	pRChild = NULL;
	pParent = NULL;
}

Node *Node::SearchNode(int nodeIndex)
{
	Node *temp = NULL;
	// 判断当前节点数据
	if(this->index == nodeIndex)
	{
		return this;
	}
	// 递归左节点数据
	if(this->pLChild != NULL)
	{
		temp = this->pLChild->SearchNode(nodeIndex);
		if(temp != NULL)
		{
			return temp;
		}
	}
	// 递归右节点数据
	if(this->pRChild != NULL)
	{
		temp = this->pRChild->SearchNode(nodeIndex);
		if(temp != NULL)
		{
			return temp;
		}
	}
	return NULL;
}

void Node::DeleteNode()
{
	if(this->pLChild != NULL)
	{
		this->pLChild->DeleteNode();
	}
	if(this->pRChild != NULL)
	{
		this->pRChild->DeleteNode();
	}
	if(this->pParent != NULL)
	{
		if(this->pParent->pLChild == this)
		{
			this->pParent->pLChild = NULL;
		}
		if(this->pParent->pRChild == this)
		{
			this->pParent->pRChild = NULL;
		}
	}
	delete this;
}

void Node::PreorderTraversal()
{
	// 根
	cout << this->data << "(" << this->index << ")" << " ";
	// 左
	if(this->pLChild != NULL)
	{
		this->pLChild->PreorderTraversal();
	}
	// 右
	if(this->pRChild != NULL)
	{
		this->pRChild->PreorderTraversal();
	}
}

void Node::InorderTraversal()
{
	// 左
	if(this->pLChild != NULL)
	{
		this->pLChild->InorderTraversal();
	}
	// 根
	cout << this->data << "(" << this->index << ")" << " ";
	// 右
	if(this->pRChild != NULL)
	{
		this->pRChild->InorderTraversal();
	}
}

void Node::PostorderTraversal()
{
	// 左
	if(this->pLChild != NULL)
	{
		this->pLChild->PostorderTraversal();
	}
	// 右
	if(this->pRChild != NULL)
	{
		this->pRChild->PostorderTraversal();
	}
	// 根
	cout << this->data << "(" << this->index << ")" << " ";
}