Tree

2022-11-06 约 1947 字预计阅读 10 分钟

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.

ADT

{

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）；
……

} ADT Tree

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

Empty binary tree
Binary tree with only one node
Binary without any right tree
Binary with left and right trees
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

Skewed Tree

Properties of binary trees

Maximum number of nodes

$The\ maximum\ number\ of\ nodes\ on\ level\ i\ of\ a\ binary\ tree\ is\ 2^{i-1}, i\geq 1$
$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

parent(i) is at $\lfloor\frac{i}{2}\rfloor$ if $i \not= 1$. If i = 1, i is the root and has no parent.
LeftChild(i) is at $2i$ if $2i \leq n$. If $2i > n$, then i has no left child
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 Tree

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

Triple Linked List

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

If symbols are operands, build a single node tree and push it on the stack
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
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<typename T>
void BinTree<T>::preorderTraverse(BinNodePosi<T> root, void (*visit)(T &)) {
    if (root == nullptr) return;
    visit(root->data);
    preorderTraverse(root->leftChild, visit);
    preorderTraverse(root->rightChild, visit);
}

//no recursive
template<typename T>
void BinaryTree<T>::visitAlongVine(BinNodePosi<T> x, void (*visit)(T &), std::stack<BinNodePosi<T>> &stack) {
    while (x != nullptr) {
        visit(x->data);
        stack.push(x->rightChild);
        x = x->leftChild;
    }
}

template<typename T>
void BinaryTree<T>::preorderTraverse(BinNodePosi<T> root, void (*visit)(T &)) {
    std::stack<BinNodePosi<T>> 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<typename T>
void BinTree<T>::InorderTraverse(BinNodePosi<T> root, void (*visit)(T &)) {
    if (root == nullptr) return;
    InorderTraverse(root->leftChild, visit);
    visit(root->data);
    InorderTraverse(root->rightChild, visit);
}

//no recursive
template<typename T>
void BinaryTree<T>::goAlongVine(BinNodePosi<T> x, std::stack<BinNodePosi<T>> &stack) {
    while (x != nullptr) {
        stack.push(x);
        x = x->leftChild;
    }
}

template<typename T>
void BinaryTree<T>::InorderTraverse(BinNodePosi<T> root, void (*visit)(T &)) {
    std::stack<BinNodePosi<T>> 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<typename T>
void BinTree<T>::PostorderTraverse(BinNodePosi<T> root, void (*visit)(T &)) {
    if (root == nullptr) return;
    PostorderTraverse(root->leftChild, visit);
    PostorderTraverse(root->rightChild, visit);
    visit(root->data);
}

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

Threaded Binary Trees

$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

empty Threaded binary tree

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

Advantage: lookup parent easily

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

Leftmost Child/Right Sibling

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

keep current root node and its left subtree as one of a tree of the forest, the right subtree as the other trees
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:

Find two trees of the lowest weight
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

目录

Tree

Data Structure

Tree

Definition

Terminology

ADT

Operations

Full Binary Tree

Complete Binary Tree

Skewed Tree

Properties of binary trees

Maximum number of nodes

Array implementation of stacks

Linked implement of Tree

Linked implement of Binary Tree

Triple Linked List

Application of Binary Trees: Expression Trees

Preliminaries: Traversal Strategy

preorder traversal strategy

Inorder traversal strategy

Postorder traversal strategy

Level order traversal strategy

Application

Reduction tree

Threaded Binary Trees

Look for successor in Inorder Threaded Binary Trees

Look for predecessor in Inorder Threaded Binary Trees

Tree and Forest

Trees Implementation

Parent Pointer Implementation

Lists of Children

Leftmost Child/Right Sibling

Implementation of Leftmost Child/Right Sibling

Huffman Tree

Prefix code

Huffman’s Algorithm

Determinant Tree