服务器之家

服务器之家 > 正文

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

时间:2021-03-25 11:24     来源/作者:Zhang_H

题目一:

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

输入样例:

?
1
2
3
4
5
6
7
8
9
8
 
 / /
 
 6 10
 
/ / / /
 
5 7 9 11

输出样例:

 

复制代码 代码如下:
8 6 10 5 7 9 11

 

思路分析:

    把一颗二叉树抽象成三个节点:根节点、左节点、右节点。

    先序遍历即可得到按行输出的效果。

    对于左子树只要保存其根节点,既保存了整个左子树。(右子树一样)

    对于根节点之外的两个子树来说说,始终是先访问左子树的根节点,再访问右子树的根节点。

    因此可以使用队列存储。

代码实现(GCC编译通过):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#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,由于这一整数序列是如下树的后序遍历结果:

?
1
2
3
4
5
6
7
8
9
8
 
/  \
 
6  10
 
/  \  /  \
 
5  7  9  11

因此返回 true。

如果输入 7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false。

思路:

二叉查找的特征:左子树的各个值均小于根,右子树的各个值均大于跟

后序遍历的特征:最后一个是根,便利顺序,左右跟。递归

好了,总结可以得到:

最后一个是根,最开始连续若干个数小于根的是左子树的节点,之后连续若干个大于根的是右子树的节点(左右子树都可能为空),然后递归描述。

代码描述如下(GCC编译通过):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
   
   
}

题目三:

输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入:

?
1
2
3
4
5
8
/ \
6 10
/\ /\
5 7 9 11

输出:

?
1
2
3
4
5
    8
  /     \
  10     6
  /\       /\
11   9   7   5

分析:

递归程序设计比较简单

    访问一个节点,只要不为空则交换左右孩子,然后分别对左右子树递归。

非递归实质是需要我们手动完成压栈,思想是一致的

代码如下(GCC编译通过):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#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);
  }
}

 

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部