数据结构

二叉树的广度优先遍历

可以在struct内写默认构造函数.
在buildTree方法中声明了nodeList[len], 返回值为&nodeList[1]时结果print方法报错,原来我是把局部变量的地址传出,结果局部变量的内存已经被释放.改为声明nodeList为全局变量,或者使用malloc.malloc方法是直接向内存申请空间,不手动free这块内存就永远不会被释放,容易产生内存泄露.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;

typedef int DATA_TYPE;

typedef struct node
{
    DATA_TYPE data;
    node *lch, *rch;
    node()
    {
        data = 0;
        lch = rch = 0;
    }
} Node;

Node nodeList[100];

void print(Node *r)
{
    if(r)
    {
        printf("%d", r->data);
        print(r->lch);
        print(r->rch);
    }
}

Node *buildTree(DATA_TYPE dataArray[], int len)
{
    for(int i=1; i<len; i++)
    {
        nodeList[i].data = dataArray[i];
        if(i%2)
        {
            nodeList[i/2].rch = &nodeList[i];
        }
        else
        {
            nodeList[i/2].lch = &nodeList[i];
        }
    }
    return &nodeList[1];
}

/**
* BFS breadth first search
* 广度优先搜索
*/
void bfs(Node *r)
{
    printf("breadth first search:\n");
    queue<Node*> que;
    que.push(r);
    while(!que.empty())
    {
        Node *node = que.front();
        que.pop();
        printf("%d", node->data);
        if(node->lch)que.push(node->lch);
        if(node->rch)que.push(node->rch);
    }
}

int main()
{
    DATA_TYPE dataArray[] = {0,1,2,3,4,5,6,7};
    Node *root = buildTree(dataArray, sizeof(dataArray)/sizeof(DATA_TYPE));
    //print(root);
    bfs(root);
    return 0;
}