這本是個簡單問題，但網上卻沒有個統一的說法

C++語言: Codee#22991 #include <stdio.h>
#include <malloc.h>

typedef struct node
{
??? char data;
??? struct node *lchild;
??? struct node *rchild;
} BTNode;
void CreateBTNode(BTNode * &b, char *str)
{
??? BTNode *St[10086], *p = NULL;
??? int top = -1, k, j = 0;
??? char ch;
??? b = NULL;
??? ch = str[j];
??? while (ch != '\0')
??? {
??????? switch(ch)
??????? {
??????? case '(':
??????????? top++;
??????????? St[top] = p;
??????????? k = 1;
??????????? break;
??????? case ')':
??????????? top--;
??????????? break;
??????? case ',':
??????????? k = 2;
??????????? break;
??????? default:
??????????? p = (BTNode *)malloc(sizeof(BTNode));
??????????? p->data = ch;
??????????? p->lchild = p->rchild = NULL;
??????????? if (b == NULL)
??????????????? b = p;
??????????? else
??????????? {
??????????????? switch(k)
??????????????? {
??????????????? case 1:
??????????????????? St[top]->lchild = p;
??????????????????? break;
??????????????? case 2:
??????????????????? St[top]->rchild = p;
??????????????????? break;
??????????????? }
??????????? }
??????? }
??????? j++;
??????? ch = str[j];
??? }
}

void DispBTNode(BTNode *b, int dep)
{
??? if (b != NULL)
??? {
??????? DispBTNode(b->lchild, dep + 2);
??????? printf("%.*s%c\n",? dep, "???????????????? ", b->data);
??????? DispBTNode(b->rchild, dep + 2);
??? }
}
void exch_pre(BTNode* b)
{
??? BTNode* tmp;
??? if(b)
??? {
??????? tmp = b->lchild;
??????? b->lchild = b->rchild;
??????? b->rchild = tmp;
??????? exch_pre(b->lchild);
??????? exch_pre(b->rchild);
??? }
}

void exch_in(BTNode* b)
{
??? BTNode* tmp;
??? if(b)
??? {
??????? exch_pre(b->lchild);
??????? tmp = b->lchild;
??????? b->lchild = b->rchild;
??????? b->rchild = tmp;
??????? exch_pre(b->lchild);???? //!!!!!!!
??? }
}

void exch_post(BTNode* b)
{
??? BTNode* tmp;
??? if(b)
??? {
??????? exch_pre(b->lchild);
??????? exch_pre(b->rchild);
??????? tmp = b->lchild;
??????? b->lchild = b->rchild;
??????? b->rchild = tmp;
??? }
}
void exch_lv(BTNode* b)
{
??? BTNode* tmp_q[10086];
??? BTNode* ptr;
??? BTNode* t;
??? int front, rear;
??? front = rear = 0;
??? tmp_q[++rear] = b;
??? while(front < rear)
??? {
??????? ptr = tmp_q[++front];
??????? t = ptr->lchild;
??????? ptr->lchild = ptr->rchild;
??????? ptr->rchild = t;
??????? if(ptr->lchild)
??????????? tmp_q[++rear] = ptr->lchild;
??????? if(ptr->rchild)
??????????? tmp_q[++rear] = ptr->rchild;
??? }
}




int main()
{
??? BTNode *b;
??? CreateBTNode(b, "A(B(D,E),C(,F))");
??? printf("每次都是在上次交換的基礎上再交換\n");
??? printf("0.初始狀態\n");
??? DispBTNode(b, 0);
??? puts("\n______________________________\n");

??? exch_pre(b);
??? printf("1.先序交換\n");
??? DispBTNode(b, 0);
??? puts("\n______________________________\n");

??? exch_in(b);
??? printf("2.中序交換\n");
??? DispBTNode(b, 0);
??? puts("\n______________________________\n");

??? exch_post(b);
??? printf("3.后序交換\n");
??? DispBTNode(b, 0);
??? puts("\n______________________________\n");

??? exch_lv(b);
??? printf("4.層次交換\n");
??? DispBTNode(b, 0);
??? puts("\n______________________________\n");

??? return 0;
}

轉載于:https://www.cnblogs.com/invisible/archive/2011/10/06/2200117.html

總結

以上是生活随笔為你收集整理的二叉树的左右子树交换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。