内容比较多，好好看看
单链表实现二叉树结构综合案例（使用类模板的方法）
--------------------二叉树节点类
#ifndef TREE_NODE
#define TREE_NODE
#include
using namespace std;
template
class Tree_Node
{
friend ostream& operator<< (ostream& out,const Tree_Node& TN);//特例 这里不是：Tree_Node&……模板参数移到前面去了
public:
Tree_Node();
Tree_Node* searchNode(int _index); //判断当前节点，当前节点的孩子节点是否是要寻找的节点
void DeleteNode();
void Preorder();
void Inorder();
void Postorder();
int m_iIndex; //节点的唯一索引值
T m_TData; //节点的数据类型在运行的时候指定
//凡是要用到当前类的声明对象的都要加上模板参数
Tree_Node* m_pLchild; //左孩子指针
Tree_Node* m_pRchild; //右孩子指针
Tree_Node* m_pParent; //父指针
};
template
ostream& operator<<(ostream& out,const Tree_Node& TN) //模板参数又移到形参变量的地方了
{
out< return out;
}
template
Tree_Node::Tree_Node() //实现构造函数，模板参数在类名中已经体现出来了
{
this->m_iIndex =0;
this->m_TData =NULL;
this->m_pLchild =NULL;
this->m_pRchild =NULL;
this->m_pParent =NULL;
}
template
Tree_Node* Tree_Node::searchNode(int _index) //根据节点的唯一索引值，查找节点，并返回节点的指针
{
if (this->m_iIndex == _index) // 这个this指的是根节点这个对象
{
return this;
}
Tree_Node* find_node =NULL; //保存左子树和右子树查找到的结果
if (this->m_pLchild !=NULL)
{
if (this->m_pLchild->m_iIndex == _index)
{
return this->m_pLchild;
}
else //当前节点的左孩子不是目标节点，再查找左孩子的后代，并返回结果，递归实现的关键
{
find_node = this->m_pLchild->searchNode(_index);
//如果在左子树上找到了，则返回找到的节点,如果没有找到，再去右子树查找，在右子树查找的结果不管有没有都返回
if (find_node != NULL)
{
return find_node;
}
}
}
if (this->m_pRchild !=NULL)
{
if (this->m_pRchild->m_iIndex == _index)
{
return this->m_pRchild;
}else
{
find_node =this->m_pRchild->searchNode(_index);
return find_node;
}
}
return NULL; // 要执行到这一步，就说明该节点既没有左孩子和右孩子，本身也不是待查找节点，就返回空指针了
}
template
void Tree_Node::DeleteNode() // 删除节点，递归删除它的左孩子节点和右孩子节点
{
if (this->m_pLchild !=NULL) //如果当前节点的左孩子节点不为空，则递归删除该左孩子节点和左孩子所有后代节点
{
this->m_pLchild->DeleteNode();
}
if (this->m_pRchild != NULL)//如果当前节点的右孩子节点不为空，则递归删除该子节点的所有后代
{
this->m_pRchild->DeleteNode();
}
//如果当前节点的父指针不为空，把这个指向关系置空
if (this->m_pParent != NULL)
{
//判断当前节点是父节点的左孩子还是右孩子，以便置空父节点的左孩子指针还是右孩子指针
if (this->m_pParent->m_pLchild == this)
{
this->m_pParent->m_pLchild =NULL; //如果当前节点是父节点的左孩子，则置空父节点的
}
if (this->m_pParent->m_pRchild == this)
{
this->m_pParent->m_pRchild =NULL;
}
}
delete this;
//这里没有显示的定义析构函数的原因是，删除节点的时候，该节点的所有指针对象都已经是空值了，没有释放内存空间的需要
// 自身节点也就是一个数据域，使用系统默认的析构函数就能完成这一点
//最后再删除本身这个节点，递归执行到这一步，就是叶子节点做的操作，这一层递归结束后，它的父节点就变成了叶子节点，递归很合理
}
template
void Tree_Node::Preorder() // 二叉树的前序遍历
{
//前序遍历先输出本身，再输出左子树，后输出右子树,递归的使用本身
cout<m_iIndex<<"："<m_TData< if (this->m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
{
this->m_pLchild->Preorder();
}
if (this->m_pRchild !=NULL)
{
this->m_pRchild->Preorder();
}
}
template
void Tree_Node::Inorder() //二叉树的中序遍历
{
//中序遍历先输出左子树，再输出根，后输出右子树
if (this->m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
{
this->m_pLchild->Inorder();
}
cout<m_iIndex<<"："<m_TData< if (this->m_pRchild !=NULL)
{
this->m_pRchild->Inorder();
}
}
template
void Tree_Node::Postorder() //二叉树的后序遍历
{
if (this->m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
{
this->m_pLchild->Postorder();
}
if (this->m_pRchild !=NULL)
{
this->m_pRchild->Postorder();
}
cout<m_iIndex<<"："<m_TData<}
#endif
------------------------------二叉树类的实现，带有模板参数的类，声明和实现最好放在一个文件中，不容易出错
#ifndef TREE_h
#define TREE_h
#include "Tree_Node.h"
template
class Tree
{
public:
Tree();
Tree_Node* searchNode(int _index); //从根节点递归的方法向下搜索树，知道找到节点的索引等于参数的索引值
bool AddNode(int _index, int _direction,Tree_Node* pNode); //添加节点
bool DeleteNode(int _index); //删除节点，不仅仅要删除自己，还要删除自己所有的后代节点，父节点的指向，用递归来实现
~Tree(); //析构函数
//树的前序遍历，后序遍历和中序遍历都是递归的方法，递归的调用节点中的方法，从这里就看到面向对象编程的好处了，比C语言的方法简单多了
void Preorder();
void Inorder();
void Postorder();
private:
Tree_Node* m_pTree;
};
template
Tree::Tree()
{
this->m_pTree = new Tree_Node();
//第一个节点为根节点，索引默认为0，未指定它的孩子节点，所以孩子节点指针为空，父节点不存在，指向默认为空
//这个地方出现了错误，写代码的时候语法没有检测出来，任何地方使用带有模板参数的函数都要加上参数列表
//错误的写法：this->m_pTree = new Tree_Node();
}
template
Tree_Node* Tree::searchNode(int _index)
{
return this->m_pTree->searchNode(_index);
}
template
bool Tree::AddNode(int _index, int _direction,Tree_Node* pNode)
{
Tree_Node* direction_node = this->searchNode(_index);
//插入节点是在指定的节点下插入，如果这个指定的节点不存在，插入操作就失败了
if (direction_node ==NULL)
{
return false;
}
//不能传进来的临时节点pNode做为树中新增的结点，因为是对指针的操作，外部操作pNode会同步影响到插入树中节点的值，应该重新申请一块内存空间
Tree_Node* new_node =new Tree_Node();
if (NULL == new_node)
{
return false;
}
new_node->m_iIndex = pNode->m_iIndex;
new_node->m_TData= pNode->m_TData;
//新增节点的父节点
new_node->m_pParent = direction_node;
if (_direction ==0) //如果插入的是左孩子，指针指向如下
{
direction_node->m_pLchild = new_node;
// 程序这里默认，目标节点没有孩子节点，二叉树的构造是从上到下一步一步构造的
//实际上有了删除节点的方法，即使该节点有过孩子节点，只需删除该孩子节点，也不是很麻烦
}
if (_direction ==1) //如果是右孩子，则当前节点指向目标节点
{
direction_node->m_pRchild = new_node;
}
return true;
}
template
bool Tree::DeleteNode(int _index) // 删除节点，这一步应该放在
{
Tree_Node* direction_node = this->searchNode(_index);
if (NULL == direction_node) //如果目标节点为空，那么删除操作也就没有意义了
{
return false;
}
//如果不为空则调用节点对象的删除方法
direction_node->DeleteNode();
return true;
}
template
Tree::~Tree()
{
//树的析构函数执行起来就很简单了，直接对根节点调用deleteNode函数就可以了
this->m_pTree->DeleteNode();
// 或者 DeleteNode(0)
}
template
void Tree::Preorder()
{
//前序遍历
this->m_pTree->Preorder();
}
template
void Tree::Inorder()
{
//中序遍历
this->m_pTree->Inorder();
}
template
void Tree::Postorder()
{
//后续遍历
this->m_pTree->Postorder();
}
#endif
--------------------测试主文件
#include
#include
#include "Tree.h"
using namespace std;
/*
10(0)
9(1) 8(2)
7(3) 6(4) 5(5) 4(6)
*/
int main()
{
Tree* tree =new Tree();
//生成一个树的，默认有一个根节点，根节点不放数据，索引默认为0
Tree_Node* node1 = new Tree_Node();
node1->m_iIndex =1;
node1->m_TData =9;
Tree_Node* node2 = new Tree_Node();
node2->m_iIndex =2;
node2->m_TData =8;
//在根节点下插入1和2号子节点
tree->AddNode(0,0,node1);
tree->AddNode(0,1,node2);
Tree_Node* node3 = new Tree_Node();
node3->m_iIndex =3;
node3->m_TData =7;
Tree_Node* node4 = new Tree_Node();
node4->m_iIndex =4;
node4->m_TData =6;
//在1号节点下插入3和4号子节点
tree->AddNode(1,0,node3);
tree->AddNode(1,1,node4);
Tree_Node* node5 = new Tree_Node();
node5->m_iIndex =5;
node5->m_TData =5;
Tree_Node* node6 = new Tree_Node();
node6->m_iIndex =6;
node6->m_TData =4;
//在2号节点下插入5和6号子节点
tree->AddNode(2,0,node5);
tree->AddNode(2,1,node6);
//前序遍历：0 1 3 4 2 5 6
tree->Preorder();
cout<<"---------------------"< //中序遍历：3 1 4 0 5 2 6
tree->Inorder();
cout<<"---------------------"< //后序遍历：3 4 1 5 2 6 0
tree->Postorder();
cout<<"---------------------"< cout<<*(tree->searchNode(3))< cout<<"---------------------"<
// 删除操作的实现
tree->DeleteNode(2);
tree->Preorder();
system("pause");
return 0;
}
