编程实现链式存储结构上交换二叉树中所有结点左右子树的算法
#include <iostream> using namespace std; # define maxSize 10 //树结点的结构体，存储的是int整型的数据 typedef struct BTNode{ int data; struct BTNode *lchild; struct BTNode *rchild; }BTNode; /* 二叉树的层次遍历 目标遍历的二叉树: 1 / \ 2 3 / \ / \ 4 5 6 7 待输出结果为1,2,3,4,5 */ void createBTree(BTNode *&p) { /* 生成这颗树，这里就是直接按照二叉树的样子来逐一生成 p做为根结点(root) */ p = (BTNode*)malloc(sizeof(BTNode)); p->data = 1; BTNode *n2, *n3, *n4, *n5, *n6, *n7;//分别对应存储元素2，3，4，5的4个结点 n2 = (BTNode*)malloc(sizeof(BTNode)); n3 = (BTNode*)malloc(sizeof(BTNode)); n4 = (BTNode*)malloc(sizeof(BTNode)); n5 = (BTNode*)malloc(sizeof(BTNode)); n6 = (BTNode*)malloc(sizeof(BTNode)); n7 = (BTNode*)malloc(sizeof(BTNode)); n2->data = 2; n3->data = 3; n4->data = 4; n5->data = 5; n6->data = 6; n7->data = 7; p->lchild = n2; p->rchild = n3; n2->lchild = n4; n2->rchild = n5; n3->lchild = n6; n3->rchild = n7; n4->lchild = n4->rchild = NULL; n5->lchild = n5->rchild = NULL; n6->lchild = n6->rchild = NULL; n7->lchild = n7->rchild = NULL; } void level(BTNode *p){ /* 二叉树层次遍历算法 建立一个循环队列，先将二叉树头结点入队列，出队列，访问该结点； 如果他有左子树，把他的左子树的根结点入队列， 如果他有右子树，把他的右子树的根结点入队列， 然后出队列，对出队结点访问； */ int front,rear; front = rear = 0; BTNode *que[maxSize]; BTNode *q; if(p != NULL){ rear = (rear + 1) % maxSize; que[rear] = p; //根结点入队 while (front != rear) { front = (front + 1) % maxSize; q = que[front]; //队头结点出队 cout << q->data << endl; if (q->lchild != NULL) { rear = (rear + 1) % maxSize; que[rear] = q->lchild; } if (q->rchild != NULL) { rear = (rear + 1) % maxSize; que[rear] = q->rchild; } } } } void change(BTNode *&p) { //其实需要遍历二叉树的结点 //交换所有节点的左右子树的 if (p == NULL) return; else { BTNode *q = p->rchild; p->rchild = p->lchild; p->lchild = q; } change(p->lchild); change(p->rchild); } int main() { BTNode *p; createBTree(p); cout << "交换前层次遍历" << endl; level(p); cout << "交换后层次遍历" << endl; change(p); level(p); return 0; }