模板类实现二叉树前序、中序、后序遍历

首先我们需要定义节点类以及二叉树类&＃xff1a;

#include
using namespace std;
template class BirnaryTree; //先声明一个类
template
class TreeNode //节点类定义
{
public:TreeNode(){left&＃61;NULL;right&＃61;NULL;}T data; //数据TreeNode *left; //左子节点TreeNode *right; //右子节点
};
template
class BirnaryTree //二叉树类定义
{
public:void PreOrder(); //前序遍历void PreOrder(TreeNode *currentNode);void InOrder(); //中序遍历void InOrder(TreeNode *currentNode);void PostOrder(); //后序遍历void PostOrder(TreeNode *currentNode);
public:TreeNode *root; //二叉树根节点
};1、前序&＃xff08;先序&＃xff09;遍历的递归实现方法

若二叉树非空&＃xff0c;则依次执行如下操作&＃xff1a;

&＃xff08;1&＃xff09;访问根节点

&＃xff08;2&＃xff09;遍历左子树

&＃xff08;3&＃xff09;遍历右子树
程序代码如下&＃xff1a;

template//前序
void BirnaryTree::PreOrder()
{if(root&＃61;&＃61;NULL)return;PreOrder(root);//成员函数调用另外一个成员函数&＃xff0c;将根传入
}
template
void BirnaryTree::PreOrder(TreeNode* currentNode)
{if(currentNode!&＃61;NULL){cout<data;PreOrder(currentNode->left);PreOrder(currentNode->right);}
}

2、中序遍历的递归实现方法

若二叉树非空&＃xff0c;则依次执行如下操作&＃xff1a;

&＃xff08;1&＃xff09;遍历左子树

&＃xff08;2&＃xff09;访问根节点

&＃xff08;3&＃xff09;遍历右子树
程序代码如下&＃xff1a;

template//中序
void BirnaryTree::InOrder()
{if(root&＃61;&＃61;NULL)return;InOrder(root);//成员函数调用另外一个成员函数&＃xff0c;将根传入
}
template
void BirnaryTree::InOrder(TreeNode* currentNode)
{if(currentNode!&＃61;NULL){InOrder(currentNode->left);cout<data;InOrder(currentNode->right);}
}

3、后序遍历的递归实现方法

若二叉树非空&＃xff0c;则依次执行如下操作&＃xff1a;

&＃xff08;1&＃xff09;遍历左子树

&＃xff08;2&＃xff09;遍历右子树

&＃xff08;3&＃xff09;访问根节点
程序代码如下&＃xff1a;

template//后序
void BirnaryTree::PostOrder()
{if(root&＃61;&＃61;NULL)return;PostOrder(root);//成员函数调用另外一个成员函数&＃xff0c;将根传入
}
template
void BirnaryTree::PostOrder(TreeNode* currentNode)
{if(currentNode!&＃61;NULL){PostOrder(currentNode->left);PostOrder(currentNode->right);cout<data;}
}

下面是主函数的测试代码&＃xff1a;

int main()
{BirnaryTree tree;TreeNode add,sub,mul,div,a,b,c,d,e;//通过手动创建了一个二叉树add.data&＃61;&＃39;&＃43;&＃39;;sub.data&＃61;&＃39;-&＃39;;mul.data&＃61;&＃39;*&＃39;;div.data&＃61;&＃39;/&＃39;;a.data&＃61;&＃39;A&＃39;;b.data&＃61;&＃39;B&＃39;;c.data&＃61;&＃39;C&＃39;;d.data&＃61;&＃39;D&＃39;;e.data&＃61;&＃39;E&＃39;;tree.root&＃61;&add;add.left&＃61;⊂add.right&＃61;&e;sub.left&＃61;&mul;sub.right&＃61;&d;mul.left&＃61;÷mul.right&＃61;&c;div.left&＃61;&a;div.right&＃61;&b;cout<<"前序:"<}程序手动创建的二叉树为&＃xff1a;

程序运行结果为&＃xff1a;