计算二叉树高度,寻找最长路径(C语言,栈,二叉树,递归方式)
源代码/************************** 21 ***********************************/#include<stdio.h>typedef struct abc{struct abc *lchild,*rchild;int data;}Node;Node * init();void scan(Node *T);Node* pre_fin
·
源代码
/************************** 计算二叉树高度,寻找最长路径 ***********************************/
#include<stdio.h>
typedef struct abc
{
struct abc *lchild,*rchild;
int data;
}Node;
Node * init();
void scan(Node *T);
Node* pre_find(Node *T,int data);
void add(Node *in_node,int dir,int data);
void pre_visit(Node *T);
void mid_visit(Node *T);
void pos_visit(Node *T);
int count_height(Node *T);
//以下为栈数据结构
//-----------------------------------------
#define Maxsize 100
typedef struct bcd
{
Node *data[Maxsize];
int top;
}Stack;
int push(Stack *p,Node *ch);
Node* pop(Stack *p);
int is_empty(Stack *s);
Stack * init_stack();
//-----------------------------------------
int find_by_height(Node *T,int h,Stack *stk);
int main()
{
Node *T=init();
Stack *stk=init_stack();
int i,a,b,c,n=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(pre_find(T,a),b,c);
}
scan(T);
int h=count_height(T);
printf("高度:%d\n",h);
find_by_height(T,h,stk);
printf("第一条最长路径为:");
while(!is_empty(stk))
{
printf("%d->",pop(stk)->data);
}
return 0;
}
Node * init()
{
Node *t=(Node*)malloc(sizeof(Node));
t->lchild=NULL;
t->rchild=NULL;
t->data=0;
return t;
}
void scan(Node *T)
{
printf("先序遍历:");
pre_visit(T);
printf("\n中序遍历:");
mid_visit(T);
printf("\n后序遍历:");
pos_visit(T);
printf("\n----------------------------------\n");
}
void add(Node *in_node,int dir,int data)
{
if(in_node!=NULL)
{
if(dir==0&&in_node->lchild==NULL)
{
Node *a=(Node*)malloc(sizeof(Node));
a->lchild=NULL;
a->rchild=NULL;
a->data=data;
in_node->lchild=a;
}
if(dir==1&&in_node->rchild==NULL)
{
Node *a=(Node*)malloc(sizeof(Node));
a->lchild=NULL;
a->rchild=NULL;
a->data=data;
in_node->rchild=a;
}
}
}
Node* pre_find(Node *T,int data)//找到以T为根节点的二叉树中值为data的节点指针
{
if(T!=NULL)
{
if(data==T->data)
return T;
Node *tmp=pre_find(T->lchild,data);
if(tmp!=NULL)
return tmp;
return pre_find(T->rchild,data);
}
return NULL;
}
void pre_change(Node *T)//交换每个节点的左右孩子
{
if(T!=NULL)
{
Node *tmp=T->lchild;
T->lchild=T->rchild;
T->rchild=tmp;
pre_change(T->lchild);
pre_change(T->rchild);
}
}
void mid_change(Node *T)//交换每个节点的左右孩子,这个交换应该有问题,除非把交换后的递归参数改成lchild
{
if(T!=NULL)
{
mid_change(T->lchild);
Node *tmp=T->lchild;
T->lchild=T->rchild;
T->rchild=tmp;
mid_change(T->rchild);//除非把这里的rchild改成lchild
}
}
void pos_change(Node *T)//交换每个节点的左右孩子
{
if(T!=NULL)
{
pos_change(T->lchild);
pos_change(T->rchild);
Node *tmp=T->lchild;
T->lchild=T->rchild;
T->rchild=tmp;
}
}
void pre_visit(Node *T)
{
if(T!=NULL)
{
printf("%d->",T->data);
pre_visit(T->lchild);
pre_visit(T->rchild);
}
}
void mid_visit(Node *T)
{
if(T!=NULL)
{
mid_visit(T->lchild);
printf("%d->",T->data);
mid_visit(T->rchild);
}
}
void pos_visit(Node *T)
{
if(T!=NULL)
{
pos_visit(T->lchild);
pos_visit(T->rchild);
printf("%d->",T->data);
}
}
int count_height(Node *T)//计算二叉树高度,高度即为最长路径长度
{
int a,b;
if(T!=NULL)
{
if(T->lchild==NULL&&T->rchild==NULL)
return 1;
//printf("%d->",T->data);
a=count_height(T->lchild);
b=count_height(T->rchild);
return 1+(a<b?b:a);
}
return 0;
}
int find_by_height(Node *T,int h,Stack *stk)//根据给定的高度h递归二叉树,如果成功找到这样的节点,将他压栈,无需遍历其他子树,并返回1,没有找到返回0。
{
int a,b;
if(T!=NULL)
{
h--;
if(h>0)
{
if(find_by_height(T->lchild,h,stk))
{
//printf("%d,",T->data);
push(stk,T);
return 1;
}
else if(find_by_height(T->rchild,h,stk))
{
//printf("%d,",T->data);
push(stk,T);
return 1;
}
}
else if(h==0)
{
//printf("%d,",T->data);
push(stk,T);
return 1;
}
}
return 0;
}
//以下为栈相关操作
int is_empty(Stack *s)
{
if(s->top==-1)
{
return 1;
}
return 0;
}
Stack * init_stack()
{
Stack *stk;
stk=(Stack *)malloc(sizeof(Stack));
stk->top=-1;
return stk;
}
int push(Stack *p,Node* ch)
{
if(p->top==Maxsize-1)
{
return 0;
}
else
{
p->data[++p->top]=ch;
return 1;
}
}
Node* pop(Stack *p)
{
if(p->top==-1)
{
return NULL;
}
else
{
return p->data[p->top--];
}
}
输入数据说明:
初始化时,根节点为0,第一行输入为插入的节点个数n,接下来有n行,例如 0 0 1,第一个代表根节点,第二个数代表左子树还是右子树,0代表左,1代表右,第三个数代表插入的节点,0 0 1就是在0左边插入一个1节点。
测试数据1:
6
0 0 1
0 1 2
1 0 3
1 1 4
2 0 5
2 1 6
上面的数据代表的也就是下面这张二叉树
测试数据2:
6
0 0 1
0 1 2
1 0 3
1 1 4
4 0 6
2 1 5
上面的数据代表的也就是下面这张二叉树
其他测试数据:
2
0 0 1
0 1 2
1
0 0 1
2
0 0 1
1 1 2
2
0 0 1
1 0 2
5
0 0 1
0 1 2
1 0 3
1 1 4
2 0 5
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献2条内容
所有评论(0)