Go语言实现二叉树遍历

Python013

Go语言实现二叉树遍历,第1张

图例如下:

结果应该是分别是：

广度优先: a ->b ->c ->d ->f ->e ->g

先序遍历: a ->b ->d ->e ->f ->g ->c

中序遍历: e ->d ->b ->g ->f ->a ->c

后序遍历: e ->d ->g ->f ->b ->c ->a

结果存在result里面，如果不存可以少一层变量

这个地方强烈建议读一下下面的第一个链接，我遵照着那篇文章实现的，只是用Go改写了而已。

首先定义一个数据结构，用来存储一些Node的信息。

这里是可以运行的，但是总会抛出一个数组越界的错误，我看了半天也没看出来哪里有问题，Mac版的devel我这边又有bug，没用起来。至少思路对了，我后面再看一下哪里的问题。(感谢 @RiXu 指正)

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define maxsize 100

typedef char datatype

typedef struct node

{

datatype data

struct node *lchild,*rchild//*parent

int l,r

} bitree

bitree *root

bitree *pre

bitree *Q[maxsize]

bitree *creatree()

{

char ch

int j,flag

int front,rear//队头、队尾指针

bitree *root,*s

root=NULL//置空二叉树

front=1rear=0//置空队列

int temp=-1

char Array[50]

printf(">>>请输入数组(以'#'结束)：\n")

while(Array[temp]!='#')

{

temp++

scanf("%c",&Array[temp])

}

int i=0

bitree *loc,*p

ch=Array[i]

while(temp!=0)//不是结束符时重复做

{

s=(bitree *)malloc(sizeof(bitree))

s->data=ch

s->lchild=NULL

s->rchild=NULL

rear++

Q[rear]=s//新结点地址入队

loc=Q[front]

if(rear==1)

{

root=s

}//输入的第一个结点为根结点

else

{

while(!loc)//扫描位置不为空时，做循环

if(s->data<loc->data)//判断当前结点值与要插入结点的值大小

{

p=locloc=loc->lchildflag=0//当前结点值>要插入结点的值大小,将指针指向当前节点的左孩子

}

else

{

p=locloc=loc->rchildflag=1//当前结点值<要插入结点的值大小,将指针指向当前节点的右孩子

}

for(j=1j<=rearj++)

{

if(Q[j]==p&&flag==0)

Q[j]->lchild=s//将结点插入到其左孩子

if(Q[j]==p&&flag==1)

Q[j]->rchild=s//将结点插入到其右孩子

}

loc=s

}

temp--

ch=Array[++i]//输入下一个字符

}

return root//返回根指针

}

void main()

{

bitree *p

p=creatree()//创建二叉树

//getch()

}