Coor.h
#pragma once
#include <ostream>
#include <iostream>
using namespace std;
class Coor {
friend ostream& operator<<(ostream& out, Coor &coor);
public:
Coor(int _x = -1, int _y = -1);
bool operator==(const Coor &coor);
void operator=(const Coor &coor);
private:
int x;
int y;
};
ostream& operator<<(ostream& out, Coor &coor) {
if (&coor == NULL)
out << "NULL" << endl;
else
out << "(" << coor.x << "," << coor.y << ")" << endl;
return out;
}
Coor::Coor(int _x, int _y) {
x = _x;
y = _y;
}
bool Coor::operator==(const Coor &coor) {
if (this->x == coor.x && this->y == coor.y)
return true;
return false;
}
void Coor::operator=(const Coor &coor) {
if (&coor != NULL) {
this->x = coor.x;
this->y = coor.y;
}
else {
this->x = -1;
this->y = -1;
}
}
Node.h
#pragma once
#include <iostream>
template <typename T>
class Node {
public :
Node();
~Node();
int index;
T *date;
Node<T> *parent;
Node<T> *leftSonNode;
Node<T> *rightSonNode;
};
template <typename T>
Node<T>::Node() {
// 初始化一个空节点
date = NULL;
index = -1;
parent = NULL;
leftSonNode = NULL;
rightSonNode = NULL;
}
template <typename T>
Node<T>::~Node() {
delete date;
date = NULL;
delete leftSonNode;
leftSonNode = NULL;
delete rightSonNode;
rightSonNode = NULL;
}
Tree.h
#pragma once
#include "Node.h"
#include "Coor.h"
#include <iostream>
template <typename T>
class Tree {
public:
// 构造一棵二叉树，初始化根节点（索引0数据NULL左右子为NULL）,树的高度
Tree();
//TEST 数据
void testDate() {
Node<T> *n1 = new Node<T>();
n1->index = root->index * 2 + 1;
Coor *c1 = new Coor(1, 1);
n1->date = c1;
Node<T> *n2 = new Node<T>();
n2->index = root->index * 2 + 2;
Coor *c2 = new Coor(2, 2);
n2->date = c2;
root->leftSonNode = n1;
root->rightSonNode = n2;
}
// 销毁二叉树。循环/递归遍历销毁全部子节点
~Tree();
// 搜索指定索引的节点的数据，并返回该索引节点的数据 T
bool search(int &nodeIndex, T &elem);
// 在指定索引的节点上插入 0左/1右 子节点，数据为elem
bool addNode(int nodeIndex, int direction, T *elem);
// 删除指定索引的节点以及该节点的子孙节点
void deleteNode(int nodeIndex);
// 前中后 序遍历
void preTraversal();
void seqTraversal();
void orderTraversal();
private:
// 根节点
Node<T> *root;
// 搜索指定索引的节点，并返回该节点的内存地址给_node
void searchAll(Node<T> *node, int &index, Node<T> **_node);
// 删除指定节点及其子孙
void deleteAll(Node<T> *node);
// 前中后 序遍历递归函数
void traversal(Node<T> *node,char i);
};
template <typename T>
// 构造一棵二叉树，初始化根节点（索引0数据NULL）,树的高度
Tree<T>::Tree() {
root = new Node<T>();
root->index = 0;
//testDate();
}
template <typename T>
// 销毁二叉树。循环/递归遍历销毁全部子节点
Tree<T>::~Tree() {
deleteNode(root->index);
}
template <typename T>
// 搜索指定索引的节点的数据，并返回该索引节点的数据 T
bool Tree<T>::search(int &nodeIndex, T &elem) {
Node<T> *_node = NULL;
searchAll(root, nodeIndex, &_node);
if (NULL != _node && -1 != _node->index)
elem = *_node->date; // 注：避免Node<T>里面的是空数据而引发异常，已重写 =（赋值） 号
return true;
}
// 搜索指定索引的节点，并返回该节点的内存地址给_node
template <typename T>
void Tree<T>::searchAll(Node<T> *node, int &index, Node<T> **_node) {
if (node->index == index) {
*_node = node;
return;
}
else {
if (node->leftSonNode != NULL)
searchAll(node->leftSonNode, index, _node);
if (node->rightSonNode != NULL)
searchAll(node->rightSonNode, index, _node);
return;
}
}
template <typename T>
// 在指定索引的节点上插入 0左/1右 子节点，数据为elem
bool Tree<T>::addNode(int nodeIndex, int direction, T *elem) {
if (direction != 0 && direction != 1)
return false;
Node<T> *_node = NULL; // 不用回收内存，因为是挂载着的
searchAll(root, nodeIndex, &_node);
if ( NULL == _node || -1 == _node->index)
return false;
Node<T> *temp = new Node<T>(); // 不用回收内存，因为是挂载着的
temp->date = elem;
temp->parent = _node;
if (0 == direction) {
temp->index = nodeIndex * 2 + 1;
_node->leftSonNode = temp;
}
else {
temp->index = nodeIndex * 2 + 2;
_node->rightSonNode = temp;
}
return true;
}
template <typename T>
// 删除指定索引的节点以及该节点的子孙节点，并返回该节点的数据
void Tree<T>::deleteNode(int nodeIndex) {
if (0 == nodeIndex) {
deleteAll(root);
root = NULL;
}
else {
Node<T> *_node = NULL;
Node<T> *parent = NULL;
searchAll(root, nodeIndex, &_node);
if (NULL == _node)
return;
parent = _node->parent;
_node->index % 2 == 1 ? parent->leftSonNode = NULL : parent->rightSonNode = NULL;
deleteAll(_node);
}
}
template <typename T>
// 删除指定节点及其子孙
void Tree<T>::deleteAll(Node<T> *node) {
if (NULL != node->leftSonNode) {
deleteAll(node->leftSonNode);
node->leftSonNode = NULL;
}
if (NULL != node->rightSonNode) {
deleteAll(node->rightSonNode);
node->rightSonNode = NULL;
}
delete node;
node = NULL;
}
// 前中后 序遍历
template <typename T>
void Tree<T>::preTraversal() {
traversal(root,'P');
}
template <typename T>
void Tree<T>::seqTraversal() {
traversal(root, 'S');
}
template <typename T>
void Tree<T>::orderTraversal() {
traversal(root, 'O');
}
template <typename T>
void Tree<T>::traversal(Node<T> *node, char i)  {
if (NULL == node) 
return;
if (i == 'P') {
cout << node->index << "  ";
if (NULL != node->leftSonNode)
traversal(node->leftSonNode, i);
if (NULL != node->rightSonNode)
traversal(node->rightSonNode, i);
}
else if (i == 'S') {
if (NULL != node->leftSonNode)
traversal(node->leftSonNode, i);
cout << node->index << "  ";
if (NULL != node->rightSonNode)
traversal(node->rightSonNode, i);
}
else if (i == 'O') {
if (NULL != node->leftSonNode)
traversal(node->leftSonNode, i);
if (NULL != node->rightSonNode)
traversal(node->rightSonNode, i);
cout << node->index << "  ";
}
}
Demo.cpp
#include "Node.h"
#include "Tree.h"
#include "Coor.h"
#include <iostream>
using namespace std;
int main() {
Tree<Coor> *t = new Tree<Coor>();
Coor *c1 = new Coor(1,2);
Coor *c2 = new Coor(2,4);
t->addNode(1, 0, c1) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
t->addNode(1, 1, c2) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
t->addNode(0, 0, c1) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
t->addNode(0, 1, c2) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
Coor *c3 = new Coor(3, 3);
Coor *c4 = new Coor(4, 4);
Coor *c5 = new Coor(5, 5);
Coor *c6 = new Coor(6, 6);
t->addNode(1, 0, c3) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
t->addNode(1, 1, c4) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
t->addNode(2, 0, c5) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
t->addNode(2, 1, c6) == true ? cout << "插入成功" << endl : cout << "插入失败" << endl;
cout << endl;
t->preTraversal();
cout << endl;
t->seqTraversal();
cout << endl;
t->orderTraversal();
cout << endl;
cout << endl;
Coor c;
int cc = 1;
t->search(cc, c);
cout << c;
cc = 0;
t->search(cc, c);
cout << c;
cc = 2;
t->search(cc, c);
cout << c;
cc = 3;
t->search(cc, c);
cout << c;
t->deleteNode(1);
cout << endl;
cc = 1;
t->search(cc, c);
cout << c;
cc = 0;
t->search(cc, c);
cout << c;
cc = 2;
t->search(cc, c);
cout << c;
cc = 3;
t->search(cc, c);
cout << c;
delete t;
t = NULL;
}
/*
输出正确：
插入失败
插入失败
插入成功
插入成功
插入成功
插入成功
插入成功
插入成功
0  1  3  4  2  5  6
3  1  4  0  5  2  6
3  4  1  5  6  2  0
(1,2)
(-1,-1)
(2,4)
(3,3)
(3,3)
(-1,-1)
(2,4)
(2,4)
*/