# Data Structure

## Tree

### Definition

One natural way to define a tree is recursively.

A tree is a collection of nodes. The collection can be empty;

otherwise, a tree consists of a distinguished node r,called root, and zero or more nonempty (sub)trees $T_1, T_2, … T_k$, each of whose roots are connected by a direct edge from r.

### Terminology

Parent: Node A is the parent of node B, if B is the root of one subtree of A.

Child: Node B is the child of node A, if A is the parent of B.

Sibling:Nodes with the same parent are siblings

Leaf:A node is called a leaf if it has no children.

Branch Node(OR internal node):Any node of a tree that has child nodes(the number of child nodes is more than 0)

Ancestor: Node A is an ancestor of node B,if A is either the parent of B or is the parent of some ancestor of B.

Descendant: Node B is the descendant of node A, if A is an ancestor of node B.

Level of a Node:Level of the root of a tree is 1, and the level of any other nodes in the tree is one more than the level of its parent

Depth of a Tree:The depth of a tree is the maximum level of any leaf in the tree (also called the height of a tree).

Degree of a node:The number of children of a node.

Degree of a tree:The max-degree of the node of a tree.

{

 1 2 3 4 5 6 7 8  ADT Tree{Data objects :{D = {ai| ai∈ElementSet, (i=1,2,…,n, n≥0)} Relationships of Data Elements:{ Recursive Definition of a tree } Basic Operations: INITTREE（＆T）； DESTROYTREE（＆T）； …… 

### Operations

{

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  INITTREE(＆T); DESTROYTREE(＆T); CREATETREE(＆T，DEFINITION); CLEARTREE(＆T); TREEEMPTY(T); TREEDEPTH(T); ROOT(T); ASSIGN(T，CUR_E，VALUE); PARENT(T，CUR_E); LEFTCHILD(T，CUR_E); RIGHTSIBLING(T，CUR_E); INSERTCHILD(＆T，＆P，i，C)； DELETECHILD(＆T，＆P，i)； TRAVERSETREE(T，VISIT())； ...... 

}

Emphasis

!!!A binary tree is a tree in which no node can have more than two children.

Five kinds of forms

1. Empty binary tree
2. Binary tree with only one node
3. Binary without any right tree
4. Binary with left and right trees
5. Binary tree with no left tree

### Full Binary Tree

A full binary tree of depth k is a binary tree of depth k having $2^k-1$ nodes

### Complete Binary Tree

A complete binary tree: a binary tree with n nodes and depth k is complete if its nodes correspond to the nodes numbered from 1 to n in the full binary tree of depth k

### Properties of binary trees

#### Maximum number of nodes

Maximum number of nodes

1. $The\ maximum\ number\ of\ nodes\ on\ level\ i\ of\ a\ binary\ tree\ is\ 2^{i-1}, i\geq 1$
2. $The\ maximum\ number\ of\ nodes\ in\ a\ binary\ tree\ of\ depth\ k\ is\ 2^{k-1}, k\geq 1.(\sum^{k-1}_02^k = 2^k - 1)$

Relation between number of leaf nodes and degree-2 nodes

For any nonempty binary tree T, if $n_0$ is the number of leaf nodes and $n_2$ is the number of nodes of degree 2,then $n_0 = n_2 + 1(n_0 = 2^{i-1}\ and\ n_2 = 2^{i - 1} - 1)$

!!!The height（depth）of a [complete binary tree] with n nodes is $\lfloor\log_2n\rfloor + 1$

$2^{k-1}-1 < n \leq 2^k – 1$

$2^{k-1}\leq n < 2^k$

$k-1\leq \log_2n <k$

$k=\lfloor\log_2n\rfloor + 1$

If a complete binary tree with n nodes is represented sequentially, then for any node with index i, $1 \leq i \leq n$,we have

1. parent(i) is at $\lfloor\frac{i}{2}\rfloor$ if $i \not= 1$. If i = 1, i is the root and has no parent.
2. LeftChild(i) is at $2i$ if $2i \leq n$. If $2i > n$, then i has no left child
3. RightChild(i) is at $2i+1$ if $2i+1 \leq n$. If $2i +1 > n$, then i has no right child

### Array implementation of stacks

Too much memory is wasted!

#### Linked implement of Binary Tree

 1 2 3 4  typedef struct BiTNode { // Node structure TElemType data; struct BiTNode *lchild, *rchild; // left, right child pointer } BiTNode, *BiTree; 

CreateBinTree

  1 2 3 4 5 6 7 8 9 10 11 12 13  Status CreateBiTree(BiTree &T) { scanf(“%c”,&ch); // ABDG###E##C#F## if (ch == ‘#’) T = NULL; else { if (!(T = (BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; }//CreateBiTree 

 1 2 3 4 5  typedef struct TriTNode { // Node TElemType data; struct TriTNode *lchild, *rchild; // Left & Right Children struct TriTNode *parent; //Parent } TriTNode, *TriTree; 

#### Application of Binary Trees: Expression Trees

$(a+b * c)+((d * e+f) * g)$

Algorithm to convert postfix expression into expression tree

Read the expression one symbol at a time

1. If symbols are operands, build a single node tree and push it on the stack
2. If the symbol is an operator, then two trees, T1 and T2, are popped from the stack (T1 is popped first) and a new tree is formed whose root is the operator and whose left and right children are T2 and T1, respectively
3. And then push the pointer to the tree on the stack

### Preliminaries: Traversal Strategy

#### preorder traversal strategy

  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  //recursive template void BinTree::preorderTraverse(BinNodePosi root, void (*visit)(T &)) { if (root == nullptr) return; visit(root->data); preorderTraverse(root->leftChild, visit); preorderTraverse(root->rightChild, visit); } //no recursive template void BinaryTree::visitAlongVine(BinNodePosi x, void (*visit)(T &), std::stack> &stack) { while (x != nullptr) { visit(x->data); stack.push(x->rightChild); x = x->leftChild; } } template void BinaryTree::preorderTraverse(BinNodePosi root, void (*visit)(T &)) { std::stack> stack{}; while (true) { visitAlongVine(root, visit, stack); if (stack.empty()) break; root = stack.top(); stack.pop(); } } 

#### Inorder traversal strategy

  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  //recursive template void BinTree::InorderTraverse(BinNodePosi root, void (*visit)(T &)) { if (root == nullptr) return; InorderTraverse(root->leftChild, visit); visit(root->data); InorderTraverse(root->rightChild, visit); } //no recursive template void BinaryTree::goAlongVine(BinNodePosi x, std::stack> &stack) { while (x != nullptr) { stack.push(x); x = x->leftChild; } } template void BinaryTree::InorderTraverse(BinNodePosi root, void (*visit)(T &)) { std::stack> stack{}; while (true) { goAlongVine(root, stack); if (stack.empty()) break; root = stack.top(); stack.pop(); visit(root->data); root = root->rightChild; } } 

#### Postorder traversal strategy

  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  //recursive template void BinTree::PostorderTraverse(BinNodePosi root, void (*visit)(T &)) { if (root == nullptr) return; PostorderTraverse(root->leftChild, visit); PostorderTraverse(root->rightChild, visit); visit(root->data); } //no recursive template void BinaryTree::gotoLeftmostLeaf(std::stack> &stack) { while (BinNodePosi x = stack.top()) { if (x->leftChild != nullptr) { if (x->rightChild != nullptr) stack.push(x->rightChild); stack.push(x->leftChild); } else { stack.push(x->rightChild); } } stack.pop(); } template void BinaryTree::PostorderTraverse(BinNodePosi root, void (*visit)(T &)) { std::stack> stack{}; if (root != nullptr) stack.push(root); while (!stack.empty()) { if (stack.top()->leftChild != root && stack.top()->rightChild != root) gotoLeftmostLeaf(stack); root = stack.top(); stack.pop(); visit(root->data); } } 

#### Level order traversal strategy

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  template void BinTree::LevelTraverse(BinNodePosi root, void (*visit)(T &)) { if (root == nullptr) return; std::queue> queue{}; queue.push(root); while (!queue.empty()) { BinNodePosi x = queue.front(); queue.pop(); visit(x->data); if (x->leftChild != nullptr) queue.push(x->leftChild); if (x->rightChild != nullptr) queue.push(x->rightChild); } } 

#### Application

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  void CountLeaf (BiTree T, int &count) { if (T) { if ((!T->lchild) && (!T->rchild)) count++; // Count leaf node CountLeaf(T->lchild, count); CountLeaf(T->rchild, count); } // if } // CountLeaf int depth(BiTree T) { int dep1,dep2; if (T == NULL) return 0; else { dep1 = depth(T->lchild); dep2 = depth(T->rchild); if (dep1 > dep2) return (dep1 + 1); else return (dep2 + 1); } } 

#### Reduction tree

preorder or postorder + Inorder is OK

$n\ nodes\ (Binary\ linked\ list):$

$number\ of\ pointers=2n$

$one\ node\ have\ it’s\ own\ pointer, expect\ root\ node$

$so\ the\ number\ of\ empty\ pointers=2n-(n-1)=n+1$

Definition: Threaded Binary Trees use n+1 null pointer field to store node’s precursor and successor information

Example: preorder traverse:$A\ B\ C\ D\ E\ F\ G\ H\ K$ so in Threaded Binary Tree:

implementation

Add “Ltag” and “Rtag” to the binary linked list as two flag fields

$[lchild] [Ltag] [data] [Rtag] [rchild]$

if has LeftChild

Ltag = 0

lchild = LeftChild

else

Ltag = 1

lchild = preorder

if has RightChild

Rtag = 0

rchild = RightChild

else

Rtag = 1

rchild = successor

Add a head node whose lchild points to the root of the binary tree, Ltag = 0, Rtag = 0

And this node is used as the precursor of the first node traversed and the successor of the last node

Finally, the head pointer is used to point to the node

A binary tree of this structure is also called a binary tree threaded list

A pointer to a precursor or successor is called a thread

A binary tree with a clue is called a threaded binary tree

The process of traversing a binary tree with a rule to turn it into a threaded binary tree is called threading

#### Look for successor in Inorder Threaded Binary Trees

 1 2 3 4 5 6 7 8 9  BiThrNode *nextnode(BiThrNode *p) { if(p->Rtag) return p->rchild; //Find the leftmost node in the right subtree next = p->rchild; while(!next->Ltag) next = next->lchild; return next; } 

#### Look for predecessor in Inorder Threaded Binary Trees

 1 2 3 4 5 6 7 8 9  BiThrNode *priornode(BiThrNode *p) { if(p->Ltag) return p->lchild; //Find the rightmost node of the left subtree pre = p->lchild; while(!pre->Rtag) pre = pre->rchild; return pre; } 

### Tree and Forest

A forest is a set of $n \geq 0$ disjoint trees

Forest

Tree

### Trees Implementation

#### Parent Pointer Implementation

have a pointer that points the parent

#### Lists of Children

From1

$[data] [child_1] [child_2] … [child_d], d\ is\ the\ tree’s\ degree$

Problem: Null pointers waste space

From2

$[data] [degree] [child_1] [child_2] … [child_{degree}], degree\ is\ the\ node’s\ degree$

Problem: nodes structure is inconsistent

From3

From4

### Implementation of Leftmost Child/Right Sibling

 1 2 3 4 5 6  typedef struct TreeNode * PtrToNode; struct TreeNode { ElementType element; PtrToNode FirstChild; PtrToNode NextSibling; }; 

FirstChild pointer: arrow that points downward

NextSibling pointer: arrow that goes left to right

Transform a binary tree into forest

1. keep current root node and its left subtree as one of a tree of the forest, the right subtree as the other trees
2. Repeat step above until the right subtree in the node is empty

### Huffman Tree

Path Length: The length of path is the number of edges on the path

Weighted Path Length, WPL

$WPL=\sum_{i=1}^kW_iL_i$

$w_i$ is the weight of the i-th leaf

$L_i$ is the path length from root to the i-th leaf

Definition: Huffman Tree: the binary tree with the minimum weighted Path Length

#### Prefix code

No codeword is a prefix of any other codeword

#### Huffman’s Algorithm

Build tree bottom-up, so that the lowest weight leaves are farthest from the root

Repeatedly:

1. Find two trees of the lowest weight
2. Merge them to form a new tree whose weight is the sum of their weights

#### Determinant Tree

Reduce the number of decisions according to the frequency of the condition

The number of nodes in the binary tree with degree 0 minus one equals the number of nodes with degree 2