一波二叉樹遍歷成績的C++解答實例分享

一波二叉樹遍歷成績的C++解答實例分享。本站提示廣大學習愛好者：（一波二叉樹遍歷成績的C++解答實例分享）文章只能為提供參考，不一定能成為您想要的結果。以下是一波二叉樹遍歷成績的C++解答實例分享正文

標題一：

  輸出一顆二元樹，從上往下按層打印樹的每一個節點，統一層依照從左往右的次序打印。

輸出樣例：

 8

 / /

 6 10

/ / / /

5 7 9 11

輸入樣例：

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);
  }
}