【数据结构】扩展先序序列建⽴⼆叉树以及对⼆叉树的⼀系列操作
题⽬要求
1. 输⼊⼆叉树的扩展先序序列，以⼆叉链表作为存储结构，建⽴⼆叉树。
2. 输出这棵⼆叉树的先序、中序和后序遍历序列，其中后序遍历使⽤⾮递归算法实现。
3. 统计⼆叉树中⾮叶⼦结点的个数。
4. 计算⼆叉树的⾼度。
⾮递归后序遍历⼆叉树思路
  在后序遍历中，左、右⼦树均访问完成后，从右⼦树返回时，上⼀层结点才能退栈并被访问。那么，当从⼦树返回时，如何判断是从左⼦树返回还是从右⼦树返回，进⽽确定栈顶的上⼀层结点是否应出栈。
  其中⼀种⽅法是，每个结点⼊栈时设置⼀个标记位flag同时⼊栈，进⼊左⼦树访问时，令flag = 0，进⼊右⼦树访问时，令flag = 1。当从⼦树返回时，通过flag的值来决定下⼀步的动作。
代码实现
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100005
/* ⼆叉链表结点 */
typedef struct Node {
char data;/* ⼆叉链表的结点信息 */
struct Node* LChild;/* 结点的左⼦树 */
struct Node* RChild;/* 结点的右⼦树 */
} BiTNode,* BiTree;
/* 栈结构 */
typedef struct elem {
BiTNode node;/* 栈中元素的结点信息 */
int flag;/* 标记位，进左⼦树为0，进右⼦树为1 */
} ElemType;
typedef struct stack {
ElemType elem[MAXSIZE];/* 顺序栈数组 */
int top;/* 栈顶指针 */
} SeqStack;
/* ⾃定义函数声明 */
BiTNode*CreateBiTree(BiTNode* root);/* 扩展先序序列建⽴⼆叉树 */
void PreOrder(BiTree root);/* 递归先序遍历⼆叉树 */
void InOrder(BiTree root);/* 递归中序遍历⼆叉树 */
void PostOrder(BiTree root);/* ⾮递归后序遍历⼆叉树 */
SeqStack*InitStack(void);/* 初始化栈 */
int Empty(SeqStack* s);/* 判空栈 */
int Push(SeqStack* s, ElemType x);/* ⼊栈 */
int Pop(SeqStack* s);/* 出栈 */
ElemType*GetTop(SeqStack* s);/* 取栈顶元素 */
int NonLeafNode(BiTree root);/* 统计⼆叉树中⾮叶⼦结点的个数 */
int BiTreeDeepth(BiTree root);/* 计算⼆叉树的⾼度 */
/* 主函数 */
int main(void){
BiTNode* root =CreateBiTree(root);
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
printf("\n");
printf("%d\n",NonLeafNode(root));
printf("%d\n",BiTreeDeepth(root));
return0;
先序中序后序遍历二叉树
}
/
* ⾃定义函数 */
BiTNode*CreateBiTree(BiTNode* root){
char ch;
ch =getchar();
if(ch =='#'){
return NULL;
}else{
root =(BiTNode*)malloc(sizeof(BiTNode));        root->data = ch;
root->LChild =CreateBiTree(root->LChild);        root->RChild =CreateBiTree(root->RChild); }
return root;
}
void PreOrder(BiTree root){
if(root){
printf("%c", root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
void InOrder(BiTree root){
if(root){
InOrder(root->LChild);
printf("%c", root->data);
InOrder(root->RChild);
}
}
void PostOrder(BiTree root){
SeqStack* s;
s =(SeqStack*)malloc(sizeof(SeqStack)); while(root ||!Empty(s)){
while(root){
ElemType temp;
temp.flag =0;
Push(s, temp);
root = root->LChild;
}
while(!Empty(s)&&GetTop(s)->flag ==1){
printf("%c",GetTop(s)->node.data);
Pop(s);
}
if(!Empty(s)){
root =GetTop(s)->node.RChild;
GetTop(s)->flag =1;
}
}
}
SeqStack*InitStack(void){
SeqStack* s;
s =(SeqStack*)malloc(sizeof(SeqStack));
s->top =-1;
return s;
}
int Empty(SeqStack* s){
if(s->top ==-1){
return1;
}else{
return0;
}
}
int Push(SeqStack* s, ElemType x){
if(s->top == MAXSIZE -1){
return0;/* 栈满不能⼊栈 */
}else{
s->top++;
s->elem[s->top]= x;
return1;
}
}
int Pop(SeqStack* s){
if(Empty(s)){
return0;/* 栈空不能出栈 */
}else{
s->top--;
return1;
}
}
ElemType*GetTop(SeqStack* s){
if(Empty(s)){
return NULL;/* 栈空 */
}else{
return&(s->elem[s->top]);
}
}
int NonLeafNode(BiTree root){
if(!root){
return0;
}else if(!root->LChild &&!root->RChild){
return0;
}else{
return NonLeafNode(root->LChild)+NonLeafNode(root->RChild)+1; }
}
int BiTreeDeepth(BiTree root){
if(!root){
return0;
}else{
if(BiTreeDeepth(root->LChild)>BiTreeDeepth(root->RChild)){
return1+BiTreeDeepth(root->LChild);
}else{
return1+BiTreeDeepth(root->RChild);
}
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。