树左孩子于右孩子交换

心已赠人 2022-09-21 12:00 114阅读 0赞

8                      8
          /   \       转换       /   \
         6     10     -->      10    6
        /  \   / \            /  \   / \
       5    7 9   11         11   9 7   5

#include <iostream>
    using namespace std;
    
    
    struct BsTreeNode
    {
    	int m_lvaue;
    	BsTreeNode *m_left;
    	BsTreeNode *m_right;
    };
    
    void Createbitree(BsTreeNode * &node,int * &arr)
    {
    	int det=*arr;
    	arr++;
    	if (det == 0)
    	{
    		node = NULL;
    	}
    	else
    	{
    		node = new BsTreeNode;
    		node->m_lvaue = det;
    		Createbitree(node->m_left, arr);
    		Createbitree(node->m_right, arr);
    	}
    }
    void PreRecurTraversal(BsTreeNode *node)
    {
    	if (node)
    	{
    		cout << node->m_lvaue<<" ";
    		PreRecurTraversal(node->m_left);
    		PreRecurTraversal(node->m_right);
    	}
    
    }
    void MidRecurTraverrsal(BsTreeNode *node)
    {
    	if (NULL != node)
    	{
    		MidRecurTraverrsal(node->m_left);
    		cout << node->m_lvaue<<"  ";
    		MidRecurTraverrsal(node->m_right);
    	}
    
    }
    void RecursionConversion(BsTreeNode *&node)
    {
    	if (NULL == node)
    	{
    		return;
    	}
    	BsTreeNode *pTmp = node->m_left;
    	node->m_left = node->m_right;
    	node->m_right = pTmp;
    	if (NULL != node->m_left)
    		RecursionConversion(node->m_left);
    	if (NULL != node->m_right)
    	{
    		RecursionConversion(node->m_right);
    	}
    }
    void main()
    {
    	int arr[] = { 8 ,6 ,5 ,0, 0, 7, 0, 0, 10, 9, 0, 0, 11, 0, 0 };
    	int *ptr = arr;
    	BsTreeNode *pRoot=NULL;
    	BsTreeNode *pTall=NULL;
    	Createbitree(pRoot,ptr);
    	cout << "**********转转前的前序和中序遍历***********" << endl;
    	cout << "前序遍历  ";
    	PreRecurTraversal(pRoot);
    
    
    	RecursionConversion(pRoot);
    
    	cout << "转换后的便利" << endl;
    	
    	PreRecurTraversal(pRoot);
    
    
    
    	system("pause");
    }