一波二叉树遍历问题的C++解答实例分享

2020-01-26 14:43:33

字体：大中小

来源：转载

供稿：网友

题目一：

输入一颗二元树，从上往下按层打印树的每个节点，同一层按照从左往右的顺序打印。

输入样例：

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

上一篇：使用C++递归求解跳台阶问题

下一篇：C++求1到n中1出现的次数以及数的二进制表示中1的个数