go语言数组转二叉树 数组转化成二叉树

数组实现二叉树

#include stdio.h

创新互联建站专注骨干网络服务器租用10年，服务更有保障！服务器租用，达州服务器托管 成都服务器租用，成都服务器托管，骨干网络带宽，享受低延迟，高速访问。灵活、实现低成本的共享或公网数据中心高速带宽的专属高性能服务器。

#include malloc.h

#define MAX 1000 //假设二叉树最多一千个结点

//当然也可以使用动态方式，不过此处为了简单演示数组存储

//二叉树采用固定长度方式处理。

class Tree {

private:

char *array[MAX];

void createOneNode(int index);

void showOneNode(int index);

public:

Tree() {

for (int i = 0; i MAX; i++)

array[i] = NULL;

}

void createTree();

void addOneNode(int index, char value);

void deleteOneNode(int index);

void showTree();

};

void Tree::createTree()

{

createOneNode(0);

}

void Tree::createOneNode(int index)

{

char value;

scanf("%c", value);

if (index = MAX || value == '#')

return;

array[index] = (char *)malloc(sizeof(char));

*array[index] = value;

createOneNode((index + 1) * 2 - 1);

createOneNode((index + 1) * 2);

}

void Tree::addOneNode(int index, char value)

{

if (index = MAX || (index != 0 array[index / 2] == NULL))

return;

if (array[index] == NULL)

array[index] = (char *)malloc(sizeof(char));

*array[index] = value;

}

void Tree::deleteOneNode(int index)

{

if (index = MAX || array[index] == NULL)

return;

free(array[index]);

array[index] = NULL;

deleteOneNode((index + 1) * 2 - 1);

deleteOneNode((index + 1) * 2);

}

void Tree::showTree()

{

showOneNode(0);

}

void Tree::showOneNode(int index)

{

if (index = MAX || array[index] == NULL)

return;

printf("%c ", *array[index]);

showOneNode((index + 1) * 2 - 1);

showOneNode((index + 1) * 2);

}

怎样把一个数组转化成二叉树？

1、从根节点向下搜，大的往右，小的往左，依次向下搜索，直到无法向下继续搜索为止。这时就找到了该数在二叉树中的位置。存储二叉树只须按行存储，从左往右存储就行了。

2、所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。

3、在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

数组建立二叉树的问题（c语言)

BTREE createbt2(int a[],int i,int n)

{

BTREE p;

if(in) return NULLelse

{

p=(BTREE)malloc(sizeof(BTNode));;//判断节点是不是虚节点，如果是的话就分配一个地址

p-data =a[i]; //用于存放数据的一个数组

p-lchild =createbt2(a,2*i,n); //你先把这个二叉树补充成带有NULL的完全二叉树，I表示从根往下数第几个节点

p-rchild =createbt2(a,2*i+1,n);

return p;

}

}

现在这个二叉树还在构造，所以不能判断是什么序的，具体什么序是看二叉树的访问的时候跟节点的位置，如果是先跟节点就是前序，同理也有中序和后序

Go语言实现二叉树遍历

图例如下:

结果应该是分别是：

广度优先: 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 指正)

Golang-基于TimeingWheel定时器

在linux下实现定时器主要有如下方式

在这当中 基于时间轮方式实现的定时器 时间复杂度最小，效率最高，然而我们可以通过 优先队列 实现时间轮定时器。

优先队列的实现可以使用最大堆和最小堆，因此在队列中所有的数据都可以定义排序规则自动排序。我们直接通过队列中 pop 函数获取数据，就是我们按照自定义排序规则想要的数据。

在 Golang 中实现一个优先队列异常简单，在 container/head 包中已经帮我们封装了，实现的细节，我们只需要实现特定的接口就可以。

下面是官方提供的例子

因为优先队列底层数据结构是由二叉树构建的，所以我们可以通过数组来保存二叉树上的每一个节点。

改数组需要实现 Go 预先定义的接口 Len , Less , Swap , Push , Pop 和 update 。

timerType结构是定时任务抽象结构

首先的 start 函数，当创建一个 TimeingWheel 时，通过一个 goroutine 来执行 start ,在start中for循环和select来监控不同的channel的状态

通过for循环从队列中取数据，直到该队列为空或者是遇见第一个当前时间比任务开始时间大的任务， append 到 expired 中。因为优先队列中是根据 expiration 来排序的，

所以当取到第一个定时任务未到的任务时，表示该定时任务以后的任务都未到时间。

当 getExpired 函数取出队列中要执行的任务时，当有的定时任务需要不断执行，所以就需要判断是否该定时任务需要重新放回优先队列中。 isRepeat 是通过判断任务中 interval 是否大于 0 判断，

如果大于0 则，表示永久就生效。

防止外部滥用，阻塞定时器协程，框架又一次封装了timer这个包，名为 timer_wapper 这个包,它提供了两种调用方式。

参数和上面的参数一样，只是在第三个参数中使用了任务池，将定时任务放入了任务池中。定时任务的本身执行就是一个 put 操作。

至于put以后，那就是 workers 这个包管理的了。在 worker 包中， 也就是维护了一个任务池，任务池中的任务会有序的执行，方便管理。

平衡二叉树

平衡二叉树的定义:

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定.

问题1:

把一个升序的数组转换成平衡二叉树

对一个二叉搜索树进行中序遍历就可以得到一个升序的数组,那么反过来考虑,数组的中值即为root,然后数组分为左子树和右子树,继续进行递归即可得出结果.

问题2:

给一个二叉树,判断是否是平衡树

首先写计算二叉树高度的函数

树的高度 = max(左子树高度，右子树高度)+1

可以得到高度后对树递归求解每个节点的左右子树的高度差，如果有大于1的，则return False