#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
typedef struct Node
{
char data;
struct Node *Lchild;
struct Node *Rchild;
}BiTNode,*BiTree;
/*************************************/
void createBiTree(BiTree *root) //扩展先序遍历序列创建二叉树
{
char ch;
ch = getchar();
if(ch == '^') *root=NULL;
else
{
*root=(BiTree)malloc(sizeof(BiTNode));
(*root)->data=ch;
createBiTree(&((*root)->Lchild));
createBiTree(&((*root)->Rchild));
}
}
void printTree(BiTree root,int h) //按树状输出二叉树
{
int i;
if(root==NULL) return ;
printTree(root->Rchild,h+1);
for(i=0;i<h;i++) printf(" ");
printf("%c\n",root->data);
printTree(root->Lchild,h+1);
}
/*************************************/
/************************************/
void Preorder(BiTree root){ //先序遍历算法
if(root){
printf(",",root->data);
Preorder(root->Lchild);
Preorder(root->Rchild);
}
}
/***********************************/
void Inorder(BiTree root){ //中序遍历算法
if(root==NULL) return;
Inorder(root->Lchild);
printf(",",root->data);
Inorder(root->Rchild);
}
/***********************************/
void NRInorder(BiTree root) //非递归中序遍历
{
BiTree s;
//s-指向当前节点
BiTree stack[100];
//定义栈
int top=-1;
//初始化栈顶指针
if(root==NULL)
return;
stack[++top]=root; //根指针入栈
s=root->Lchild; //s指向左子树
while(s!=NULL||top!=-1) //当存在节点(涉及到根下右子树)或者栈不为空,进行遍历
{
while(s!=NULL) //如果存在节点,寻找最左子树并入栈
{
if(top>=99)
{
printf("栈为满\n");
return;
}
stack[++top]=s; //当前节点入栈
s=s->Lchild; //左子树进行遍历
}
if(top==-1)
{
printf("栈为空\n");
return;
}
s=stack[top--];
//弹出栈顶元素到s中
printf("%c ",s->data);
//输出当前节点元素值
s=s->Rchild;
//遍历右子树
}
}
/*************************************/
void Postorder(BiTree root){ //后序遍历算法
if(root){
Postorder(root->Lchild);
Postorder(root->Rchild);
printf(",",root->data);
}
}
/***********************************/ //树的高度
int PostTreeDepth(BiTree root)
{
int hl,hr,h;
if(root==NULL) return 0;
else
{
hl=PostTreeDepth(root->Lchild);
hr=PostTreeDepth(root->Rchild);
h =(hl>hr? hl:hr)+1;
return h;
}
}
/**********************************/
int PostTreeLeaf(BiTree root) //后序遍历求节点数
{
int count,count1,count2;
if(root == NULL)
return 0;
if(root->Lchild == NULL && root->Rchild == NULL)
return 1;
count1=PostTreeLeaf(root->Lchild);
count2=PostTreeLeaf(root->Rchild);
count =count1+count2;
return count;
}
/***********************************/
int PostTreeOneAspectLeaf(BiTree root,int aspect) //求树每层有多少个叶子
{
int count,count1,count2;
if(root==NULL||aspect==0) return 0;
if(aspect==1&&root->Lchild==NULL&&root->Rchild==NULL) return 1;
count1=PostTreeOneAspectLeaf(root->Lchild,aspect-1);
count2=PostTreeOneAspectLeaf(root->Rchild,aspect-1);
count=count1+count2;
return count;
}
BiTree SDParents(BiTree root,BiTree current)
{
BiTree p;
if(root==NULL) return NULL;
if(root->Lchild==current||root->Rchild==current)
return root;
p=SDParents(root->Lchild,current);
if(p!=NULL) return p;
else return(SDParents(root->Rchild,current));
}
int main()
{
BiTree root=NULL;
int h; //树的高度；
int count; //树的叶子节点的个数
int aspect=1; //树的层数
char ch;
printf("请按扩展的先序遍历序列输入树的节点数据:\n");
createBiTree(&root);
printf("按树状结果输出：\n");
printTree(root,1);
printf("\n先序遍历输出:\n");
Preorder(root);
printf("\n中序遍历输出:\n");
Inorder(root);
printf("\n非递归中序遍历输出:\n");
NRInorder(root);
printf("\n后序遍历输出:\n");
Postorder(root);
h=PostTreeDepth(root);
printf("\n树的高度为:\n");
printf("%d",h);
count=PostTreeLeaf(root);
printf("\n树的叶子节点个数为:\n");
printf("%d\n",count);
printf("第%d层有%d个叶子结点",aspect,count);
printf("\n结点B的双亲为：\n");
root=SDParents(root,root->Lchild);
printf("%c",root->data);
}
转载请注明原文地址: https://ju.6miu.com/read-1000204.html
