devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的存储结构和二叉树的遍历方法以及实现代码_用c语言实现二叉树的三种遍历方式

作者：IT小白 | 2024-06-16 15:20:20

赞

踩

用c语言实现二叉树的三种遍历方式

文章目录

一、二叉树的顺序存储

在这里插入图片描述
在这里插入图片描述
如果二叉树如下图中所示，补全节点使其成为完全二叉树的方法太浪费空间；
在这里插入图片描述

二、二叉树的链式存储

在这里插入图片描述

三、二叉树的遍历

遍历二叉树是将树中的结点按一定规律排列成一个线性序列，即是对非线性结构线性化的操作。
使得每个结点在这些线性序列中有且仅有一个直接前驱和一个直接后继。

1.二叉树的层次遍历

在这里插入图片描述

在这里插入图片描述
实现层次遍历代码如下：

/*
 * 程序名：btree1.c，此程序演示二叉树的层次遍历。
 * 作者：C语言技术网(www.freecplus.net) 日期：20200202
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

///
// 二叉树的数据结构。
typedef struct BiTNode
{
  char   data;               // 存放结点的数据元素。
  struct BiTNode *lchild;    // 指向左子结点地址的指针。
  struct BiTNode *rchild;    // 指向右子结点地址的指针。
}BiTNode,*BiTree;
///


///
// 队列的数据结构。
#define MAXSIZE 30       // 循环队列的最大长度，最多可以存放MAXSIZE-1个元素。

typedef BiTree ElemType;     // 自定义队列的数据元素为二叉树。

typedef struct
{
  ElemType data[MAXSIZE];   // 用数组存储循环队列中的元素。
  int front;                // 队列的头指针。
  int rear;                 // 队列的尾指针，指向队尾的下一个元素。
}SeqQueue,*PSeqQueue;
///

///
// 队列操作的函数。

// 循环队列QQ的初始化操作。
void InitQueue(PSeqQueue QQ);

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee);

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee);

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ);

// 清空循环队列。
void Clear(PSeqQueue QQ);

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ);

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ);
///


// 二叉树的层次遍历。
void LevelOrder(BiTree TT);

int main()
{
  BiTree TT=0; // 声明树指针变量。

  /*
  // 手工构造一个如下结构的二叉树。
             1
          /     \
         2       3
        / \     /
       4   5   6
      / \ / \
     7  8 9  0
  */

  // 分配根节点。
  TT=(BiTNode *)malloc(sizeof(BiTNode));
  TT->data='1';
  TT->lchild=TT->rchild=0;

  // 第二层第一个节点。
  TT->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->data='2'; TT->lchild->lchild=TT->lchild->rchild=0;

  // 第二层第二个节点。
  TT->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->rchild->data='3'; TT->rchild->lchild=TT->rchild->rchild=0;

  // 第三层第一个节点。
  TT->lchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->lchild->data='4'; TT->lchild->lchild->lchild=TT->lchild->lchild->rchild=0;

  // 第三层第二个节点。
  TT->lchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->rchild->data='5'; TT->lchild->rchild->lchild=TT->lchild->rchild->rchild=0;

  // 第三层第三个节点。
  TT->rchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->rchild->lchild->data='6'; TT->rchild->lchild->lchild=TT->rchild->lchild->rchild=0;

  // 第四层第一个节点。
  TT->lchild->lchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->lchild->lchild->data='7'; TT->lchild->lchild->lchild->lchild=TT->lchild->lchild->lchild->rchild=0;

  // 第四层第二个节点。
  TT->lchild->lchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->lchild->rchild->data='8'; TT->lchild->lchild->rchild->lchild=TT->lchild->lchild->rchild->rchild=0;

  // 第四层第三个节点。
  TT->lchild->rchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->rchild->lchild->data='9'; TT->lchild->rchild->lchild->lchild=TT->lchild->rchild->lchild->rchild=0;

  // 第四层第四个节点。
  TT->lchild->rchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->rchild->rchild->data='0'; TT->lchild->rchild->rchild->lchild=TT->lchild->rchild->rchild->rchild=0;

  // 二叉树层次遍历。
  printf("层次遍历结果："); LevelOrder(TT); printf("\n");

  return 0;
}

// 访问出队元素。
void visit(BiTNode *pp)
{
  printf("%c ",pp->data);  // 访问出队元素就是把值输出来，意思一下就行了。
}

// 二叉树层次遍历。
void LevelOrder(BiTree TT)
{
  SeqQueue QQ;     // 创建循环队列。

  InitQueue(&QQ);  // 初始化循环队列。

  ElemType ee=TT;  // 队列的元素是二叉树。
   
  InQueue(&QQ,&ee);  // 把根结点当成队列的元素入队。
  
  while (IsEmpty(&QQ)!=1)  // 队列不为空。
  {
    OutQueue(&QQ,&ee);  // 队头元素出队。

    visit(ee);  // 访问出队元素。
 
    if (ee->lchild != NULL) InQueue(&QQ,&ee->lchild);  // 如果出队元素有左结点，左结点入队。

    if (ee->rchild != NULL) InQueue(&QQ,&ee->rchild);  // 如果出队元素有右结点，右结点入队。
  }
}

// 初始化循环队列
void InitQueue(PSeqQueue QQ)
{
  Clear(QQ); // 清空循环队列。
}

// 清空循环队列。
void Clear(PSeqQueue QQ)
{
  if (QQ == NULL) return;  // 检查空指针。

  QQ->front=QQ->rear=0;
  memset(QQ->data,0,sizeof(ElemType)*MAXSIZE);  // 数组元素清零。
}

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int Length(PSeqQueue QQ)
{
  if (QQ == NULL) return 0;  // 检查空指针。

  return (QQ->rear-QQ->front+MAXSIZE)%MAXSIZE;
}

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqQueue QQ)
{
  if (QQ == NULL) return 0;    // 检查空指针。

  if (QQ->front == QQ->rear) return 1;

  return 0;
}

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ)
{
  if (QQ == NULL) return 0;   // 检查空指针。

  if ( ((QQ->rear+1)%MAXSIZE) == QQ->front) return 1;

  return 0;
}

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee)
{
  if ( (QQ == NULL) || (ee == NULL) ) return 0;   // 检查空指针。

  if (IsFull(QQ) == 1)
  {
    printf("循环队列已满，不能插入。\n"); return 0;
  }

  memcpy(&QQ->data[QQ->rear],ee,sizeof(ElemType));  // 用数组的下标访问。
  // memcpy(QQ->data+QQ->rear,ee,sizeof(ElemType));    // 采用指针运算也可以。

  QQ->rear=(QQ->rear+1)%MAXSIZE;  // 队尾指针后移。

  return 1;
}

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee)
{
  if ( (QQ == NULL) || (ee == NULL) ) return 0;   // 检查空指针。

  if (IsEmpty(QQ) == 1) { printf("队列为空。\n"); return 0; }

  memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));  // 用数组的下标访问。
  // memcpy(ee,QQ->data+QQ->front,sizeof(ElemType));    // 采用指针运算也可以。

  QQ->front=(QQ->front+1)%MAXSIZE;  // 队列头指针后移。

  return 1;
}



  • 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
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230

2. 二叉树的三种基本遍历方法

在这里插入图片描述

1、先序遍历 ：

先看动图看遍历步骤，再看实例；
在这里插入图片描述下图中的左右 要理解为树木，不要片面的理解成节点；
在这里插入图片描述

2、中序遍历：

在这里插入图片描述

在这里插入图片描述

3、后序遍历

在这里插入图片描述
在这里插入图片描述

3.二叉树遍历的代码实现

1.递归方案实现遍历：

1.先序递归：

在这里插入图片描述

2.中序递归：

在这里插入图片描述

1.后序递归：

在这里插入图片描述
三种方法的区别只是visit()代码的位置不同而已；

2、代码实现：

/*
 * 程序名：btree2.c，此程序演示二叉树的前序遍历、中序遍历和后序遍历，包括递归和非递归两种方法。
 * 作者：C语言技术网(www.freecplus.net) 日期：20200202
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

///
// 二叉树的数据结构。
typedef struct BiTNode
{
  char   data;               // 存放结点的数据元素。
  struct BiTNode *lchild;    // 指向左子结点地址的指针。
  struct BiTNode *rchild;    // 指向右子结点地址的指针。
}BiTNode,*BiTree;
///



// 栈的数据结构。
#define MAXSIZE 30       // 顺序栈的最大长度。

typedef BiTree ElemType;     // 自定义栈的数据元素为二叉树。

typedef struct
{
  ElemType data[MAXSIZE];   // 用数组存储顺序栈中的元素。
  int top;                  // 栈顶指针，从0到MAXSIZE-1，-1表示空栈。
                            // 也可以从1到MAXSIZE，0表示空栈。
}SeqStack,*PSeqStack;



// 顺序栈SS的初始化操作。
void InitStack(PSeqStack SS);                     

// 元素入栈，返回值：0-失败；1-成功。
int Push(PSeqStack SS, ElemType *ee);

// 元素出栈，返回值：0-失败；1-成功。
int Pop(PSeqStack SS, ElemType *ee);

// 求顺序栈的长度，返回值：栈SS中元素的个数。
int Length(PSeqStack SS);                   

// 清空顺序栈。
void Clear(PSeqStack SS);                    

// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqStack SS);                    

// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqStack SS);

// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS);                    

// 获取栈顶元素，返回值：0-失败；1-成功。
// 只查看栈顶元素的值，元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee);


// 求二叉树的高度。
int TreeDepth(BiTree TT);

// 访问结点元素。
void visit(BiTNode *pp);

// 采用递归的方法对二叉树的先序遍历。
void PreOrder(BiTree TT);
// 不采用递归的方法对二叉树的先序遍历。
void PreOrder1(BiTree TT);

// 采用递归的方法对二叉树的中序遍历。
void InOrder(BiTree TT);
// 不采用递归的方法对二叉树的中序遍历。
void InOrder1(BiTree TT);

// 采用递归的方法对二叉树的后序遍历。
void PostOrder(BiTree TT);
// 不采用递归的方法对二叉树的后序遍历。
void PostOrder1(BiTree TT);

int main()
{
  BiTree TT=0; // 声明树指针变量。

  /*
  // 手工构造一个如下结构的二叉树。
             1
          /     \
         2       3
        / \     /
       4   5   6
      / \ / \
     7  8 9  0
  */

  // 分配根节点。
  TT=(BiTNode *)malloc(sizeof(BiTNode));
  TT->data='1';
  TT->lchild=TT->rchild=0;

  // 第二层第一个节点。
  TT->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->data='2'; TT->lchild->lchild=TT->lchild->rchild=0;

  // 第二层第二个节点。
  TT->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->rchild->data='3'; TT->rchild->lchild=TT->rchild->rchild=0;

  // 第三层第一个节点。
  TT->lchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->lchild->data='4'; TT->lchild->lchild->lchild=TT->lchild->lchild->rchild=0;

  // 第三层第二个节点。
  TT->lchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->rchild->data='5'; TT->lchild->rchild->lchild=TT->lchild->rchild->rchild=0;

  // 第三层第三个节点。
  TT->rchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->rchild->lchild->data='6'; TT->rchild->lchild->lchild=TT->rchild->lchild->rchild=0;

  // 第四层第一个节点。
  TT->lchild->lchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->lchild->lchild->data='7'; TT->lchild->lchild->lchild->lchild=TT->lchild->lchild->lchild->rchild=0;

  // 第四层第二个节点。
  TT->lchild->lchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->lchild->rchild->data='8'; TT->lchild->lchild->rchild->lchild=TT->lchild->lchild->rchild->rchild=0;

  // 第四层第三个节点。
  TT->lchild->rchild->lchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->rchild->lchild->data='9'; TT->lchild->rchild->lchild->lchild=TT->lchild->rchild->lchild->rchild=0;

  // 第四层第四个节点。
  TT->lchild->rchild->rchild=(BiTNode *)malloc(sizeof(BiTNode));
  TT->lchild->rchild->rchild->data='0'; TT->lchild->rchild->rchild->lchild=TT->lchild->rchild->rchild->rchild=0;

  // 二叉树的先序遍历。
  printf("先序遍历结果1："); PreOrder(TT); printf("\n");
  printf("先序遍历结果2："); PreOrder1(TT); printf("\n");

  // 二叉树的中序遍历。
  printf("中序遍历结果1："); InOrder(TT); printf("\n");
  printf("中序遍历结果2："); InOrder1(TT); printf("\n");

  // 二叉树的后序遍历。
  printf("后序遍历结果1："); PostOrder(TT); printf("\n");
  printf("后序遍历结果2："); PostOrder1(TT); printf("\n");


  // 求二叉树的高度。
  printf("树的高度是：%d\n",TreeDepth(TT));

  return 0;
}

// 初始化顺序栈
void InitStack(PSeqStack SS)
{
  Clear(SS); // 清空顺序栈。
}

// 清空顺序栈。
void Clear(PSeqStack SS)
{
  if (SS == NULL) return; // 检查空指针。

  SS->top=-1;  // 栈顶指针置为-1。
  memset(SS->data,0,sizeof(ElemType)*MAXSIZE);  // 数组元素清零。
}

// 求顺序栈的长度，返回值：栈SS中元素的个数。
int Length(PSeqStack SS)
{
  if (SS == NULL) return 0; // 检查空指针。

  return SS->top+1;
}


// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。
int IsEmpty(PSeqStack SS)
{
  if (SS == NULL) return 0;  // 检查空指针。

  if (SS->top == -1) return 1;

  return 0;
}

// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqStack SS)
{
  if (SS == NULL) return 0;  // 检查空指针。

  if (SS->top >= MAXSIZE-1) return 1;

  return 0;
}

// 元素入栈，返回值：0-失败；1-成功。
int Push(PSeqStack SS, ElemType *ee)
{
  if ( (SS == NULL) || (ee == NULL) ) return 0;  // 检查空指针。

  if (IsFull(SS) == 1)
  {
    printf("顺序栈已满，不能插入。\n"); return 0;
  }

  SS->top++;  // 栈指针先加1。

  memcpy(&SS->data[SS->top],ee,sizeof(ElemType));  // 用数组的下标访问。
  // memcpy(SS->data+SS->top,ee,sizeof(ElemType));    // 采用指针运算也可以。

  return 1;
}

// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS)
{
  if (SS == NULL) return;  // 检查空指针。

  if (SS->top == -1) { printf("栈为空。\n"); return; }

  int kk;
  for (kk = 0; kk <= SS->top; kk++)
  {
    printf("SS[%d],value=%d\n",kk,SS->data[kk]);     // 用数组的下标访问。
    // printf("SS[%d],value=%d\n",kk,*(SS->data+kk));   // 采用指针运算也可以。
  }
}

// 元素出栈，返回值：0-失败；1-成功。
int Pop(PSeqStack SS, ElemType *ee)
{
  if ( (SS == NULL) || (ee == NULL) ) return 0;  // 检查空指针。

  if (SS->top == -1) { printf("栈为空。\n"); return 0; }

  memcpy(ee,&SS->data[SS->top],sizeof(ElemType));  // 用数组的下标访问。
  // memcpy(ee,SS->data+SS->top,sizeof(ElemType));    // 采用指针运算也可以。

  SS->top--;  // 栈指针减1。

  return 1;
}

// 获取栈顶元素，返回值：0-失败；1-成功。
// 只查看栈顶元素的值，元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee)
{
  if ( (SS == NULL) || (ee == NULL) ) return 0;  // 检查空指针。

  if (IsEmpty(SS) == 1) { printf("栈为空。\n"); return 0; }

  memcpy(ee,&SS->data[SS->top],sizeof(ElemType));  // 用数组的下标访问。
  // memcpy(ee,SS->data+SS->top,sizeof(ElemType));    // 采用指针运算也可以。

  return 1;
}

// 访问结点元素。
void visit(BiTNode *pp)
{
  printf("%c ",pp->data);  // 访问结点元素就是把值输出来，意思一下就行了。
}

// 二叉树的先序遍历。
void PreOrder(BiTree TT)
{
  if (TT == NULL) return;

  visit(TT);               // 访问子树TT的根结点。
  PreOrder(TT->lchild);    // 遍历左子树。
  PreOrder(TT->rchild);    // 遍历右子树。
}

// 二叉树的中序遍历。
void InOrder(BiTree TT)
{
  if (TT == NULL) return;

  InOrder(TT->lchild);     // 遍历左子树。
  visit(TT);               // 访问子树TT的根结点。
  InOrder(TT->rchild);     // 遍历右子树。
}

// 二叉树的后序遍历。
void PostOrder(BiTree TT)
{
  if (TT == NULL) return;

  PostOrder(TT->lchild);     // 遍历左子树。
  PostOrder(TT->rchild);     // 遍历右子树。
  visit(TT);                 // 访问子树TT的根结点。
}

// 不采用递归的方法对二叉树的先序遍历。
void PreOrder1(BiTree TT)
{
  SeqStack SS;     // 创建顺序栈。

  InitStack(&SS);  // 初始化顺序栈。

  ElemType ee=TT;  // 队列的元素是二叉树。

  while ( (ee!=NULL) || (IsEmpty(&SS)!=1) )
  {
    if (ee!=NULL)
    {
      visit(ee);               // 入栈前访问。
      Push(&SS,&ee);           // 入栈。
      ee=ee->lchild;           // 继续处理左子树。
    }
    else
    {
      Pop(&SS,&ee);            // 出栈。
      ee=ee->rchild;           // 处理右子树。 
    }
  }
}

// 不采用递归的方法对二叉树的中序遍历。
void InOrder1(BiTree TT)
{
  SeqStack SS;     // 创建顺序栈。

  InitStack(&SS);  // 初始化顺序栈。

  ElemType ee=TT;  // 队列的元素是二叉树。

  while ( (ee!=NULL) || (IsEmpty(&SS)!=1) )
  {
    if (ee!=NULL)
    {
      Push(&SS,&ee);        // 入栈。
      ee=ee->lchild;        // 继续处理左子树。
    }
    else
    {
      Pop(&SS,&ee);        // 出栈。
      visit(ee);           // 访问出栈元素。
      ee=ee->rchild;       // 处理右子树。
    }
  }
}

// 不采用递归的方法对二叉树的后序遍历。
void PostOrder1(BiTree TT)
{
  SeqStack SS;      // 创建顺序栈。

  InitStack(&SS);   // 初始化顺序栈。

  ElemType ee=TT;   // 队列的元素是二叉树。
  
  ElemType pp=NULL; // 最近访问过的结点。

  while ( (ee!=NULL) || (IsEmpty(&SS)!=1) )
  {
    if (ee!=NULL)    // 从根结点开始，沿树的左结点，依次入栈，直到左结点为空。
    {
      Push(&SS,&ee);
      ee=ee->lchild;
    }
    else   // 转向右。
    {
      // 读取栈顶元素，不出栈。
      GetTop(&SS,&ee);       

      // 如果右子树存在并且没有被访问过。
      if ( (ee->rchild!=NULL) && (ee->rchild!=pp) )
      {
        ee=ee->rchild;  // 转向右。
        Push(&SS,&ee);  // 右子树的根结点入栈。
        ee=ee->lchild;  // 再转向右子树的左结点。
      }
      else  
      {
        Pop(&SS,&ee);  // 将结点弹出。
        visit(ee);     // 访问结点。
        pp=ee;         // 记下最近访问过的结点。
        ee=NULL;       // 结点访问完后，重置ee为空，继续读取栈顶元素。
      }
    }
  }
}

// 求二叉树的高度。
int TreeDepth(BiTree TT)
{
  if (TT==NULL) return 0;

  int ll=TreeDepth(TT->lchild);  // 求左子树的高度。

  int rr=TreeDepth(TT->rchild);  // 求右子树的高度。

  return ll>rr ? ll+1: rr+1;  // 取左、右子树的较大者再加上根结点的高度。
}

  • 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
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
  • 373
  • 374
  • 375
  • 376
  • 377
  • 378
  • 379
  • 380
  • 381
  • 382
  • 383
  • 384
  • 385
  • 386
  • 387
  • 388
  • 389
  • 390
  • 391
  • 392
  • 393
  • 394
  • 395
  • 396
  • 397
  • 398
  • 399
  • 400
  • 401
  • 402
  • 403

3、非递归使用栈实现遍历

在这里插入图片描述
上图建议和下图中的文字解析一起看较容易理解；
在这里插入图片描述
在这里插入图片描述

实现代码在上述代码段中，函数为 PostOrder1(BiTree TT)、InOrder1(BiTree TT)、PreOrder1(BiTree TT)；

4.由遍历序列构造二叉树；在这里插入图片描述

给定一个序列，在给定一个遍历的方法，能否将还原出二叉树呢？
答案是：不能，如下图，给定先序遍历 123
可以构造出几种数；
在这里插入图片描述

还原一颗二叉树，需要多种遍历方法，仅一种遍历方法，无法还原二叉树：

由遍历序列构造二叉树

先序遍历序列+中序遍历序列
后序遍历序列+中序遍历序列
层次遍历序列+中序遍历序列

在这里插入图片描述
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/727147
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号