Eddie Chen


A Front-End Web Developer;

A fakegeek studying at Uestc;

A boy who loves the logic and structure of coding;


Resume

Project List

+

福州金玉堂网站

form 2011 - 2012

福州金玉堂企业网站开发

页面重构, jQuery开发, 基于Ajax的在线聊天子系统, 实时期货价格图表生成(基于Ajax&jsonp)

→ View website

+

diandian.com 数个模板开发

+

中国技术供需在线

form 2011 - 2012

中国技术供需在线-教育部全国高校产学研合作公共服务网络平台

负责一期项目后端开发, 数据库设计

基于PHP, CI框架开发

→ View website

+

电子科技大学校工会新版网站

2011

电子科技大学校工会新版网站

负责后台开发(PHP+CI)以及项目管理

→ View website

+

电子科技大学科技处网站

2010

电子科技大学科技处网站

负责部分页面重构

→ View website

Skill

HTML

80%

CSS & CSS3

70%

Javascript

80%

PHP

60%
*skill scores are based on the test provided by Elance.com.

Blog

恶补基础之数据结构学习笔记--二叉树


前言

陆陆续续看了3天的树, 今天写一篇学习笔记. 本该在上周就完成的, 由于中途一门考试的影响, 断断续续拖到了现在..

看了若干天的线性结构之后, 终于看到树了. 老实说这三年前就该掌握的东西现在才重新开确实有点说不过去.

由于树结构的不确定性, 无论存储和运算都不是很方便, 所以针对树的操作一般都转化成二叉树来做, 二叉树有良好定义的结构, 在存储实现上也比较容易.

二叉树

树这章总体感觉就是一堆定义, 和树相关的一些算法貌似是被丢到了第八章之后了, 过几天才会看到.

二叉树定义(摘自<大话数据结构>)

二叉树是n个节点的有限集合, 该集合或为空集, 或者由一个根节点和两个互不相交的, 分别称为左子树和右子树的二叉树组成.(递归定义)

特殊二叉树
  1. 斜树 - 所有结点都只有右子树或者只有左子树的二叉树
  2. 满二叉树 - 所有分支结点都有左右子树, 且所有叶子都在同一层上
  3. 完全二叉树 - 结点编号和同样深度满二叉树编号位置完全相同
二叉树存储

1.顺序存储

按照结点编号来存, 完全二叉树时有优势.

2.二叉链表

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
二叉树遍历

1.先序遍历 2.后续遍历 3.中序遍历

先,中,后 指的是头结点的顺序.

通过1,3组合 或者 2,3组合可以确定一棵二叉树

线索二叉树

对于链式存储中可能出现的结点闲置, 引入前驱后驱指针, 一方面讲二叉树线索化, 一方面处理掉闲置指针. 再引入两个标志ltag和rtag, 标志左右指针类型.

前驱和后续的指定 由某种次序遍历方法给定

树与森林的转换

树->二叉树

1.加线 - 兄弟结点之间加线 2.去线 - 只保留第一个孩子的线 3.旋转 - 旋转角度构成好看点的二叉树, 第一个孩子是左孩子.

森林->二叉树

1.每棵树转成二叉树 2.第一棵树不动, 第二棵树开始依次把后一棵树的根结点作为前一棵树的根结点右孩子 (根据前面的定义, 树->二叉树的转换中, 根结点总是没有右孩子)

赫夫曼树

结点带权路径长度: 该结点到跟节点之间路径长度*权值 树的带权路径长度WPL: 所有节点的带权路径长度之和

赫夫曼树构造

1.权值从小到大排序 2.取最小的两个组成一棵二叉树,其根结点权值为叶子结点权值之和 3.新二叉树根结点和未操作结点组成新的序列 重复1~的过程

赫夫曼编码

这个倒是N多课程里都学到过, 就不详细写了.


Date:

About

This is Eddie Chen, a front-end web developer, a member of Dreamfly Studio of UESTC.
Keep in touch:
haozi[a,t]haozi.name


Powered by Eddie Chen.