一波二叉樹遍歷問題的C++解答實例分享
更新時間：2016年02月15日 16:29:43 作者：Zhang_H
這篇文章主要介紹了一波二叉樹遍歷問題的C++解答實例分享,包括節(jié)點打印和轉(zhuǎn)換為鏡像等問題的解答,需要的朋友可以參考下
題目一：
輸入一顆二元樹，從上往下按層打印樹的每個節(jié)點，同一層按照從左往右的順序打印。
輸入樣例：
8 / / 6 10 / / / / 5 7 9 11
輸出樣例：
復(fù)制代碼 代碼如下:
8 6 10 5 7 9 11
思路分析：
把一顆二叉樹抽象成三個節(jié)點：根節(jié)點、左節(jié)點、右節(jié)點。
先序遍歷即可得到按行輸出的效果。
對于左子樹只要保存其根節(jié)點，既保存了整個左子樹。（右子樹一樣）
對于根節(jié)點之外的兩個子樹來說說，始終是先訪問左子樹的根節(jié)點，再訪問右子樹的根節(jié)點。
因此可以使用隊列存儲。
代碼實現(xiàn)（GCC編譯通過）：
#include "stdio.h"
#include "stdlib.h"
//二叉樹節(jié)點
#define size 7
//二叉樹節(jié)點定義
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;
//循環(huán)結(jié)束為隊列為空
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;
}
//根據(jù)數(shù)組創(chuàng)建二叉排序樹
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;
}
題目二：
輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。
如果是返回 true，否則返回 false。
例如輸入 5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：
8 / \ 6 10 / \ / \ 5 7 9 11
因此返回 true。
如果輸入 7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回 false。
思路：
二叉查找的特征：左子樹的各個值均小于根，右子樹的各個值均大于跟
后序遍歷的特征：最后一個是根，便利順序，左右跟。遞歸
好了，總結(jié)可以得到：
最后一個是根，最開始連續(xù)若干個數(shù)小于根的是左子樹的節(jié)點，之后連續(xù)若干個大于根的是右子樹的節(jié)點（左右子樹都可能為空），然后遞歸描述。
代碼描述如下（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;
}
題目三：
輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。
用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：
8 / \ 6 10 /\ /\ 5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
分析：
遞歸程序設(shè)計比較簡單
訪問一個節(jié)點，只要不為空則交換左右孩子，然后分別對左右子樹遞歸。
非遞歸實質(zhì)是需要我們手動完成壓棧，思想是一致的
代碼如下（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);//遞歸實現(xiàn)函數(shù)聲明
void mirrorIteratively(BTree * root);//非遞歸實現(xiàn)函數(shù)聲明
BTree * CreatTree(int a[],int n);//創(chuàng)建二叉樹（產(chǎn)生二叉排序樹）
void Iorder(BTree * root);//中序遍歷查看結(jié)果
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)//結(jié)束條件
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;
}
}
//產(chǎn)生二叉排序樹
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);
}
}
相關(guān)文章
這篇文章主要為大家介紹了C++ LeetCode300最長遞增子序列示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
C++函數(shù)pyrUp和pyrDown來實現(xiàn)圖像金字塔功能
這篇文章主要介紹了C++函數(shù)pyrUp和pyrDown來實現(xiàn)圖像金字塔功能,如何使用OpenCV函數(shù) pyrUp 和 pyrDown 對圖像進行向上和向下采樣,需要的朋友可以參考下2017-03-03
這篇文章主要介紹了C++中單例的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-09-09
本篇文章是對如何判斷一個整數(shù)的二進制中有多少個1的方法進行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了在while中使用cin>>a?為條件及注意事項說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了C語言lseek()函數(shù)詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
c++中虛函數(shù)和純虛函數(shù)的作用與區(qū)別
這篇文章主要介紹了c++中虛函數(shù)和純虛函數(shù)的作用與區(qū)別,需要的朋友可以參考下2014-07-07
set set是一種關(guān)聯(lián)式容器,下面這篇文章主要給大家介紹了關(guān)于C++中map和set使用的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2023-03-03
Qt中const?QString轉(zhuǎn)換?char?*可能的坑
本文主要介紹了Qt中const?QString轉(zhuǎn)換?char?*可能的坑，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要為大家分享下本人在閱讀《C++ Primer》函數(shù)一章時的讀書總結(jié),需要的朋友可以參考下2014-02-02