顺序结构实现二叉树的建立和各种遍历

「爱情、让人受尽委屈。」 2022-09-19 10:39 50阅读 0赞

//顺序存储的二叉树虽然节约了左右指针的空间，但是在对于一些深度较大，并且  
//树 的结构畸形，比如有一些树可能退化成为单链表  
//这种情况会造成二叉树空间浪费很大  
  
  
\#include <stdio.h>  
\#include <string.h>  
\#include <stdlib.h>  
//二叉树层序遍历是需要的循环队列  
\#define MAXSIZE 100  
typedef struct Queue  
\{  
int data\[MAXSIZE\];  
int top;//队列的头部  
int rear;//指向队列尾部的后一个元素  
\}Queue;  
  
  
void Init(Queue \*Q)  
\{  
memset(Q->data,0,sizeof(Q->data));  
Q->top = Q->rear = 0;  
\}  
  
  
bool Empty(Queue \*Q)  
\{  
if(Q->rear == Q->top)  
\{  
return true;  
\}  
return false;  
\}  
  
  
bool Full(Queue\*Q)  
\{  
if(Q->top == (Q->rear+1)%MAXSIZE)  
return true;  
return false;  
\}  
  
  
bool EnQueue(Queue\* Q,int e)  
\{  
if(Full(Q))  
return false;  
Q->data\[Q->rear\] = e;  
Q->rear = (Q->rear+1)%MAXSIZE;  
return true;  
\}  
  
  
bool DeQueue(Queue \*Q,int &e)  
\{  
if(Empty(Q))  
return false;  
e = Q->data\[Q->top\];  
Q->top = (Q->top+1)%MAXSIZE;  
return true;  
\}  
  
  
//定义二叉树的最大层数  
\#define MAXDEPTH 10  
int t\[1<<MAXDEPTH\];//二叉树顺序存储数组，0代表空，默认是正数  
char \* str = "abdh\#\#\#e\#\#cf\#\#g\#\#";  
int index = 0;  
//二叉树的建立，利用先序遍历的思想来建立  
//n是根节点  
void Create(int n)  
\{  
//如果是\#的话说明是空  
if(str\[index++\] == '\#')  
\{  
t\[n\] =t\[2\*n\] = t\[2\*n+1\] = 0;  
\}  
else  
\{  
t\[n\] = str\[index-1\];  
Create(2\*n);  
Create(2\*n+1);  
\}  
\}  
//二叉树的先序遍历  
void Pre(int root)  
\{  
printf("%c",t\[root\]);  
if(t\[root\*2\])  
Pre(root\*2);  
if(t\[root\*2+1\])  
Pre(root\*2+1);  
\}  
//二叉树的中序遍历  
void In(int root)  
\{  
if(t\[root\*2\])  
In(root\*2);  
printf("%c",t\[root\]);  
if(t\[root\*2+1\])  
In(root\*2+1);  
\}  
//二叉树的后序遍历  
void Post(int root)  
\{  
if(t\[root\*2\])  
Post(root\*2);  
if(t\[root\*2+1\])  
Post(root\*2+1);  
printf("%c",t\[root\]);  
\}  
//二叉树的层序遍历  
void Level()  
\{  
Queue Q;  
Init(&Q);  
int temp;  
int root = 1;  
EnQueue(&Q,1);  
while(!Empty(&Q))  
\{  
DeQueue(&Q,temp);  
printf("%c",t\[temp\]);  
if(t\[temp\*2\])  
EnQueue(&Q,temp\*2);  
if(t\[temp\*2+1\])  
EnQueue(&Q,temp\*2+1);  
\}  
\}  
  
  
int main()  
\{  
//初始化全部是kong  
memset(t,0,sizeof(t));  
//建立二叉树  
Create(1);  
//先序遍历  
Pre(1);  
putchar('\\n');  
//中序遍历  
In(1);  
putchar('\\n');  
//后序遍历  
Post(1);  
putchar('\\n');  
//层序遍历  
Level();  
putchar('\\n');  
return 0;  
\}