C++ 二叉树创建、遍历访问、删除

Love The Way You Lie 2022-06-12 02:23 97阅读 0赞

**代码包含：二叉树数组创建（前序）、前序、中序、后序遍历、节点访问、删除  
  
代码说明：该代码使用模板建立，一些地方并未完善，比如array\[index\]==-1，仅仅使用于数字类型，如果二叉树存储的是char或string，需在这之前判断类型，给予特定的空标识，对于节点的访问，使用一个函数指针传递对节点的操作，删除只能使用后序遍历的方式  
  
\#include<iostream>  
using namespace std;  
  
template <typename T>  
struct Node\{  
T data;  
Node<T>\* left;  
Node<T>\* right;  
\};  
  
  
template <typename T>  
void Create(Node<T>\*& node,T array\[\],int& index,int& length)\{  
if(index>=length||array\[index\]==-1)\{  
node=0;  
\}  
else\{  
node=new Node<T>();  
node->data=array\[index\];  
Create(node->left,array,++index,length);  
Create(node->right,array,++index,length);  
\}  
\}  
  
template <typename T>  
void PreOrderTraversal(Node<T>\*& node,void(\*func)(Node<T>\*& arg))\{  
if(node!=0)\{  
if(func!=0)\{  
func(node);  
\}  
PreOrderTraversal(node->left,func);  
PreOrderTraversal(node->right,func);  
\}  
\}  
  
  
template <typename T>  
void InOrderTraversal(Node<T>\*& node,void(\*func)(Node<T>\*& arg))\{  
if(node!=0)\{  
InOrderTraversal(node->left,func);  
if(func!=0)\{  
func(node);  
\}  
InOrderTraversal(node->right,func);  
\}  
\}  
  
template <typename T>  
void PostOrderTraversal(Node<T>\*& node,void(\*func)(Node<T>\*& arg))\{  
if(node!=0)\{  
PostOrderTraversal(node->left,func);  
PostOrderTraversal(node->right,func);  
if(func!=0)\{  
func(node);  
\}  
\}  
\}  
  
  
template <typename T>  
void Delete(Node<T>\*& node)\{  
delete node;  
\}  
  
template <typename T>  
void Show(Node<T>\*& node)\{  
cout<<node->data<<endl;  
\}  
/\*  
1  
2 5  
3 4 6  
\*/  
  
int main()\{  
void(\*Delegate)(Node<int>\*& arg);  
Delegate=0;  
int array\[\]=\{  
1,2,3,-1,-1,4,-1,-1,5,6,-1,-1,-1  
\};  
  
Node<int>\* tree;  
int index=0;  
int length=sizeof(array)/sizeof(array\[0\]);  
Create(tree,array,index,length);  
  
Delegate=Show;  
InOrderTraversal(tree,Delegate);  
  
  
Delegate=Delete;  
PostOrderTraversal(tree,Delegate);  
return 0;  
\}**