快捷導(dǎo)航

一波二叉樹遍歷問題的C++解答實(shí)例分享

更新時(shí)間：2016年02月15日 16:29:43 作者：Zhang_H

這篇文章主要介紹了一波二叉樹遍歷問題的C++解答實(shí)例分享,包括節(jié)點(diǎn)打印和轉(zhuǎn)換為鏡像等問題的解答,需要的朋友可以參考下

題目一：

輸入一顆二元樹，從上往下按層打印樹的每個節(jié)點(diǎn)，同一層按照從左往右的順序打印。

輸入樣例：

輸出樣例：

復(fù)制代碼代碼如下:

8 6 10 5 7 9 11

思路分析：

把一顆二叉樹抽象成三個節(jié)點(diǎn)：根節(jié)點(diǎn)、左節(jié)點(diǎn)、右節(jié)點(diǎn)。

先序遍歷即可得到按行輸出的效果。

對于左子樹只要保存其根節(jié)點(diǎn)，既保存了整個左子樹。（右子樹一樣）

對于根節(jié)點(diǎn)之外的兩個子樹來說說，始終是先訪問左子樹的根節(jié)點(diǎn)，再訪問右子樹的根節(jié)點(diǎn)。

因此可以使用隊(duì)列存儲。

代碼實(shí)現(xiàn)（GCC編譯通過）：

#include "stdio.h"
#include "stdlib.h"
 
//二叉樹節(jié)點(diǎn)
#define size 7
 
//二叉樹節(jié)點(diǎn)定義
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é)束為隊(duì)列為空
  while(front != rear)
  {    
      //根出隊(duì)列
    front = (front +1)%size;
    p = queue[front];
    printf("%3d",p->data);
 
    //左孩子不空，隊(duì)不滿入隊(duì)
    if(p->left && ((rear+1)%size != front))
    {
      rear = (rear+1)%size;
      queue[rear] = p->left;
    }
         
        //右孩子不空，隊(duì)不滿入隊(duì)
    if(p->right && ((rear+1)%size != front))
    {
      rear = (rear+1)%size;
      queue[rear] = p->right;
    }
         
        //隊(duì)滿，報(bào)錯
    if((rear+1)%size == front)
    {
      printf("隊(duì)列空間不足，錯誤....\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é)點(diǎn)，之后連續(xù)若干個大于根的是右子樹的節(jié)點(diǎn)（左右子樹都可能為空），然后遞歸描述。

代碼描述如下（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é)點(diǎn)都大于右子樹的結(jié)點(diǎn)。
用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：

8
/ \
6 10
/\ /\
5 7 9 11

輸出：

    8
  /     \
  10     6
  /\       /\
11   9   7   5

分析：

遞歸程序設(shè)計(jì)比較簡單

訪問一個節(jié)點(diǎn)，只要不為空則交換左右孩子，然后分別對左右子樹遞歸。

非遞歸實(shí)質(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);//遞歸實(shí)現(xiàn)函數(shù)聲明
void mirrorIteratively(BTree * root);//非遞歸實(shí)現(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);
  }
}

您可能感興趣的文章: