C++数据结构--二叉树的复制和删除

矫情吗；* 2021-11-26 23:56 128阅读 0赞

**本示例所用到的二叉树：  
![20130801083400015][]  
  
  
template<typename T>  
class node  
\{  
public:  
T val; //节点值  
 node<T>\* left; //左节点   
 node<T>\* right; //右节点  
  
 node():val(T()),left(nullptr),right(nullptr)\{\}  
 node(T v, node<T>\* l=nullptr, node<T>\* r=nullptr):val(v),left(l),right(r)\{\}  
\};  
  
  
  
  
  
  
node<char>\* createBTree()  //构建一棵示例二叉树   
 \{   
node<char>\* g=new node<char>('G');  
node<char>\* e=new node<char>('E');  
node<char>\* f=new node<char>('F');  
node<char>\* d=new node<char>('D',nullptr,g);  
node<char>\* c=new node<char>('C',nullptr,f);  
node<char>\* b=new node<char>('B',d,e);  
node<char>\* a=new node<char>('A',b,c);  
  
return a;  
  
 \}**

**//采用后序遍历方式复制二叉树**

**node<char> \* copy(node<char> \*root)  
\{   
node<char> \*newRoot=nullptr; //新的根节点   
node<char> \*newLeft=nullptr; //新的左子树节点  
node<char> \*newRight=nullptr; //新的右子树节点   
  
if(!root)  
\{   
return nullptr;  
\}   
else  
\{   
newLeft=copy(root->left); //复制左子树   
newRight=copy(root->right); //复制右子树   
newRoot=new node<char>(root->val,newLeft,newRight); //新建一个根节点把左子树和右子树连接起来   
\}  
  
return newRoot;  
\}**

**//采用后序遍历方式删除二叉树**

**void destroy(node<char> \*root)  
\{   
if(!root)  
\{   
return;  
\}  
else  
\{   
destroy(root->left); //删除左子树  
destroy(root->right); //删除右子树  
delete root;  
\}  
\}**

**//后序遍历二叉树**

**void postTravel(node<char>\* root)  
 \{   
 if(!root)  
 \{   
return;  
 \}  
 else  
 \{   
postTravel(root->left);  
postTravel(root->right);  
cout<<root->val<<ends;  
 \}  
 \}   
  
int main()  
\{   
 node<char>\* root=createBTree();  
 node<char>\* newRoot=copy(root);  
 postTravel(newRoot);  
 destroy(newRoot);  
  
return 0;  
\}  
  
  
  
  
output:  
G D E B F C A**

[20130801083400015]: /images/20211126/dd351c12608d4c4a86852ed718a42035.png