題目一：
輸入一顆二元樹，從上往下按層打印樹的每個節點，同一層按照從左往右的順序打印。
輸入樣例：
8 / / 6 10/ / / /5 7 9 11
輸出樣例：
思路分析：
把一顆二叉樹抽象成三個節點：根節點、左節點、右節點。
先序遍歷即可得到按行輸出的效果。
對于左子樹只要保存其根節點，既保存了整個左子樹。（右子樹一樣）
對于根節點之外的兩個子樹來說說，始終是先訪問左子樹的根節點，再訪問右子樹的根節點。
因此可以使用隊列存儲。
代碼實現（GCC編譯通過）：
#include "stdio.h"#include "stdlib.h" //二叉樹節點#define size 7 //二叉樹節點定義typedef struct node{ int data; struct node *left; struct node *right;}BTree; int printLine(BTree * root);BTree * CreatTree(int a[],int n); int main(void){ int array[size] = {8,6,10,5,7,9,11}; BTree * root; root = CreatTree(array,size); printLine(root); printf("/n"); return 0;} int printLine(BTree * root){ BTree * queue[size], *p; int front,rear; front = rear = 0; rear = (rear+1)%size; queue[rear] = root; //循環結束為隊列為空 while(front != rear) { //根出隊列 front = (front +1)%size; p = queue[front]; printf("%3d",p->data); //左孩子不空，隊不滿入隊 if(p->left && ((rear+1)%size != front)) { rear = (rear+1)%size; queue[rear] = p->left; } //右孩子不空，隊不滿入隊 if(p->right && ((rear+1)%size != front)) { rear = (rear+1)%size; queue[rear] = p->right; } //隊滿，報錯 if((rear+1)%size == front) { printf("隊列空間不足，錯誤..../n"); return 0; } } return 1;} //根據數組創建二叉排序樹BTree * CreatTree(int a[],int n){ BTree * root ,*p,*cu,*pa; int i; root = (BTree *)malloc(sizeof(BTree)); root->data = a[0]; root->left = root->right =NULL; for(i=1;i<n;i++) { p = (BTree *)malloc(sizeof(BTree)); p->data = a[i]; p->left = p->right =NULL; cu = root; while(cu) { pa = cu; if(cu->data > p->data) cu = cu->left; else cu = cu->right; } if(pa->data > p->data) pa->left = p; else pa->right = p; } return root;}題目二：
輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。
如果是返回 true，否則返回 false。
例如輸入 5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果：
8/ /6 10/ / / /5 7 9 11
因此返回 true。
如果輸入 7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回 false。
思路：
二叉查找的特征：左子樹的各個值均小于根，右子樹的各個值均大于跟
后序遍歷的特征：最后一個是根，便利順序，左右跟。遞歸
好了，總結可以得到：
最后一個是根，最開始連續若干個數小于根的是左子樹的節點，之后連續若干個大于根的是右子樹的節點（左右子樹都可能為空），然后遞歸描述。
代碼描述如下（GCC編譯通過）：
#include "stdio.h"#include "stdlib.h" int isPostorderResult(int a[],int n);int helper(int a[],int s,int e); int main(void){ int a[7] = {5,7,6,9,11,10,8}; int b[4] = {7,4,6,5}; int tmp; tmp = isPostorderResult(a,7); printf("%d",tmp); return 0;} int isPostorderResult(int a[],int n){ return helper(a,0,n-1);} int helper(int a[],int s,int e){ int i,j,root; if(s == e) return 1; for(i=0;i<e && a[i]<a[e];i++); if(i != 0 && helper(a,s,i-1) == 0) return 0; for(j=i;j<e && a[j]>a[e];j++); if(j==e && helper(a,i,j-1) == 1) return 1; else return 0; }題目三：
輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。
用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
8/ /6 10// //5 7 9 11
輸出：
8 / / 10 6 // //11 9 7 5
分析：
遞歸程序設計比較簡單
訪問一個節點，只要不為空則交換左右孩子，然后分別對左右子樹遞歸。
非遞歸實質是需要我們手動完成壓棧，思想是一致的
代碼如下（GCC編譯通過）：
#include "stdio.h"#include "stdlib.h" #define MAXSIZE 8 typedef struct node{ int data; struct node * left; struct node * right;}BTree; void swap(BTree ** x,BTree ** y);//交換左右孩子void mirror(BTree * root);//遞歸實現函數聲明void mirrorIteratively(BTree * root);//非遞歸實現函數聲明BTree * CreatTree(int a[],int n);//創建二叉樹（產生二叉排序樹）void Iorder(BTree * root);//中序遍歷查看結果 int main(void){ int array[MAXSIZE] = {5,3,8,7,2,4,1,9}; BTree * root; root = CreatTree(array,MAXSIZE); printf("變換前：/n"); Iorder(root); printf("/n變換后：/n");//兩次變換，與變化前一致 mirror(root); mirrorIteratively(root); Iorder(root); printf("/n"); return 0;} void swap(BTree ** x,BTree ** y){ BTree * t = * x; * x = * y; * y = t;} void mirror(BTree * root){ if(root == NULL)//結束條件 return; swap(&(root->left),&(root->right));//交換 mirror(root->left);//左子樹遞歸 mirror(root->right);//右子樹遞歸} void mirrorIteratively(BTree * root){ int top = 0; BTree * t; BTree * stack[MAXSIZE+1]; if(root == NULL) return; //手動壓棧、彈棧 stack[top++] = root; while(top != 0) { t = stack[--top]; swap(&(t->left),&(t->right)); if(t->left != NULL) stack[top++] = t->left; if(t->right != NULL) stack[top++] = t->right; }} //產生二叉排序樹BTree * CreatTree(int a[],int n){ BTree * root ,*p,*cu,*pa; int i; root = (BTree *)malloc(sizeof(BTree)); root->data = a[0]; root->left = root->right =NULL; for(i=1;i<n;i++) { p = (BTree *)malloc(sizeof(BTree)); p->data = a[i]; p->left = p->right =NULL; cu = root; while(cu) { pa = cu; if(cu->data > p->data) cu = cu->left; else cu = cu->right; } if(pa->data > p->data) pa->left = p; else pa->right = p; } return root;}//中序遍歷void Iorder(BTree * root){ if(root) { Iorder(root->left); printf("%3d",root->data); Iorder(root->right); }}新聞熱點
疑難解答
圖片精選
