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)
*/