【数据结构周周练】015 利用递归算法创建链式存储的二叉树并转换左右孩子结点

﹏ヽ暗。殇╰゛Y 2021-06-11 15:13 408阅读 0赞

# 一、前言 #

哈哈，今天就是程序员节啦，祝大家**1024程序员节快乐**。

今天要给大家分享的算法是交换二叉树是的左右孩子结点，比较简单，需要创建一个结点用来暂存左孩子结点，下面给大家送上代码。

# 二、题目 #

将下图用二叉树存入，并交换二叉树是的左右孩子结点。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。

![70][] 不是完全二叉树

![70 1][] 是完全二叉树

#  三、代码 #

#define MAXQUEUESIZE 10
    
    #include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct BiTNode {
    	int data;
    	int number;
    	struct BiTNode *lChild, *rChild, *parent;
    }BiTNode, *BiTree;
    
    int number = 0;
    int yon = 0;
    int yesOrNo[] = { 1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0 };
    int numData[] = { 1,2,4,3,5,7,8,6 };
    
    BiTree treeParent = NULL;
    
    int OperationBiTree(BiTree &T) {
    	T = (BiTree)malloc(sizeof(BiTNode));
    	if (!T)
    	{
    		cout << "空间分配失败(Allocate space failure.)" << endl;
    		exit(OVERFLOW);
    	}
    	T->data = numData[number];
    	T->number = number;
    	number++;
    	T->lChild = NULL;
    	T->rChild = NULL;
    	T->parent = treeParent;
    	return 1;
    }
    
    int RecursionEstablishBiTree(BiTree &T) {
    	OperationBiTree(T);
    	treeParent = T;
    	if (yesOrNo[yon++])
    		RecursionEstablishBiTree(T->lChild);
    	treeParent = T;
    	if (yesOrNo[yon++])
    		RecursionEstablishBiTree(T->rChild);
    
    	return 1;
    }
    
    void VisitBiTree(BiTree &T) {
    	cout << "The number of present node is ：" << T->number << "; ";
    	cout << "   data is ：" << T->data << ";\n ";
    	if (T->lChild)
    		cout << "    has left child and the number is :" << T->lChild->number << ";\n";
    	if (T->rChild)
    		cout << "    has right child,and the number is :" << T->rChild->number << ";\n";
    	cout << endl;
    }
    
    //Visit tree use the preorder technique. 
    void PreOrderVisitBiTree(BiTree T) {
    	if (T)
    	{
    		VisitBiTree(T);
    		PreOrderVisitBiTree(T->lChild);
    		PreOrderVisitBiTree(T->rChild);
    	}
    }
    
    int ExchangeChildNode(BiTree &T) {
    	BiTree p;
    	if (T)
    	{
    		ExchangeChildNode(T->lChild);
    		ExchangeChildNode(T->rChild);
    
    		p = T->lChild;
    		T->lChild = T->rChild;
    		T->rChild = p;
    	}
    	return 1;
    }
    
    void main() {
    	BiTree T;
    	RecursionEstablishBiTree(T);
    
    	cout << "************【Recursion of the binary tree just establish】************\n";
    	PreOrderVisitBiTree(T);
    
    	ExchangeChildNode(T);
    	cout << "*******【Recursion of the binary tree just exchange child node】*******\n";
    	PreOrderVisitBiTree(T);
    
    }

# 四、实现效果 #

创建效果如下，遍历访问测试：

![70 2][] 创建成功的二叉树遍历

![70 3][] 第一棵树

对于第二颗树，只需要修改两个位置，树创建时候的两个数组：

int yesOrNo[] = { 1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0 };
    int numData[] = { 1,2,4,8,9,5,3,6,7 };

结果如下：

![70 4][] 创建成功的二叉树遍历

![70 5][] 第二棵树

[70]: /images/20210516/05442e6ad5f74a5380123873a4b552e5.png
[70 1]: /images/20210516/9cfdacaed5f546fd8dacafe64e4c9825.png
[70 2]: /images/20210516/1e6223d036ee4649816b0d5b09ac1258.png
[70 3]: /images/20210516/fa8857f6e861460ba6378e5cfa8e919b.png
[70 4]: /images/20210516/a388bcf140f1464cbe4626447732080b.png
[70 5]: /images/20210516/02cafb36bb234b01971ffdd5595c4fa7.png