二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组。
网站建设哪家好，找成都创新互联！专注于网页设计、网站建设、微信开发、微信平台小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了乌尔禾免费建站欢迎大家使用！
后序遍历
层次遍历
一、头文件
#include#include#include#define MAXSIZE 5 二、二叉树的结构
//二叉树的结构
typedef struct BTnode
{
char element;
struct BTnode *left;
struct BTnode *right;
}*BTnodePtr;三、队列的结构
//队列
typedef struct BTNodePtrQueue
{
BTnodePtr *nodePtrs;
int front;
int rear;
}*QueuePtr;四、队列的初始化
//初始化队列
QueuePtr initQueue()
{
QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
resultPtr->front = 0;
resultPtr->rear = 1;
return resultPtr;
}五、判断队列是否为空
int isQueueEmpty(QueuePtr paraQueuePtr)
{
if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear)
{
return 1;
}
return 0;
}六、添加元素
//在队列中添加元素
void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
{
printf("The queue is full.\n");
return ;
}
Queue->nodePtrs [Queue->rear] = newBTnodePtr;
Queue->rear = (Queue->rear+1)%MAXSIZE;
printf("enqueue %c ends.\r\n", newBTnodePtr->element);
}七、删除元素
//删除元素
BTnodePtr deQueue(QueuePtr Queue)
{
if(isQueueEmpty(Queue))
{
printf("The queue is empty,can not delete.\n");
return ;
}
Queue->front = (Queue->front +1)%MAXSIZE;
printf("delete %c ends.\n",Queue->nodePtrs [Queue->front]->element);
return Queue->nodePtrs [Queue->front];
}八、创建结点
//创建结点
BTnodePtr constructBTnode(char newElement)
{
BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
newPtr->element = newElement;
newPtr->left = NULL;
newPtr->right = NULL;
return newPtr;
}九、创建二叉树
//创建二叉树
BTnodePtr stringToBTree(char *newString)
{
int i;
char ch;
i = 0;
QueuePtr Queue = initQueue();
BTnodePtr resultHeader;
BTnodePtr tempParent,tempLeftChlid,tempRightChild;
ch = newString[i];
resultHeader = constructBTnode(ch);
enqueue(Queue,resultHeader);
while(!isQueueEmpty(Queue))
{
tempParent = deQueue(Queue);
//左
i++;
if(newString[i] == '#')
{
tempParent->left = NULL;
}
else
{
tempLeftChlid = constructBTnode(newString[i]);
enqueue(Queue,tempLeftChlid);
tempParent->left = tempLeftChlid;
}
//右
i++;
if(newString[i] == '#')
{
tempParent->right = NULL;
}
else
{
tempRightChild = constructBTnode(newString[i]);
enqueue(Queue,tempRightChild);
tempParent->right = tempRightChild;
}
}
return resultHeader;
}十、层次遍历
//层次遍历
void levelwise(BTnodePtr newTreePtr)
{
char string[100];
int i = 0;
QueuePtr Queue = initQueue();
BTnodePtr tempNodePtr;
enqueue(Queue,newTreePtr);
while(!isQueueEmpty(Queue))
{
tempNodePtr = deQueue(Queue);
string[i] = tempNodePtr->element ;
i++;
if(tempNodePtr->left != NULL)
{
enqueue(Queue,tempNodePtr->left);
}
if(tempNodePtr->right != NULL)
{
enqueue(Queue,tempNodePtr->right);
}
}
string[i] = '\0';
printf("levewise:%s",string);
}十一、主函数
int main(){
BTnodePtr tempHeader;
char* tempString = "acde#bf######";
tempHeader = stringToBTree(tempString);
printf("Levelwise: ");
levelwise(tempHeader);
printf("\r\n");
return 1;
}十二、全部代码
include#include#include#define MAXSIZE 5
//二叉树的结构
typedef struct BTnode
{
char element;
struct BTnode *left;
struct BTnode *right;
}*BTnodePtr;
//队列
typedef struct BTNodePtrQueue
{
BTnodePtr *nodePtrs;
int front;
int rear;
}*QueuePtr;
//初始化队列
QueuePtr initQueue()
{
QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
resultPtr->front = 0;
resultPtr->rear = 1;
return resultPtr;
}
int isQueueEmpty(QueuePtr paraQueuePtr)
{
if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear)
{
return 1;
}
return 0;
}
//在队列中添加元素
void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
{
printf("The queue is full.\n");
return ;
}
Queue->nodePtrs [Queue->rear] = newBTnodePtr;
Queue->rear = (Queue->rear+1)%MAXSIZE;
printf("enqueue %c ends.\r\n", newBTnodePtr->element);
}
//删除元素
BTnodePtr deQueue(QueuePtr Queue)
{
if(isQueueEmpty(Queue))
{
printf("The queue is empty,can not delete.\n");
return ;
}
Queue->front = (Queue->front +1)%MAXSIZE;
printf("delete %c ends.\n",Queue->nodePtrs [Queue->front]->element);
return Queue->nodePtrs [Queue->front];
}
//创建结点
BTnodePtr constructBTnode(char newElement)
{
BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
newPtr->element = newElement;
newPtr->left = NULL;
newPtr->right = NULL;
return newPtr;
}
//创建二叉树
BTnodePtr stringToBTree(char *newString)
{
int i;
char ch;
i = 0;
QueuePtr Queue = initQueue();
BTnodePtr resultHeader;
BTnodePtr tempParent,tempLeftChlid,tempRightChild;
ch = newString[i];
resultHeader = constructBTnode(ch);
enqueue(Queue,resultHeader);
while(!isQueueEmpty(Queue))
{
tempParent = deQueue(Queue);
//左
i++;
if(newString[i] == '#')
{
tempParent->left = NULL;
}
else
{
tempLeftChlid = constructBTnode(newString[i]);
enqueue(Queue,tempLeftChlid);
tempParent->left = tempLeftChlid;
}
//右
i++;
if(newString[i] == '#')
{
tempParent->right = NULL;
}
else
{
tempRightChild = constructBTnode(newString[i]);
enqueue(Queue,tempRightChild);
tempParent->right = tempRightChild;
}
}
return resultHeader;
}
//层次遍历
void levelwise(BTnodePtr newTreePtr)
{
char string[100];
int i = 0;
QueuePtr Queue = initQueue();
BTnodePtr tempNodePtr;
enqueue(Queue,newTreePtr);
while(!isQueueEmpty(Queue))
{
tempNodePtr = deQueue(Queue);
string[i] = tempNodePtr->element ;
i++;
if(tempNodePtr->left != NULL)
{
enqueue(Queue,tempNodePtr->left);
}
if(tempNodePtr->right != NULL)
{
enqueue(Queue,tempNodePtr->right);
}
}
string[i] = '\0';
printf("levewise:%s",string);
}
int main(){
BTnodePtr tempHeader;
char* tempString = "acde#bf######";
tempHeader = stringToBTree(tempString);
printf("Levelwise: ");
levelwise(tempHeader);
printf("\r\n");
return 1;
} 十三、测试结果
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
