CHAPTER 4
TREES § 1 Preliminaries
1,Terminology
Lineal Tree
Pedigree Tree
( binary tree )
【 Definition】 A tree is a collection of nodes,The collection
can be empty; otherwise,a tree consists of
(1) a distinguished node r,called the root;
(2) and zero or more nonempty (sub)trees T1,,Tk,each of
whose roots are connected by a directed edge from r.
Note:
Subtrees must not connect together,Therefore every
node in the tree is the root of some subtree.
There are edges in a tree with N nodes.
Normally the root is drawn at the top.
N? 1
A
CB D
GFE H I J
MLK
degree of a node,:= number of
subtrees of the node,For example,
degree(A) = 3,degree(F) = 0.
degree of a tree,:=
For example,degree of this tree = 3.
)n o d e(d e g r e em a xt r e en o d e?
leaf ( terminal node ),:= a node with degree 0 (no children).
parent,:= a node that has subtrees.
children,:= the roots of the subtrees of a parent.
siblings,:= children of the same parent.
A
CB D
GFE H I J
MLK
ancestors of a node,:= all the nodes along the path from the
node up to the root.
descendants of a node,:= all the nodes in its subtrees.
depth of ni,:= length of the unique path
from the root to ni,Depth(root) = 0.
height of ni,:= length of the longest path from ni to a leaf,
Height(leaf) = 0,and height(D) = 2.
height (depth) of a tree,:= height(root) = depth(deepest leaf).
path from n1 to nk,:= a (unique) sequence
of nodes n1,n2,…,nk such that ni is the
parent of ni+1 for 1? i < k.
length of path,:= number of edges on
the path.
2,Implementation
List Representation
A
CB D
GFE H I J
MLK
( A )
( A ( B,C,D ) )
( A ( B ( E,F ),C ( G ),D ( H,I,J ) ) )
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) ) )
A
B
C
D
E
F
G
H
I
J
K
L
M
FirstChild-NextSibling Representation
FirstChild NextSibling
Element
A
CB D
GFE H I J
MLK
N
A
CB
N
D
E
N
K
N N
F
N N
G H
N
I
N N
J
N N
L
N N
M
Note,The representation is not unique since the
children in a tree can be of any order.
§ 2 Binary Trees
【 Definition】 A binary tree is a tree in which no node can
have more than two children.
NA
CB ND
E
NK
NNF NNG H NI NNJ
NNL NNM
Rotate the FirstChild-NextSibling tree clockwise by 45?.
45?
Left Right
Element Left
Right
L LR R
Property
Property 1,at the level I of binary tree,there are at
most 2i-1nodes,(i? 1) [prove using induction]
Prove,when i=1,there is only root node,2i-1=2 0=1
Provided to all j,i>j?1,then proposition is right,that
is to say there are at most 2j-1nodes at level j.
From Induction hypothesis,we know that there are
at most 2i-2nodes at level i-1.
Since the degree of every node in binary tree is at
most 2,so the maximum node value of level I is as
twice as the maximum node value of level i-1,
namely 2* 2i － 2= 2 i-1.
Property 2,a binary tree which depth is k
has at most 2 k-1 nodes (k? 1),
Prove,since property 1,maximum node
value of a binary tree which depth is k
k
i
i
1
12
＝ 20 + 21 + … + 2 k-1 = 2 k-1
1
()
k
i
th e m a x im u m n o d e v a l u e o f le v e l i
＝
Property 3,to any binary tree T,if number
of leaves is n0,the number of node
(degree of node is 2) is n2,then n0= n2 +1.
Prove,if the number of node (degree of
node is 1) is n1,the total number of node
is n,the total number of edge is e,then as
the definition of binary tree,
n = n0 + n1 + n2 e = 2n2 + n1 = n – 1
so,there comes 2n2 + n1 = n0 + n1 + n2 -
1
n2 = n0 - 1 n0 = n2 + 1
Definition 1,Full Binary Tree
A binary tree of depth k is called for full binary
tree,if it has 2 k-1 nodes,
Two special forms of binary tree
6
2
1
754
3
8 9 10 11 13 14 1512
Full Binary Tree
2
1
54
3
6 7
2
1
654
3
Not complete binary tree
Definition 2 Complete Binary Tree
If the height of a binary tree is h,then it has h levels,
Except the level h,number of node of the other levels all
reaches the largest,Level h lack several continuous
nodes from right to left,then this is complete binary tree.
6
2
1
754
3
8 9 10 11 12
Complete binary tree
Property 4,the depth of complete binary tree,
which has n (n? 0) nodes,is?log2(n)?＋ 1
Prove,If the depth of complete binary tree is h,
then according to property 2 and the definition
of complete binary tree,there comes
2h－ 1 - 1 < n? 2h－ 1 or 2h－ 1? n < 2h
Logarithm is h－ 1 < log2n? h,since h is
integer,so there comes h =?log2(n)? ＋ 1
Property 5,If there is an n nodes complete binary tree,we
encode the node from top to bottom,left to right using
0,1,2,…,n -1,then there comes such relations,
If i=0,then I has no parents.
If i>0,then the parents of i are (i -1)/2,
If 2*i+1 < n,then the left child of I is 2*i+1,if 2*i+2 < n,
then the right child of I is 2*i+2.
If node number is even,and i!=0,then left brother is i-1.
If node number is odd,and i!=n-1,then right brother is
i+1.
Node I is in level log2(i+1),0
7
1 2
3 4 5 6
8 9
Complete binary tree Commom binary tree
Storage structure of binary tree
1
1 2 3 4 5 6 7 8 910
9
1 2 3 4 0 5 6 7 8 0 0 910
2
4
8 9 10
5 6 7
3
1
2 3
654
7 8
Sequence implementation
910
Linked list implementation
lChild data rChild
data
lChild rChild
Binary linked list
Node structure with two pointers
lChild data parent rChild
parent
data
lChild rChild
Trigeminal List
Node structure with three pointers
Example
A A A
B B B
CCC D D D
FFFE E E
root root root
Binary tree Binary linked list Trigeminal List
Static structure for the Trigeminal List
A
B
C D
FE
root data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
typedef char TreeData; //结点数据类型
typedef struct node { //结点定义
TreeData data;
struct node * leftChild,* rightchild;
} BinTreeNode;
typedef BinTreeNode * BinTree;
//根指针
Definition of binary linked list
Void destroy ( BinTreeNode *current )
{//删除根为 current的子树
if ( current != NULL ) {
destroy ( current -> leftChild );
destroy ( current -> rightChild );
delete current;
}
}
Basic algorithm
BinTreeNode *Parent ( BinTreeNode * start,
BinTreeNode * cuurent )
{//找当前结点的双亲结点，并返回
if ( start == NULL ) return NULL;
if ( start->leftChild == current ||
start->rightChild == current )
return start; //找到
BinTreeNode *p; //否则
if (( p = Parent ( start->leftChild,
current ))!= NULL ) return p; //在左子树中找
else return Parent(start->rightChild,
current); //在右子树中找
}
void BinaryTree Traverse ( BinTreeNode
*current,ostream &out )
{//搜索并输出根为 current的二叉树
if ( current != NULL ) {
out << current->data <<;
Traverse ( current->leftChild,out );
Traverse ( current->rightChild,out );
}
}
INTree ( istream&in,BinaryTree & Tree )
{//输入并建立一棵二叉树 Tree
Type item;
in >> item;
While(item!=RefValue)
{
CreateBinTree ( istream& in,
root );
cout <<,,
in >> item;
}
return in
}
OUTree ( ostream& out,BinaryTree&Tree )
{//输出一棵二叉树 Tree
out <<,二叉树的前序遍历,\n";
Traverse (root,out );
out << endl;
return out;
}
traverse binary tree
Traversal of the tree is visiting the nodes of the tree
as some kind of order,and visit every node only
once.
If we call visiting root node as V
Traverse left subtree of root node as L
Traverse right subtree of root node as R
Then possible traversal order is:
Preorder VLR
Inorder LVR
Postorder LRV
V
L R
The definition of inorder traversal of binary
tree:
If binary tree is null,then operation
null;
Or
inorder traverse left subtree (L)；
visit root node (V)；
inorder traverse right subtree (R)。
Traversal result:
a + b * c - d - e / f
Inorder Traversal
-
-
/+
*a
b
c d
e f
void InOrder ( BinTreeNode *T )
{
if ( T != NULL ) {
InOrder ( T->leftChild );
cout << T->data;
InOrder ( T->rightChild );
}
}
Recursion algorithm of the Inorder Traversal
The definition of preorder traversal of
binary tree:
If binary tree is null,then operation
null;
Or
Visit root node (V)；
preorder traverse left subtree(L)；
preorder traverse right subtree(R)。
Traversal result:
- + a * b - c d / e f
Preorder Traversal
-
-
/+
*a
b
c d
e f
void PreOrder ( BinTreeNode *T ) {
if ( T != NULL ) {
cout << T->data;
PreOrder ( T->leftChild );
PreOrder ( T->rightChild );
}
}
Recursion algorithm of the Preorder Traversal
The definition of postorder traversal of
binary tree:
If binary tree is null,then operation
null;
Or
postorder traverse left subtree(L)；
postorder traverse right subtree(R)；
Visit root node (V)。
Traversal result:
a b c d - * + e f / -
Postorder Traversal
-
-
/+
*a
b
c d
e f
void PostOrder ( BinTreeNode * T ) {
if ( T != NULL ) {
PostOrder ( T->leftChild );
PostOrder ( T->rightChild );
cout << T->data;
}
}
Recursion algorithm of the Postorder Traversal
the application of binary tree traversal
1.Create binary tree as preorder (recursion arithmetic)
Create binary tree recursively
The order you input node value must corresponding to
the order you preorderly create binary tree,And make
an appointment that the value of null node is the value
that cannot appear in the input list,so you can end the
recursion,and this value is in RefValue,For example,
use,@” or,-1” to represent the null node of
character list or positive integer.
The result of binary tree?s Preorder Traversal
A B C @ @ D E @ G @ @ F @ @ @
A
B
C D
E
G
F@ @
@
@ @
@ @
@
void Crt_BinTree ( ifstream& in,BinTreeNode *& T ) {
TreeData x;
if ( !in.eof ( ) ) {
in >> x; //读入根结点的值
if ( x != RefValue ) {
T = new BinTreeNode; //建立根结点
if ( T == NULL ) {
cerr <<,存储分配错 !” << endl;
exit (1);
}
T->data = x;
Crt_BinTree ( in,T->leftChild );
Crt_BinTree ( in,T->rightChild );
}
else T = NULL;
}
}
Create binary tree
void createBinTree ( filename,
BinTreeNode *& Tree )
{//建立一棵二叉树 Tree.
TreeData item;
ifstream fin(filename);//打开文件
if ( !fin )
{ cerr <<,文件未发现 !” << endl;
exit (1);
}
Crt_BinTree ( ifstream& fin,Tree );
fin.close ( );//关闭文件
}
int Count ( BinTreeNode *T ) {
if ( T == NULL ) return 0;
else return 1 + Count ( T->leftChild )
+ Count ( T->rightChild );
}
2,count the number of binary tree?s node
(recursion algorithm)
int Leaf_Count(Bitree T)
{//求二叉树中叶子结点的数目
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1;
//叶子结点
else return Leaf_Count(T-lchild)+Leaf_Count(T-
rchild); //左子树的叶子数加上右子树的叶子数
}
3,count the number of binary tree?s
leaf node
int Height ( BinTreeNode * T )
{
if ( T == NULL ) return -1;
else{
int m = Height ( T->leftChild );
int n = Height ( T->rightChild ) );
return (m > n)? m+1,n+1;
}
}
4,Solve binary tree?s height (recursion
algorithm)
5,Copy binary tree(recursion algorithm)
int Copy( BinTreeNode * T )
{
if ( T == NULL ) return -1;
BinTreeNode * temp=new BinTreeNode;
Temp->data=T->data;
Temp-> leftChild = Copy( T->leftChild );
Temp-> rightChild = Copy(T->rightChild );
return temp;
}
6,Two binary tree is equal or not(recursion
algorithm)
int Equal( BinTreeNode *a,BinTreeNode *b) {
if ( a == NULL && b == NULL ) return 1;
if ( a !== NULL && b !== NULL
&& a->data==b->data
&& equal( a->leftChild,b->leftChild)
&& equal( a->rightChild,b->rightChild) )
return 1;
return 0;//如果 a和 b的子树不等同，则函数返回 0
}
Inorder traversal(not recursion algorithm)
stack implementation
b
a
a
b c
d e
a
d
a a
Push a b Pop b
traverse Push d
Pop d
traverse
Pop e
traverse
e
c c
emptyPop atraverse Push c e Pop ctraverse
void InOrder ( BinTree T ) {
stack S; InitStack( &S ); //递归工作栈
BinTreeNode *p = T; //初始化
while ( p != NULL || !StackEmpty(&S) ) {
if( p != NULL )
{ Push(&S,p); p = p->leftChild; }
if ( !StackEmpty(&S) ) { //栈非空
Pop(&S,p); //退栈
cout << p->data << endl; //访问根
p = p->rightChild;
}//if
}//while
return ok;
}
a
b c
d e
Preorder traversal(not recursion algorithm)
stack implementation
a
cb c
d e
d
c c
traverse
a
push
c
left
b
traverse
b
push
d
left
NULL
pop
d
traverse
d
left
NULL
pop
c
traverse
c
left
e
traverse
e
left
空
pop
end
void PreOrder( BinTree T ) {
stack S; InitStack(&S); //递归工作栈
BinTreeNode * p = T; Push (&S,NULL);
while ( p != NULL ) {
cout << p->data << endl;
if ( p->rightChild != NULL )
Push ( &S,p->rightChild );
if ( p->leftChild != NULL )
p = p->leftChild;//进左子树
else Pop( &S,p );
}
}
a
b c
d e
Definition of StackNode
typedef struct {
BinTreeNode *ptr; //结点指针
enum tag{ L,R }; //该结点退栈标记
} StackNode;
Root
tag = L,meaning is to pop leftchild,traverse rightchild。
tag = R,meaning is to pop rightchild,traverse root。
ptr tag{L,R}
Postorder traversal(not recursion algorithm)
stack implementation
void PostOrder ( BinTree T ) {
stack S; InitStack(&S); StackNode w;
BinTreeNode * p = T;
do {
while ( p != NULL ) { //向左子树走
w.ptr = p; w.tag = L; Push (&S,w);
p = p->leftChild;
}
int continue = 1; //继续循环标记
while ( continue && !StackEmpty(&S) ) {
Pop (&S,w); p = w.ptr;
switch ( w.tag ) { //判断栈顶 tag标记
case L,w.tag = R; Push (&S,w);
continue = 0;
p = p->rightChild; break;
case R,cout << p->data << endl;
}
}
} while ( p != NULL || !StackEmpty(&S) );
cout << endl;
}
practice,swap leftchild for rightchild
(recursion algoritnm)
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
if ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
unknown ( p->rightChild );
}
}
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
while ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
p = p->rightChild;
}
}
Remove the second recursion statement
without stack
Remove two recursion statements with stack
void unknown ( BinTreeNode * T ) {
BinTreeNode *p,*temp;
stack S; InitEmpty (&S);
if ( T != NULL ) {
push(&S,T);
while ( ! StackEmpty(&S) ) {
Pop(&S,p); //栈中退出一个结点
temp = p->leftChild; //交换子女
p->leftChild = p->rightChild;
p->rightChild = temp;
if ( p->rightChild != NULL )
push (&S,p->rightChild );
if ( p->leftChild != NULL )
push (&S,p->leftChild );
}
}
}
〖 Example〗
Directory listing in a hierarchical file system.
Listing format,files that are of depth di will have their names
indented by di tabs.
/usr
mark alex bill
book course hw.c hw.c coursework
ch1.c ch2.c ch3.c cop3530
fall96 spr97 sum97
syl.r syl.r syl.r
cop3212
fall96 fall97
grades gradesp1.r p2.r p1.rp2.r
Unix directory
/usr
mark
book
Ch1.c
Ch2.c
Ch3.c
course
cop3530
fall96
syl.r
spr97
syl.r
sum97
syl.r
hw.c
alex
hw.c
bill
work
course
cop3212
fall96
grades
p1.r
p2.r
fall97
p2.r
p1.r
grades
static void ListDir ( DirOrFile D,int Depth )
{
if ( D is a legitimate entry ) {
PrintName (D,Depth );
if ( D is a directory )
for (each child C of D )
ListDir ( C,Depth + 1 );
}
}
Note,Depth is an internal variable and
must not be seen by the user of this
routine,One solution is to define
another interface function as the
following:
void ListDirectory ( DirOrFile D )
{ ListDir( D,0 ); }
T ( N ) = O( N )
〖 Example〗 Calculating the size of a directory.
/usr
mark alex bill
book course hw.c hw.c coursework
ch1.c ch2.c ch3.c cop3530
fall96 spr97 sum97
syl.r syl.r syl.r
cop3212
fall96 fall97
grades gradesp1.r p2.r p1.rp2.r
Unix directory with file sizes
1
1 1 1
1 1 1 1
1 1
1 1 1 1 1
3 2 4
6 8
1 5 2 3 4 1 2 7 9
static int SizeDir ( DirOrFile D )
{
int TotalSize;
TotalSize = 0;
if ( D is a legitimate entry ) {
TotalSize = FileSize( D );
if ( D is a directory )
for (each child C of D )
TotalSize += SizeDir(C);
} /* end if D is legal */
return TotalSize;
} T ( N ) = O( N )
LeftThread=0,LeftChild is left child pointer
LeftThread=1,LeftChild is preceding pointer
RightThread=0,RightChild is right child pointer
RightThread=1,RightChild is successive pointer
LeftChild RightChilddata
LeftThread RightThread
Threaded Binary Tree(线索化二叉树 )
Node structure
template <class Type> class ThreadNode {
friend class ThreadTree<Type>;
private:
int leftThread,rightThread;
ThreadNode<Type> *leftChild,*rightChild;
Type data;
public:
ThreadNode ( const Type item )
,data (item),leftChild (NULL),
rightChild (NULL),leftThread (0),
rightThread (0) { }
};
C++ Implementation
template <class Type> class ThreadTree;
Definition of Threaded Binary Trees (infix)
Definition of Threaded Binary Trees (infix)
template <class Type> class ThreadTree {
private:
ThreadNode<Type> * root; //根
InThread ( ThreadNode <Type> * current,
ThreadNode <Type> * pre ); //建树
public:
ThreadTree ( ),root (NULL) { }; //构造函数
ThreadNode<Type> *
First ( ThreadNode <Type> * current );
ThreadNode<Type> *
Last ( ThreadNode <Type> * current );
ThreadNode<Type> *
Next ( ThreadNode <Type> * current );
ThreadNode<Type> *
Prior ( ThreadNode <Type> * current );
…………
}
Create Threaded Binary Trees (infix) by
Inorder traversal
template <class Type>
void ThreadTree<Type>,:
InThread ( ThreadNode<Type> * current,
ThreadNode<Type> *& pre ) {
if ( current != NULL ) {
InThread ( current->leftChild,pre );
//递归,左子树线索化
if ( current->leftChild == NULL ) {
current->leftChild = pre;
current->leftThread = 1;
} //建立当前结点的前驱线索
if ( pre != NULL &&
pre->rightChild == NULL ) {
pre->rightChild = current;
pre->rightThread = 1;
} //建立前驱结点的后继线索
pre = current; //前驱跟上当前指针
InThread ( current->rightChild,pre );
//递归,右子树线索化
}
}
+
A?
D
B C
〖 Example〗 Given the syntax tree of an expression (infix)
A + B? C? D
F F
F + F
T A T F? F
F? F T D T
T B T T C T
head node
Storage structure of tree
Parent representation,use a consequent
storage to store tree?s nodes,meanwhile,use a
node?s pointer to denote the position of
parent in the array.
A
B C D
E F G
data
parent
A B C D E F G
-1 0 0 0 1 1 3
0 1 2 3 4 5 6
§ 4 Tree and forest
Definition of tree with parent representation
#define MaxSize//the number of the biggest
pointer
typedef char TreeData; // data of the pointer
typedef struct { //tree pointer definition
TreeData data;
int parent;
} TreeNode;
typedef TreeNode Tree[MaxSize]; //tree
A
B C D
E F G
First child/next sibling representation
First solution,the same number of linked pointers
data child1 child2 child3 childd
A
B C D
E F G
Null pointer number,n(k-1)+1
Node structure data firstChild nextSibling
A
B C D
E F G
N+1 empty linked pointers
Second solution,First child/next sibling representation
（ binary linked list representation）
B
C
D
G
F
E
A?
typedef char TreeData;
typedef struct node {
TreeData data;
struct node *firstChild,*nextSibling;
} TreeNode;
typedef TreeNode * Tree;
Definition of tree with first child/next sibling
representation
T1 T2 T3
T1 T2 T3
A F H
B C D G I J
E K
A F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 trees
Binary tree representation of each tree
Binary tree representation
of forest
Transform trees with forest
Binary tree representation of tree:
Traversal of tree
Depth-first traversal
Root-first traversal
Root-last traversal
A
B C D
E F G
A
B
CE
D
G
F
Depth-first traversal
When the tree is not empty
visit the root
followed by traversing the trees
of every root
Root-first traversal,ABEFCDG
Preorder traversal of the corresponding
binary tree,ABEFCDG
The root-first traversal results is the same
as the results of the preorder traversal of the corresponding
binary tree.
Root-first traversal can use the preorder algorithm of the
corresponding binary tree.
A
B
CE
D
G
F
Root-first traversal
root-last traversal,
When the tree is not empty
followed by root-last traversing the
trees of every root
Visit the root
Root-last traversal,EFBCGDA
Inorder traversal of the corresponding binary tree,
EFBCGDA
The root-last traversal results is the same
as the results of the inorder traversal of the
corresponding binary tree.
Root-last traversal can use the inorder algorithm of the
corresponding binary tree.
A
B
CE
D
G
F
Using the preorder and inorder traversal of
one binary tree can only identify a binary tree.
example,preorder { ABHFDECKG } and
inorder { HBDFAEKCG },the process of
binary tree construction is as follow,
HBDF EKCG
A
EKCG
A
B
H DF
§ 5 Binary Tree count
KCG
EKCG
A
B
H DF
EKCG
A
B
H F
D
E
A
B
H F
D
E
A
B
H F
D
C
K G
If the preorder sequence is fixed,given the
different inorder sequences can receive
different binary trees.
6
1
2
3 4
5
7
8 9
6
1
2
3 7
5
8
4 9
Fix the preorder sequence and choose all
possible inorder sequence,how many of the
binary tree can be constructed?
example,3 data { 1,2,3 },can receive 5
different binary trees,Their preorder
sequences is 123,inorder sequence may be
321,231,213,132,123.
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
T:The number of the trees which have n nodes and
with different forms.
S:the number of the binary trees which have n-1
nodes and are not similar with each other.
T=S
the different trees with 0,1,2 nodes as
follows:
b0 =1 b1 =1 b2 =2
b3 =5
b4 =14
!!
)!(2
1
1
1
1
2 nn
n
nn
b C n nn
Count the number of different trees with
n nodes.
result：
bi bn-i-1
1
1
0
1
n
i
inin bbb
Path Length
The path length (PL) is the number of the
branches between two connected nodes,
The external path (EPL) is the sum of the
distances between root node and each leaf
node.
The internal path (IPL) is the sum of the
distances between root node and each non-
leaf node.
Path length PL = EPL + IPL
§ 6 Huffman Tree
1
2 3
4 5 6 7
8
2 3
4 5
6 7
8External path length of tree
EPL = 3*1+2*3 = 9
External path length of tree
EPL = 1*1+2*1+3*1+4*1 = 10
1
Weighted Path Length,WPL
If leaf node ai is at depth li and weighted value
is wi,then the WPL of tree is equal to
1
0
n
i
ii lwW P L
ii lw
WPL = 2*2+ WPL = 2*1+ WPL = 7*1+
4*2+5*2+ 4*2+5*3+ 5*2+2*3+
7*2 = 36 7*3 = 46 4*3 = 35
2
2
24
4
45 5
5
7
7
7
WPL(external)
is minimum
Huffman Tree
The binary tree with smallest weighted
path length (WPL) is called Huffman tree.
In Huffman tree,the node with bigger
weight is closest to the root node.
(1)Create the forest including N extended B-trees F =
{ T0,T1,T2,…,Tn-1 } with the N given value of weight
{w0,w1,w2,…,wn-1},every extended B-tree Ti has
only one root node with the weight value of wi,and
both of its left child and right child are null.
Huffman algorithm:
(2)Repeat the following steps until there is
only one tree left in F,
① Pick up two B-trees of which the root
has the smallest weight value,Use them as
the left child and right child to create a new
B-tree,Set the value of the new root with the
sum of the two of its child trees.
② Delete the two B-trees from F.
③ Add the new B-tree to F.
F,{7} {5} {2} {4} F,{7} {5} {6}
F,{7} {11}
7 5 2 4
initial union{2} {4}
7 5
2 4
6
F,{18} 11
7 5
2 4
6
union{5} {6}
5
union{7} {11}2
7
4
6
11
18
Process of constructing a Huffman tree
5 27 4
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
Storage structure of the giving example
start
5
2
7
4
6
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
6 -1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
4
4
2 3i
process
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 4 -1 -1
4 4 -1 -1
6 -1 2 3
11 -1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
5
5
1 4i
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 5 -1 -1
2 4 -1 -1
4 4 -1 -1
6 5 2 3
11 -1 1 4
18 -1 -1 -1
0
1
2
3
4
5
6
p1
p2
6
6
0 5i
18
end
const int n = 20;//叶结点数
const int m = 2*n -1;//结点数
typedef struct {
float weight;
int parent,leftChild,rightChild;
} HTNode;
typedef HTNode HuffmanTree[m];
Definition of huffman tree
Create huffman tree
void CreateHuffmanTree ( HuffmanTree T,
float fr[ ] ) {
for ( int i = 0; i < n; i++ )
T[i].weight = fr[i];
for ( i = 0; i < m; i++ ) {
T[i].parent = -1;
T[i].leftChild = -1;
T[i].rightChild = -1;
}
for ( i = n; i < m; i++ ) {
int min1 = min2 = MaxNum;
int pos1,pos2;
for ( int j = 0; j < i; j++ )
if ( T[j].parent == -1 )
if ( T[j].weight < min1 )
{ pos2 = pos1; min2 = min1;
pos1 = j; min1 = T[j].weight;
}
else if ( T[j].weight < min2 )
{ pos2 = j; min2 = T[j].weight; }
T[i].leftChild = pos1;
T[i].rightChild = pos2;
T[i].weight =
T[pos1].weight + T[pos2].weight;
T[pos1].parent = T[pos2].parent = i;
}
}
Best decision tree
Table of examination results
[ 0,6 0 ) [ 6 0,7 0 ) [ 7 0,8 0 ) [ 8 0,9 0 ) [ 9 0,1 0 0 )
不及格 及格 中 良 优
0,1 0 0,15 0,2 5 0,3 5 0,1 5
Decision tree
不及格及格中良 优
<60?
<70?
<80?
<90?
0.10
0.15
0.25
0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4
= 3.15
Best decision tree
不及格 及格中 良 优<60?
<70?
<80?
<90?
0.10 0.15
0.25 0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2
= 0.3+0.45+0.5+0.7+0.3 = 2.25
Huffman Coding
Main use,Data Compression
Given a packet：
CAST CAST SAT AT A TASA
The character set is { C,A,S,T },the
frequency (times) of each character’s
appearance is W＝ { 2,7,4,5 }。
If give every character equal-length code:
A,00 T,10 C,01 S,11
The total length of codes will be ( 2+7+4+5 ) *
2 = 36,
If give different character different code according
to their different appearance frequency,we can
except to shorter the total length of codes.
The frequency of each character is { 2/18,7/18,
4/18,5/18 },change to integer will be { 2,7,4,
5 }.Using them as the weight value of the
corresponding leaf node to create Huffman tree,The
left is supposed to be 0,and the right will be 1,so
we can get the Huffman code.
7 2 5 4
0 1
00 11
A C T S
A,0 T,10 C,110 S,111
Its total length of codes is：
7*1+5*2+( 2+4 )*3 = 35.It’s
shorter than equal-length codes.
The total length of codes exactly
equals the WPL (weighted path
length) of Huffman Tree,
Huffman code is a non-prefix
code,It won’t cause
misunderstand during encoding,Huffman coding tree
0
0
0
1
1
1
2 4
5
7
TREES § 1 Preliminaries
1,Terminology
Lineal Tree
Pedigree Tree
( binary tree )
【 Definition】 A tree is a collection of nodes,The collection
can be empty; otherwise,a tree consists of
(1) a distinguished node r,called the root;
(2) and zero or more nonempty (sub)trees T1,,Tk,each of
whose roots are connected by a directed edge from r.
Note:
Subtrees must not connect together,Therefore every
node in the tree is the root of some subtree.
There are edges in a tree with N nodes.
Normally the root is drawn at the top.
N? 1
A
CB D
GFE H I J
MLK
degree of a node,:= number of
subtrees of the node,For example,
degree(A) = 3,degree(F) = 0.
degree of a tree,:=
For example,degree of this tree = 3.
)n o d e(d e g r e em a xt r e en o d e?
leaf ( terminal node ),:= a node with degree 0 (no children).
parent,:= a node that has subtrees.
children,:= the roots of the subtrees of a parent.
siblings,:= children of the same parent.
A
CB D
GFE H I J
MLK
ancestors of a node,:= all the nodes along the path from the
node up to the root.
descendants of a node,:= all the nodes in its subtrees.
depth of ni,:= length of the unique path
from the root to ni,Depth(root) = 0.
height of ni,:= length of the longest path from ni to a leaf,
Height(leaf) = 0,and height(D) = 2.
height (depth) of a tree,:= height(root) = depth(deepest leaf).
path from n1 to nk,:= a (unique) sequence
of nodes n1,n2,…,nk such that ni is the
parent of ni+1 for 1? i < k.
length of path,:= number of edges on
the path.
2,Implementation
List Representation
A
CB D
GFE H I J
MLK
( A )
( A ( B,C,D ) )
( A ( B ( E,F ),C ( G ),D ( H,I,J ) ) )
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) ) )
A
B
C
D
E
F
G
H
I
J
K
L
M
FirstChild-NextSibling Representation
FirstChild NextSibling
Element
A
CB D
GFE H I J
MLK
N
A
CB
N
D
E
N
K
N N
F
N N
G H
N
I
N N
J
N N
L
N N
M
Note,The representation is not unique since the
children in a tree can be of any order.
§ 2 Binary Trees
【 Definition】 A binary tree is a tree in which no node can
have more than two children.
NA
CB ND
E
NK
NNF NNG H NI NNJ
NNL NNM
Rotate the FirstChild-NextSibling tree clockwise by 45?.
45?
Left Right
Element Left
Right
L LR R
Property
Property 1,at the level I of binary tree,there are at
most 2i-1nodes,(i? 1) [prove using induction]
Prove,when i=1,there is only root node,2i-1=2 0=1
Provided to all j,i>j?1,then proposition is right,that
is to say there are at most 2j-1nodes at level j.
From Induction hypothesis,we know that there are
at most 2i-2nodes at level i-1.
Since the degree of every node in binary tree is at
most 2,so the maximum node value of level I is as
twice as the maximum node value of level i-1,
namely 2* 2i － 2= 2 i-1.
Property 2,a binary tree which depth is k
has at most 2 k-1 nodes (k? 1),
Prove,since property 1,maximum node
value of a binary tree which depth is k
k
i
i
1
12
＝ 20 + 21 + … + 2 k-1 = 2 k-1
1
()
k
i
th e m a x im u m n o d e v a l u e o f le v e l i
＝
Property 3,to any binary tree T,if number
of leaves is n0,the number of node
(degree of node is 2) is n2,then n0= n2 +1.
Prove,if the number of node (degree of
node is 1) is n1,the total number of node
is n,the total number of edge is e,then as
the definition of binary tree,
n = n0 + n1 + n2 e = 2n2 + n1 = n – 1
so,there comes 2n2 + n1 = n0 + n1 + n2 -
1
n2 = n0 - 1 n0 = n2 + 1
Definition 1,Full Binary Tree
A binary tree of depth k is called for full binary
tree,if it has 2 k-1 nodes,
Two special forms of binary tree
6
2
1
754
3
8 9 10 11 13 14 1512
Full Binary Tree
2
1
54
3
6 7
2
1
654
3
Not complete binary tree
Definition 2 Complete Binary Tree
If the height of a binary tree is h,then it has h levels,
Except the level h,number of node of the other levels all
reaches the largest,Level h lack several continuous
nodes from right to left,then this is complete binary tree.
6
2
1
754
3
8 9 10 11 12
Complete binary tree
Property 4,the depth of complete binary tree,
which has n (n? 0) nodes,is?log2(n)?＋ 1
Prove,If the depth of complete binary tree is h,
then according to property 2 and the definition
of complete binary tree,there comes
2h－ 1 - 1 < n? 2h－ 1 or 2h－ 1? n < 2h
Logarithm is h－ 1 < log2n? h,since h is
integer,so there comes h =?log2(n)? ＋ 1
Property 5,If there is an n nodes complete binary tree,we
encode the node from top to bottom,left to right using
0,1,2,…,n -1,then there comes such relations,
If i=0,then I has no parents.
If i>0,then the parents of i are (i -1)/2,
If 2*i+1 < n,then the left child of I is 2*i+1,if 2*i+2 < n,
then the right child of I is 2*i+2.
If node number is even,and i!=0,then left brother is i-1.
If node number is odd,and i!=n-1,then right brother is
i+1.
Node I is in level log2(i+1),0
7
1 2
3 4 5 6
8 9
Complete binary tree Commom binary tree
Storage structure of binary tree
1
1 2 3 4 5 6 7 8 910
9
1 2 3 4 0 5 6 7 8 0 0 910
2
4
8 9 10
5 6 7
3
1
2 3
654
7 8
Sequence implementation
910
Linked list implementation
lChild data rChild
data
lChild rChild
Binary linked list
Node structure with two pointers
lChild data parent rChild
parent
data
lChild rChild
Trigeminal List
Node structure with three pointers
Example
A A A
B B B
CCC D D D
FFFE E E
root root root
Binary tree Binary linked list Trigeminal List
Static structure for the Trigeminal List
A
B
C D
FE
root data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
typedef char TreeData; //结点数据类型
typedef struct node { //结点定义
TreeData data;
struct node * leftChild,* rightchild;
} BinTreeNode;
typedef BinTreeNode * BinTree;
//根指针
Definition of binary linked list
Void destroy ( BinTreeNode *current )
{//删除根为 current的子树
if ( current != NULL ) {
destroy ( current -> leftChild );
destroy ( current -> rightChild );
delete current;
}
}
Basic algorithm
BinTreeNode *Parent ( BinTreeNode * start,
BinTreeNode * cuurent )
{//找当前结点的双亲结点，并返回
if ( start == NULL ) return NULL;
if ( start->leftChild == current ||
start->rightChild == current )
return start; //找到
BinTreeNode *p; //否则
if (( p = Parent ( start->leftChild,
current ))!= NULL ) return p; //在左子树中找
else return Parent(start->rightChild,
current); //在右子树中找
}
void BinaryTree Traverse ( BinTreeNode
*current,ostream &out )
{//搜索并输出根为 current的二叉树
if ( current != NULL ) {
out << current->data <<;
Traverse ( current->leftChild,out );
Traverse ( current->rightChild,out );
}
}
INTree ( istream&in,BinaryTree & Tree )
{//输入并建立一棵二叉树 Tree
Type item;
in >> item;
While(item!=RefValue)
{
CreateBinTree ( istream& in,
root );
cout <<,,
in >> item;
}
return in
}
OUTree ( ostream& out,BinaryTree&Tree )
{//输出一棵二叉树 Tree
out <<,二叉树的前序遍历,\n";
Traverse (root,out );
out << endl;
return out;
}
traverse binary tree
Traversal of the tree is visiting the nodes of the tree
as some kind of order,and visit every node only
once.
If we call visiting root node as V
Traverse left subtree of root node as L
Traverse right subtree of root node as R
Then possible traversal order is:
Preorder VLR
Inorder LVR
Postorder LRV
V
L R
The definition of inorder traversal of binary
tree:
If binary tree is null,then operation
null;
Or
inorder traverse left subtree (L)；
visit root node (V)；
inorder traverse right subtree (R)。
Traversal result:
a + b * c - d - e / f
Inorder Traversal
-
-
/+
*a
b
c d
e f
void InOrder ( BinTreeNode *T )
{
if ( T != NULL ) {
InOrder ( T->leftChild );
cout << T->data;
InOrder ( T->rightChild );
}
}
Recursion algorithm of the Inorder Traversal
The definition of preorder traversal of
binary tree:
If binary tree is null,then operation
null;
Or
Visit root node (V)；
preorder traverse left subtree(L)；
preorder traverse right subtree(R)。
Traversal result:
- + a * b - c d / e f
Preorder Traversal
-
-
/+
*a
b
c d
e f
void PreOrder ( BinTreeNode *T ) {
if ( T != NULL ) {
cout << T->data;
PreOrder ( T->leftChild );
PreOrder ( T->rightChild );
}
}
Recursion algorithm of the Preorder Traversal
The definition of postorder traversal of
binary tree:
If binary tree is null,then operation
null;
Or
postorder traverse left subtree(L)；
postorder traverse right subtree(R)；
Visit root node (V)。
Traversal result:
a b c d - * + e f / -
Postorder Traversal
-
-
/+
*a
b
c d
e f
void PostOrder ( BinTreeNode * T ) {
if ( T != NULL ) {
PostOrder ( T->leftChild );
PostOrder ( T->rightChild );
cout << T->data;
}
}
Recursion algorithm of the Postorder Traversal
the application of binary tree traversal
1.Create binary tree as preorder (recursion arithmetic)
Create binary tree recursively
The order you input node value must corresponding to
the order you preorderly create binary tree,And make
an appointment that the value of null node is the value
that cannot appear in the input list,so you can end the
recursion,and this value is in RefValue,For example,
use,@” or,-1” to represent the null node of
character list or positive integer.
The result of binary tree?s Preorder Traversal
A B C @ @ D E @ G @ @ F @ @ @
A
B
C D
E
G
F@ @
@
@ @
@ @
@
void Crt_BinTree ( ifstream& in,BinTreeNode *& T ) {
TreeData x;
if ( !in.eof ( ) ) {
in >> x; //读入根结点的值
if ( x != RefValue ) {
T = new BinTreeNode; //建立根结点
if ( T == NULL ) {
cerr <<,存储分配错 !” << endl;
exit (1);
}
T->data = x;
Crt_BinTree ( in,T->leftChild );
Crt_BinTree ( in,T->rightChild );
}
else T = NULL;
}
}
Create binary tree
void createBinTree ( filename,
BinTreeNode *& Tree )
{//建立一棵二叉树 Tree.
TreeData item;
ifstream fin(filename);//打开文件
if ( !fin )
{ cerr <<,文件未发现 !” << endl;
exit (1);
}
Crt_BinTree ( ifstream& fin,Tree );
fin.close ( );//关闭文件
}
int Count ( BinTreeNode *T ) {
if ( T == NULL ) return 0;
else return 1 + Count ( T->leftChild )
+ Count ( T->rightChild );
}
2,count the number of binary tree?s node
(recursion algorithm)
int Leaf_Count(Bitree T)
{//求二叉树中叶子结点的数目
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1;
//叶子结点
else return Leaf_Count(T-lchild)+Leaf_Count(T-
rchild); //左子树的叶子数加上右子树的叶子数
}
3,count the number of binary tree?s
leaf node
int Height ( BinTreeNode * T )
{
if ( T == NULL ) return -1;
else{
int m = Height ( T->leftChild );
int n = Height ( T->rightChild ) );
return (m > n)? m+1,n+1;
}
}
4,Solve binary tree?s height (recursion
algorithm)
5,Copy binary tree(recursion algorithm)
int Copy( BinTreeNode * T )
{
if ( T == NULL ) return -1;
BinTreeNode * temp=new BinTreeNode;
Temp->data=T->data;
Temp-> leftChild = Copy( T->leftChild );
Temp-> rightChild = Copy(T->rightChild );
return temp;
}
6,Two binary tree is equal or not(recursion
algorithm)
int Equal( BinTreeNode *a,BinTreeNode *b) {
if ( a == NULL && b == NULL ) return 1;
if ( a !== NULL && b !== NULL
&& a->data==b->data
&& equal( a->leftChild,b->leftChild)
&& equal( a->rightChild,b->rightChild) )
return 1;
return 0;//如果 a和 b的子树不等同，则函数返回 0
}
Inorder traversal(not recursion algorithm)
stack implementation
b
a
a
b c
d e
a
d
a a
Push a b Pop b
traverse Push d
Pop d
traverse
Pop e
traverse
e
c c
emptyPop atraverse Push c e Pop ctraverse
void InOrder ( BinTree T ) {
stack S; InitStack( &S ); //递归工作栈
BinTreeNode *p = T; //初始化
while ( p != NULL || !StackEmpty(&S) ) {
if( p != NULL )
{ Push(&S,p); p = p->leftChild; }
if ( !StackEmpty(&S) ) { //栈非空
Pop(&S,p); //退栈
cout << p->data << endl; //访问根
p = p->rightChild;
}//if
}//while
return ok;
}
a
b c
d e
Preorder traversal(not recursion algorithm)
stack implementation
a
cb c
d e
d
c c
traverse
a
push
c
left
b
traverse
b
push
d
left
NULL
pop
d
traverse
d
left
NULL
pop
c
traverse
c
left
e
traverse
e
left
空
pop
end
void PreOrder( BinTree T ) {
stack S; InitStack(&S); //递归工作栈
BinTreeNode * p = T; Push (&S,NULL);
while ( p != NULL ) {
cout << p->data << endl;
if ( p->rightChild != NULL )
Push ( &S,p->rightChild );
if ( p->leftChild != NULL )
p = p->leftChild;//进左子树
else Pop( &S,p );
}
}
a
b c
d e
Definition of StackNode
typedef struct {
BinTreeNode *ptr; //结点指针
enum tag{ L,R }; //该结点退栈标记
} StackNode;
Root
tag = L,meaning is to pop leftchild,traverse rightchild。
tag = R,meaning is to pop rightchild,traverse root。
ptr tag{L,R}
Postorder traversal(not recursion algorithm)
stack implementation
void PostOrder ( BinTree T ) {
stack S; InitStack(&S); StackNode w;
BinTreeNode * p = T;
do {
while ( p != NULL ) { //向左子树走
w.ptr = p; w.tag = L; Push (&S,w);
p = p->leftChild;
}
int continue = 1; //继续循环标记
while ( continue && !StackEmpty(&S) ) {
Pop (&S,w); p = w.ptr;
switch ( w.tag ) { //判断栈顶 tag标记
case L,w.tag = R; Push (&S,w);
continue = 0;
p = p->rightChild; break;
case R,cout << p->data << endl;
}
}
} while ( p != NULL || !StackEmpty(&S) );
cout << endl;
}
practice,swap leftchild for rightchild
(recursion algoritnm)
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
if ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
unknown ( p->rightChild );
}
}
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
while ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
p = p->rightChild;
}
}
Remove the second recursion statement
without stack
Remove two recursion statements with stack
void unknown ( BinTreeNode * T ) {
BinTreeNode *p,*temp;
stack S; InitEmpty (&S);
if ( T != NULL ) {
push(&S,T);
while ( ! StackEmpty(&S) ) {
Pop(&S,p); //栈中退出一个结点
temp = p->leftChild; //交换子女
p->leftChild = p->rightChild;
p->rightChild = temp;
if ( p->rightChild != NULL )
push (&S,p->rightChild );
if ( p->leftChild != NULL )
push (&S,p->leftChild );
}
}
}
〖 Example〗
Directory listing in a hierarchical file system.
Listing format,files that are of depth di will have their names
indented by di tabs.
/usr
mark alex bill
book course hw.c hw.c coursework
ch1.c ch2.c ch3.c cop3530
fall96 spr97 sum97
syl.r syl.r syl.r
cop3212
fall96 fall97
grades gradesp1.r p2.r p1.rp2.r
Unix directory
/usr
mark
book
Ch1.c
Ch2.c
Ch3.c
course
cop3530
fall96
syl.r
spr97
syl.r
sum97
syl.r
hw.c
alex
hw.c
bill
work
course
cop3212
fall96
grades
p1.r
p2.r
fall97
p2.r
p1.r
grades
static void ListDir ( DirOrFile D,int Depth )
{
if ( D is a legitimate entry ) {
PrintName (D,Depth );
if ( D is a directory )
for (each child C of D )
ListDir ( C,Depth + 1 );
}
}
Note,Depth is an internal variable and
must not be seen by the user of this
routine,One solution is to define
another interface function as the
following:
void ListDirectory ( DirOrFile D )
{ ListDir( D,0 ); }
T ( N ) = O( N )
〖 Example〗 Calculating the size of a directory.
/usr
mark alex bill
book course hw.c hw.c coursework
ch1.c ch2.c ch3.c cop3530
fall96 spr97 sum97
syl.r syl.r syl.r
cop3212
fall96 fall97
grades gradesp1.r p2.r p1.rp2.r
Unix directory with file sizes
1
1 1 1
1 1 1 1
1 1
1 1 1 1 1
3 2 4
6 8
1 5 2 3 4 1 2 7 9
static int SizeDir ( DirOrFile D )
{
int TotalSize;
TotalSize = 0;
if ( D is a legitimate entry ) {
TotalSize = FileSize( D );
if ( D is a directory )
for (each child C of D )
TotalSize += SizeDir(C);
} /* end if D is legal */
return TotalSize;
} T ( N ) = O( N )
LeftThread=0,LeftChild is left child pointer
LeftThread=1,LeftChild is preceding pointer
RightThread=0,RightChild is right child pointer
RightThread=1,RightChild is successive pointer
LeftChild RightChilddata
LeftThread RightThread
Threaded Binary Tree(线索化二叉树 )
Node structure
template <class Type> class ThreadNode {
friend class ThreadTree<Type>;
private:
int leftThread,rightThread;
ThreadNode<Type> *leftChild,*rightChild;
Type data;
public:
ThreadNode ( const Type item )
,data (item),leftChild (NULL),
rightChild (NULL),leftThread (0),
rightThread (0) { }
};
C++ Implementation
template <class Type> class ThreadTree;
Definition of Threaded Binary Trees (infix)
Definition of Threaded Binary Trees (infix)
template <class Type> class ThreadTree {
private:
ThreadNode<Type> * root; //根
InThread ( ThreadNode <Type> * current,
ThreadNode <Type> * pre ); //建树
public:
ThreadTree ( ),root (NULL) { }; //构造函数
ThreadNode<Type> *
First ( ThreadNode <Type> * current );
ThreadNode<Type> *
Last ( ThreadNode <Type> * current );
ThreadNode<Type> *
Next ( ThreadNode <Type> * current );
ThreadNode<Type> *
Prior ( ThreadNode <Type> * current );
…………
}
Create Threaded Binary Trees (infix) by
Inorder traversal
template <class Type>
void ThreadTree<Type>,:
InThread ( ThreadNode<Type> * current,
ThreadNode<Type> *& pre ) {
if ( current != NULL ) {
InThread ( current->leftChild,pre );
//递归,左子树线索化
if ( current->leftChild == NULL ) {
current->leftChild = pre;
current->leftThread = 1;
} //建立当前结点的前驱线索
if ( pre != NULL &&
pre->rightChild == NULL ) {
pre->rightChild = current;
pre->rightThread = 1;
} //建立前驱结点的后继线索
pre = current; //前驱跟上当前指针
InThread ( current->rightChild,pre );
//递归,右子树线索化
}
}
+
A?
D
B C
〖 Example〗 Given the syntax tree of an expression (infix)
A + B? C? D
F F
F + F
T A T F? F
F? F T D T
T B T T C T
head node
Storage structure of tree
Parent representation,use a consequent
storage to store tree?s nodes,meanwhile,use a
node?s pointer to denote the position of
parent in the array.
A
B C D
E F G
data
parent
A B C D E F G
-1 0 0 0 1 1 3
0 1 2 3 4 5 6
§ 4 Tree and forest
Definition of tree with parent representation
#define MaxSize//the number of the biggest
pointer
typedef char TreeData; // data of the pointer
typedef struct { //tree pointer definition
TreeData data;
int parent;
} TreeNode;
typedef TreeNode Tree[MaxSize]; //tree
A
B C D
E F G
First child/next sibling representation
First solution,the same number of linked pointers
data child1 child2 child3 childd
A
B C D
E F G
Null pointer number,n(k-1)+1
Node structure data firstChild nextSibling
A
B C D
E F G
N+1 empty linked pointers
Second solution,First child/next sibling representation
（ binary linked list representation）
B
C
D
G
F
E
A?
typedef char TreeData;
typedef struct node {
TreeData data;
struct node *firstChild,*nextSibling;
} TreeNode;
typedef TreeNode * Tree;
Definition of tree with first child/next sibling
representation
T1 T2 T3
T1 T2 T3
A F H
B C D G I J
E K
A F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 trees
Binary tree representation of each tree
Binary tree representation
of forest
Transform trees with forest
Binary tree representation of tree:
Traversal of tree
Depth-first traversal
Root-first traversal
Root-last traversal
A
B C D
E F G
A
B
CE
D
G
F
Depth-first traversal
When the tree is not empty
visit the root
followed by traversing the trees
of every root
Root-first traversal,ABEFCDG
Preorder traversal of the corresponding
binary tree,ABEFCDG
The root-first traversal results is the same
as the results of the preorder traversal of the corresponding
binary tree.
Root-first traversal can use the preorder algorithm of the
corresponding binary tree.
A
B
CE
D
G
F
Root-first traversal
root-last traversal,
When the tree is not empty
followed by root-last traversing the
trees of every root
Visit the root
Root-last traversal,EFBCGDA
Inorder traversal of the corresponding binary tree,
EFBCGDA
The root-last traversal results is the same
as the results of the inorder traversal of the
corresponding binary tree.
Root-last traversal can use the inorder algorithm of the
corresponding binary tree.
A
B
CE
D
G
F
Using the preorder and inorder traversal of
one binary tree can only identify a binary tree.
example,preorder { ABHFDECKG } and
inorder { HBDFAEKCG },the process of
binary tree construction is as follow,
HBDF EKCG
A
EKCG
A
B
H DF
§ 5 Binary Tree count
KCG
EKCG
A
B
H DF
EKCG
A
B
H F
D
E
A
B
H F
D
E
A
B
H F
D
C
K G
If the preorder sequence is fixed,given the
different inorder sequences can receive
different binary trees.
6
1
2
3 4
5
7
8 9
6
1
2
3 7
5
8
4 9
Fix the preorder sequence and choose all
possible inorder sequence,how many of the
binary tree can be constructed?
example,3 data { 1,2,3 },can receive 5
different binary trees,Their preorder
sequences is 123,inorder sequence may be
321,231,213,132,123.
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
T:The number of the trees which have n nodes and
with different forms.
S:the number of the binary trees which have n-1
nodes and are not similar with each other.
T=S
the different trees with 0,1,2 nodes as
follows:
b0 =1 b1 =1 b2 =2
b3 =5
b4 =14
!!
)!(2
1
1
1
1
2 nn
n
nn
b C n nn
Count the number of different trees with
n nodes.
result：
bi bn-i-1
1
1
0
1
n
i
inin bbb
Path Length
The path length (PL) is the number of the
branches between two connected nodes,
The external path (EPL) is the sum of the
distances between root node and each leaf
node.
The internal path (IPL) is the sum of the
distances between root node and each non-
leaf node.
Path length PL = EPL + IPL
§ 6 Huffman Tree
1
2 3
4 5 6 7
8
2 3
4 5
6 7
8External path length of tree
EPL = 3*1+2*3 = 9
External path length of tree
EPL = 1*1+2*1+3*1+4*1 = 10
1
Weighted Path Length,WPL
If leaf node ai is at depth li and weighted value
is wi,then the WPL of tree is equal to
1
0
n
i
ii lwW P L
ii lw
WPL = 2*2+ WPL = 2*1+ WPL = 7*1+
4*2+5*2+ 4*2+5*3+ 5*2+2*3+
7*2 = 36 7*3 = 46 4*3 = 35
2
2
24
4
45 5
5
7
7
7
WPL(external)
is minimum
Huffman Tree
The binary tree with smallest weighted
path length (WPL) is called Huffman tree.
In Huffman tree,the node with bigger
weight is closest to the root node.
(1)Create the forest including N extended B-trees F =
{ T0,T1,T2,…,Tn-1 } with the N given value of weight
{w0,w1,w2,…,wn-1},every extended B-tree Ti has
only one root node with the weight value of wi,and
both of its left child and right child are null.
Huffman algorithm:
(2)Repeat the following steps until there is
only one tree left in F,
① Pick up two B-trees of which the root
has the smallest weight value,Use them as
the left child and right child to create a new
B-tree,Set the value of the new root with the
sum of the two of its child trees.
② Delete the two B-trees from F.
③ Add the new B-tree to F.
F,{7} {5} {2} {4} F,{7} {5} {6}
F,{7} {11}
7 5 2 4
initial union{2} {4}
7 5
2 4
6
F,{18} 11
7 5
2 4
6
union{5} {6}
5
union{7} {11}2
7
4
6
11
18
Process of constructing a Huffman tree
5 27 4
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
Storage structure of the giving example
start
5
2
7
4
6
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
6 -1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
4
4
2 3i
process
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 4 -1 -1
4 4 -1 -1
6 -1 2 3
11 -1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
5
5
1 4i
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 5 -1 -1
2 4 -1 -1
4 4 -1 -1
6 5 2 3
11 -1 1 4
18 -1 -1 -1
0
1
2
3
4
5
6
p1
p2
6
6
0 5i
18
end
const int n = 20;//叶结点数
const int m = 2*n -1;//结点数
typedef struct {
float weight;
int parent,leftChild,rightChild;
} HTNode;
typedef HTNode HuffmanTree[m];
Definition of huffman tree
Create huffman tree
void CreateHuffmanTree ( HuffmanTree T,
float fr[ ] ) {
for ( int i = 0; i < n; i++ )
T[i].weight = fr[i];
for ( i = 0; i < m; i++ ) {
T[i].parent = -1;
T[i].leftChild = -1;
T[i].rightChild = -1;
}
for ( i = n; i < m; i++ ) {
int min1 = min2 = MaxNum;
int pos1,pos2;
for ( int j = 0; j < i; j++ )
if ( T[j].parent == -1 )
if ( T[j].weight < min1 )
{ pos2 = pos1; min2 = min1;
pos1 = j; min1 = T[j].weight;
}
else if ( T[j].weight < min2 )
{ pos2 = j; min2 = T[j].weight; }
T[i].leftChild = pos1;
T[i].rightChild = pos2;
T[i].weight =
T[pos1].weight + T[pos2].weight;
T[pos1].parent = T[pos2].parent = i;
}
}
Best decision tree
Table of examination results
[ 0,6 0 ) [ 6 0,7 0 ) [ 7 0,8 0 ) [ 8 0,9 0 ) [ 9 0,1 0 0 )
不及格 及格 中 良 优
0,1 0 0,15 0,2 5 0,3 5 0,1 5
Decision tree
不及格及格中良 优
<60?
<70?
<80?
<90?
0.10
0.15
0.25
0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4
= 3.15
Best decision tree
不及格 及格中 良 优<60?
<70?
<80?
<90?
0.10 0.15
0.25 0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2
= 0.3+0.45+0.5+0.7+0.3 = 2.25
Huffman Coding
Main use,Data Compression
Given a packet：
CAST CAST SAT AT A TASA
The character set is { C,A,S,T },the
frequency (times) of each character’s
appearance is W＝ { 2,7,4,5 }。
If give every character equal-length code:
A,00 T,10 C,01 S,11
The total length of codes will be ( 2+7+4+5 ) *
2 = 36,
If give different character different code according
to their different appearance frequency,we can
except to shorter the total length of codes.
The frequency of each character is { 2/18,7/18,
4/18,5/18 },change to integer will be { 2,7,4,
5 }.Using them as the weight value of the
corresponding leaf node to create Huffman tree,The
left is supposed to be 0,and the right will be 1,so
we can get the Huffman code.
7 2 5 4
0 1
00 11
A C T S
A,0 T,10 C,110 S,111
Its total length of codes is：
7*1+5*2+( 2+4 )*3 = 35.It’s
shorter than equal-length codes.
The total length of codes exactly
equals the WPL (weighted path
length) of Huffman Tree,
Huffman code is a non-prefix
code,It won’t cause
misunderstand during encoding,Huffman coding tree
0
0
0
1
1
1
2 4
5
7
