树和二叉树

  • 树的结点包含一个数据元素以及若干个指向其子树的分支。
  • 结点拥有的子树数称为结点的度(degree).
  • 度为0的结点称为叶子(leaf)或终端结点。度不为0的结点称为非终端结点或分支结点。
  • 除根节点以外,分支结点也称为内部结点。
  • 树的度是树内各结点的度的最大值。
  • 结点的子树的根称为该结点的孩纸,相应的,该结点称为孩子的双亲(parent).
  • 树中结点的最大层次称为树的深度(depth)或者高度。
  • 如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。
  • 森林(forest)是多颗互不相交的树的集合。

    二叉树 binary tree

性质

  1. 在二叉树的第i层上至多有2的(i-1)次方个结点
  2. 深度为k的二叉树至多有2的k次方-1个结点。
  3. 对任何一颗二叉树,如果其终端结点个数为n0,度为2的结点个数为n2,则n0=n2+1;(推导:n=n0+n1+n2,n=1+2n2+n1)
  4. 具有n个结点的完全二叉树的深度为[log2-n]+1

满二叉树 一颗深度为k且有2的k次方-1个结点的二叉树称为满二叉树。

完全二叉树

可以对满二叉树的结点进行编号,约定编号从根节点起,自上而下,自左至右。 由此可以引出完全二叉树的定义:深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。

二叉树的存储结构

  1. 顺序存储结构

用一组地址连续的存储单元依次自上而下,自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。 对于一般二叉树。则应将其每个结点与完全二叉树上的结点相对照,存储在一维数组的相应分量中,0表示不存在此结点。

  1. 链式存储结构

二叉链表(数据域,左,右指针域)或者三叉链表(多一个指向双亲结点的链域)。

遍历二叉树

构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
function BinaryNode(value,leftChild,rightChild){
this.value=value;
this.lChild=leftChild;
this.rChild=rightChild;
}
var binaryTree = new BinaryNode("-");
binaryTree.leftChild = new BinaryNode("10");
binaryTree.rightChild = new BinaryNode("7");
function visit(binaryNode){
if (binaryNode.value) {
console.log(binaryNode.value);
}
}

递归先序遍历

1
2
3
4
5
6
7
8
preOrderVisit(binaryTree);
function preOrderVisit(binaryTree){
if (binaryTree) {
visit(binaryTree);
preOrderVisit(binaryTree.leftChild);
preOrderVisit(binaryTree.rightChild);
}
}

非递归中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function InorderVisit(binaryTree){
var stack = [];
stack.push(binaryTree);
while (stack.length) {
while (stack[stack.length-1]) {
stack.push(stack[stack.length-1].leftChild);
}
stack.pop();
if (stack.length) {
var tmp = stack.pop();
visit(tmp);
stack.push(tmp.rightChild);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
function InorderVisit(binaryTree){
var stack = [],
tmp = binaryTree;
while (tmp || stack.length) {
if (tmp) {
stack.push(tmp);tmp = tmp.leftChild;
}else{
tmp = stack.pop();
visit(tmp);
tmp = tmp.rightChild;
}
}
}

制造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//空格用来退出createBiTree
var valArr = [0,1,2,"","","",3,4,"",5,"","",6,"","",""];
function createBiTree(){ //按照先序遍历制造二叉树
while (valArr.length) {
var binaryNode;
var tmp = valArr.shift();
if (tmp !== "") {
binaryNode = new BinaryNode(tmp);
binaryNode.leftChild = createBiTree(binaryNode.leftChild);
binaryNode.rightChild = createBiTree(binaryNode.rightChild);
}else {
return null;
}
return binaryNode;
}
}
var test = createBiTree();

线索二叉树 thread binary tree

从上节的讨论可知,遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列。这实质上是一个非线性结构进行线性化操作,使每个结点(除第一个与最后一个)在这些线性序列中有且仅有一个直接前驱和直接后继。 但是,当以二叉链表为结构存储二叉树时,只能找到结点的左右孩子结点,而不能直接得到任一结点的直接前驱和后继。

解决方案 原理:在有n个结点二叉树中必然会有n+1个空链域,利用这n+1个空链域存储前继后继信息。 故可以在左右孩子指针上新增一个布尔值标识,当左链域指向左孩子结点时为0,当指向前区时为1。 以这种结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表。

中序遍历双向线索表

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
function BinaryThrNode(obj) {
this.val = obj.value || null;
this.lChild = obj.lChild || null;
this.lTag = obj.lTage || 0; //0表示指向结点,1表示线索
this.rChild = obj.rChild || null;
this.rTag = obj.rTag || 0;
}
function visit(binaryNode){
if (binaryNode.val) {
console.log(binaryNode.val);
}
}
// 对双向线索表进行中序遍历
function InOrderTraverse(biThrTree){ //biThrTree指向头结点
var tmp = biThrTree.lChild;
while (tmp!==biThrTree) {
while (!tmp.lTag) {
tmp = tmp.lChild;
}
visit(tmp);
while (tmp.rTag && tmp!==biThrTree) {
tmp=tmp.rChild;
visit(tmp);
}
tmp=tmp.rChild;
}
return biThrTree;
}

线索化二叉树

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
//线索化二叉树
function InOrderThreading(biThrTree,biTree){
biThrTree = new BinaryThrNode();
biThrTree.lChild = biTree;
biThrTree.rTag = 1;
biThrTree.rChild = biThrTree;
if (!biTree) {
biThrTree.lTag = 1;
biThrTree.lChild = biThrTree;
}else {
biThrTree.lChild = biTree;
var pre = biThrTree;
InThreading(biTree);
pre.rChild = biThrTree;
pre.rTag = 1;
biThrTree.rChild = pre;
}
return biThrTree;
}
function InThreading(binaryNode){
if (binaryNode) {
InThreading(binaryNode.lChild);
if (!binaryNode.lChild) {
binaryNode.lTag = 1;
p.lChild = pre;
}
if (!pre.rChild) {
pre.rTag = 1;
pre.rChild = binaryNode;
}
InThreading(binaryNode.rChild);
}
}

赫夫曼树及其应用

赫夫曼树又称最优树,是一种带权路径长度最短的树。

最优二叉树

树的路径长度是从树的根到每一个结点长度的和。 树的带权路径长度为树中所有叶子结点的带权路径长度之和。

  • 根据n个权值{w1, w2, ⋯,wn},构造成n棵二叉树的集合F={T1, T2, ⋯,Tn},其中每棵二叉树只有一个权值为wi的根结点,没有左、右子树;
  • 在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树,且新的二叉树根结点权值为其左、右子树根结点的权值之和;
  • 在F中删除这两棵树,同时将新得到的树加入F中;
  • 重复2,3,直到F只含一棵树为止。

构造Huffman树时,为了规范,规定F={T1,T2, ⋯,Tn}中权值小的二叉树作为新构造的二叉树的左子树,权值大的二叉树作为新构造的二叉树的右子树;在取值相等时,深度小的二叉树作为新构造的二叉树的左子树,深度大的二叉树作为新构造的二叉树的右子树。

赫夫曼编码

若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称为前缀编码。

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
// 赫夫曼树和赫夫曼编码的存储结构
function HuffmanNode(weight, parent, leftChild, rightChild) {
this.weight = weight || 0;
this.parent = parent || 0;
this.leftChild = leftChild || 0;
this.rightChild = rightChild || 0;
}
// 创建一棵叶子结点数为n的Huffman树
function buildHuffmanTree(weights, n) {
n = n || weights.length;
var m = 2 * n - 1;
var huffmanTree = [];
// 初始化
for (var i = 0; i < n; i++)
huffmanTree[i] = new HuffmanNode(weights[i], 0, 0, 0);
for (; i < m; i++)
huffmanTree[i] = new HuffmanNode(0, 0, 0, 0);
for (i = n; i < m; i++) {
// 在HT[1..i-1]选择parent为0且weight最小的两个结点,返回其序号为[s1, s2]
var ret = select(huffmanTree, i);
var s1 = ret[0];
var s2 = ret[1];
huffmanTree[s1].parent = i;
huffmanTree[s2].parent = i;
huffmanTree[i].leftChild = s1;
huffmanTree[i].rightChild = s2;
huffmanTree[i].weight = huffmanTree[s1].weight + huffmanTree[s2].weight;
}
return huffmanTree;
}
function select(huffmanTree, len) {
var ret = [];
for (var i = 0; i < len; i++) {
var node = huffmanTree[i];
if (node.parent !== 0) continue;
if (ret.length < 2) {
ret.push(i);
} else {
var index = huffmanTree[ret[0]].weight > huffmanTree[ret[1]].weight ? 0 : 1;
if (node.weight < huffmanTree[ret[index]].weight)
ret[index] = i;
}
}
if (ret[0] > ret[1]) {
var temp = ret[0];
ret[0] = ret[1];
ret[1] = temp;
}
return ret;
}

参考资料

  1. javascript实现数据结构: 树和二叉树,二叉树的遍历和基本操作
  2. 树和二叉树的应用
分享 留言