设二叉树的存储结构为二叉链表,编写有关二叉树的递归算法:
发布网友
发布时间：2022-05-05 22:22
共1个回答
热心网友
时间：2022-06-28 05:10
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define NUM_NODE12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
}
else
{
p = *--top;//p出栈
if (p)printf("%d ", p->data);
p = p->rchild;
}
}
//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p)printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}
//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍历求结点的深度和度为0，1,2的结点数，结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;
//遍历循环
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p)printf("%d ", p->data); //Visit结点
//计算个结点的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;
p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;
return ;
}
//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}
//求广度的程序，返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}
