C++二叉树左右孩子的交换

川长思鸟来 2022-08-18 03:24 136阅读 0赞

二叉树每个结点实现左右孩子（如果存在）的交换，这个思想大概就是判断一下树的每个结点是否存在左、右结点，若存在，则直接交换位置

核心代码如下：

通过递归遍历或者其他的遍历，在遍历的同时，进行对结点判断，是否存在左孩子和右孩子，若存在（至少一个），则进行交换

void Exchange(BiNode<T>\*t)  
  \{  
    if(t->lchild!=NULL)  
Exchange(t->lchild);  
if(t->rchild!=NULL)  
Exchange(t->rchild);  
BiNode<T>\*pointer;  
pointer=t->lchild;  
t->lchild=t->rchild;  
t->rchild=pointer;  
  \}

完全代码如下：

\#include<string>  
\#include<iostream>  
\#include<stack>  
using namespace std;   
//二叉链表表示二叉树   
template<class T>  
class BiNode    
\{    
public:  
     T data;//节点数据    
     BiNode \* lchild;//左孩子    
     BiNode \* rchild;//右孩子  
     BiNode();  
BiNode(T d)\{ data=d; \}        //new一个结点的时候就给其数据域赋值  
~BiNode()\{\}

//建树  
void createTree(BiNode<T>\* &t, string post,string in) //后序，中序  
\{  
if(post.length()==0)  
\{  
   t=NULL;  
\}  
if(post.length()!=0)  
\{  
  
  
int dex=post.length()-1;   //根结点在后序序列的位置  
    t=new BiNode<T>(post\[dex\]);  //新建一个根结点  
   int index=in.find(post\[dex\]);  //查找根结点在中序序列的位置  
            string  lchild\_in=in.substr(0, index);  
            string  rchild\_in=in.substr(index+1);  
            string  lchild\_post=post.substr(0, index);  
            string  rchild\_post=post.substr(index,rchild\_in.length());   
if(t!=NULL)  
            \{  
createTree(t->lchild,lchild\_post,lchild\_in);  
                createTree(t->rchild,rchild\_post,rchild\_in);  
\}  
\}  
\}  
  void Exchange(BiNode<T>\*t)  
  \{  
    if(t->lchild!=NULL)  
Exchange(t->lchild);  
if(t->rchild!=NULL)  
Exchange(t->rchild);  
BiNode<T>\*pointer;  
pointer=t->lchild;  
t->lchild=t->rchild;  
t->rchild=pointer;  
  \}  
  void inOrder(BiNode<T> \*t)//中序遍历  
\{  
   if(t==NULL)  
\{  
 return ;  
\}  
if(t!=NULL)  
\{  
  inOrder(t->lchild);  
  cout<<t->data;  
  inOrder(t->rchild);  
    
\}  
\}  
\};  
int main()  
\{  
   BiNode<char> \*t=NULL;  
   string post="FGDBHECA";  
   string   in="BFDGACEH";  
   t->createTree(t,post,in);  
   cout<<"交换前的中序遍历: "<<endl;  
   t->inOrder(t);  
   cout<<endl;  
   cout<<"交换后的中序遍历: "<<endl;  
   t->Exchange(t);  
   t->inOrder(t);  
   cout<<endl;  
     
   return 0;  
\}