数据结构基础(四)

Chapter 3 Tree

Preliminary

Terminology

Tree: collection of nodes

1. a distinguishd node $r$, called the root
2. zero or more nonempty (sub)trees T~1~, T~2~, …, each of whose roots are connected by a directed edge from $r$

N-node tree owns N-1 edges

Other terminologies

• Degree of a node: number of subtrees of the node
• Degree of a tree: maximum of degrees of nodes
• Parent
• Child
• Sibling
• Leaf: a node with degree 0
• Path from n~1~ to n~k~: (unique)
• Length of path: number of edges on the path
• Depth of n~i~: depth of root is 0
• Height of n~i~: height of leaves is 0
• Height / Depth of tree: height of root / depth of deepest leaf
• Ancestors of a node: including its parent node
• Descendants of a node

 

Implementation

• List Representation

• FirstChild-NextSibling Representaion

Tree{
	ElemType Element;
	Tree FisrtChild, NextSibling;
};

it is not unique; but it can change any common tree to a binary tree

 

Binary Tree

Degree <= 2

typedef struct TreeNode *Tree;
struct TreeNode{
	ElemType element;
	Tree left, right;
};

Expression Trees

[Eg1] Constructing an Expression Tree From Postfix Expression

[Solve] Stack

 

Tree Traversals

visit each node exactly once

T(N) = O(N)

Preorder Traversal

void Preorder(Tree tree){
	if(tree){
		Visit(tree);
		Preorder(tree->left);
		Preorder(tree->right);
	}
}

Postorder Traversal

void Postorder(Tree tree){
	if(tree){
		Postorder(tree->left);
		Postorder(tree->right);
		Visit(tree);
	}
}

Levelorder Traversal

void Levelorder(Tree tree){
	Queue que;
	que.push(tree);
	while(!que.empty()){
		Visit(que.pop());
		que.push(tree->left);
		que.push(tree->right);
	}
}

Inorder Traversal

void Inorder(Tree tree){
	if(tree){
		Inorder(tree->left);
		Visit(tree);
		Inorder(tree->right);
	}
}

void InorderIterative(Tree tree){
	Stack st;
	while(1){
		while(tree){
			st.push(tree);
			tree = tree->left;
		}
		tree = st.top();
		st.pop();
		if(!tree)	break;
		Visit(tree);
		tree = tree->right;
	}
}

Preorder & Postorder traversals could be used in common trees but Inorder traversal could not

[Eg1] Directory listing in a hierarchical file index

[Eg2] Calculatiing the size of a directory

In Linux, we could

$ tree

 

Threaded Binary Tree

there are N + 1 pointers to NULL wasted in common binary tree with N nodes

• Rule 1: if tree->left is NULL, replace it with a pointer to the inorder predocessor of tree
• Rule 2: if tree->right is NULL, replace it with a pointer to the inorder successor of tree
• Rule 3: Dummy-head node is needed, pointers of node ordered first or last in inorder traversal pointing to NULL should point to the dummy-head node

typedef struct ThreadedTreeNode *ThreadedTree;
struct ThreadedTreeNode{
	ElemType Element;
	// if left/right represents a thread, then assign it with TRUE
	bool leftThread, rightThread;
	ThreadedTree left, right;
};

 

Complete Binary Tree

All leaf node are on 2 adjacent levels

The maxinum number of nodes on level $i$: $2^{i-1}$
The maxinum number of nodes in a binary tree of depth of $k$: $2^k-1$

 

The Search Tree ADT – BST

Defination

A Binary Tree

• Each key is an integer
• left < right
• right > left

 

Implementations

1. Find
2. FindMin

Tree FindMin(Tree root){
    if(root == NULL || root->left == NULL){
        return root;
    }
    else if(root->left){
        return FindMin(root->left);
    }
}

3. FindMax
4. Insert

Tree Insert(ElemType key, Tree root){
    if(root == NULL){
        root = malloc(sizeof(struct TreeNode));
        root->element = key;
        root->left = root->right = NULL;
    }
    else{
        if(key < root->element){
            root->left = Insert(key, root->left);
        }
        else if(key > root->element){
            root->right = Insert(key, root->right);
        }
        else{
            ;
        }
    }
    return root;
}

5. delete
   • Delete a leaf node: Reset its parent link to NULL
   • Delete a degree 1 node: Replace the node by its single child
   • Delete a degree 2 or more node:
     • Replace the node by the largest onr in its left subtree / the smallest one in its right subtree
     • Delete the replacing node from the subtree

Tree Delete(ElemType key, Tree root){
    Tree tmpNode;
    if(root == NULL){
        return NULL;
    }
    else if(key < root->element){
        root->left = Delete(key, root->left);
    }
    else if(key > root->element){
        root->right = Delete(key, root->right);
    }
    else{
        if(root->left && root->right){
            tmpNode = FindMin(root->right);
            root->element = tmpNode->element;
            root->right = Delete(tmpNode->element, root->right);
        }
        else{
            tmpNode = root;
            if(root->left == NULL){
                root = root->right;
            }
            else if(root->right == NULL){
                root = root->left;
            }
            free(tmpNode);
        }
    }
    return root;
}