返回顶部

收藏

按从上到下从左到右的顺序构建满二叉树

更多
#include "stdafx.h"

#include "stdlib.h"
#include "stdio.h"

typedef struct node
{
    int num;
    node * lchild;
    node * rchild;
};

struct chain
{
    node * Node;
    chain * next;
}*head;

//显示二叉树,借用了别人的额代码
void ShowTree(node *T) 
{
    node *stack[100];
    node*p;
    int level[100][2];
    int top,n,i;
    int width=4;
    if(T!=NULL)
    {
        top=1;
        stack[top]=T;
        level[top][0]=width;
        while(top>0)
        {
            p=stack[top];
            n=level[top][0];
            for(i=1;i<=n;i++)
                printf(" ");
            printf("%d",p->num);
            for(i=n+1;i<60;i+=2)
                printf("*");
            printf("\\n\\t\\t");
            top--;
            if(p->rchild!=NULL)
            {
                top++;
                stack[top]=p->rchild ;
                level[top][0]=n+width;
                level[top][1]=2;
            }
            if(p->lchild!=NULL)
            {
                top++;
                stack[top]=p->lchild ;
                level[top][0]=n+width;
                level[top][1]=1;
            }
        }
    }
}

//每次新添加的节点加入链表尾部。
//则新节点的父节点必然是头节点。
void AddNode(int Num)
{

    node * NewNode=(node*)calloc(1,sizeof (node));
    NewNode->num=Num;

    node * FatherNode=head->Node;

    if(FatherNode->lchild ==NULL)
        FatherNode->lchild =NewNode;

    else if(FatherNode->rchild ==NULL)
    {
        FatherNode->rchild =NewNode;
        //如果右节点也添加了,则链表头移到下一个
        head=head->next ;
    }
    else
        return;

    chain *tail=head;
    //找到链表尾
    while (tail->next!=NULL)
        tail=tail->next;
    //添加新节点到链表尾
    chain *Newtail=(chain*)calloc(1,sizeof (chain));
    Newtail->Node =NewNode;
    tail->next=Newtail;
}

//本程序的目的是构造满二叉树(版本2),
//按照从上到下、从左到右添加。
//平台为vc++2010,如果是vc6删除第一个头文件即可。
//新手学习二叉树,请各位多多指教!
//本程序的版本1链接:
//http://www.oschina.net/code/snippet_217193_12427
//email     leiyang-ge@163.com
//qq        675686066
int main()
{
    //根节点
    node * root=(node*)calloc(1,sizeof (node));
    root->num=1;

    head=(chain*)calloc(1,sizeof (chain));
    head->Node =root;
    head->next =NULL;

    for(int N=2;N<=31;N++)

        AddNode(N);

    ShowTree(root);

    getchar();
    return 0;
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

发表评论