计算二叉树高度，寻找最长路径（C语言，栈，二叉树，递归方式）

源代码/************************** 21 ***********************************/#include<stdio.h>typedef struct abc{struct abc *lchild,*rchild;int data;}Node;Node * init();void scan(Node *T);Node* pre_fin

ghhgy531

912人浏览 · 2020-11-29 21:13:27

ghhgy531 · 2020-11-29 21:13:27 发布

源代码

/************************** 计算二叉树高度，寻找最长路径 ***********************************/
#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--];
    }
}