cos

title: Data Structure Study Notes <4> Binary Tree
link: Data Structure Study Notes <4> Binary Tree
catalog: true
lang: en
date: 2020-03-15 00:38:18
subtitle: MOOC Zhejiang University's Data Structure Online Course Study Notes - Binary Tree
tags:

• c++
• data structure
• binary tree
  categories:
• [notes, data structure]

1. What is a Tree#

1. Definition of a Tree#

A tree is a finite set of n (n≥0) nodes.
When n=0, it is called an empty tree.
For any non-empty tree (n>0), it has the following properties:

1. The tree has a special node called the "root", represented by r.
2. The remaining nodes can be divided into m (m>0) disjoint finite sets T1, T2, ..., Tm, where each set itself is a tree and is called a "subtree" of the original tree.
3. The subtrees are disjoint.
4. Except for the root node, each node has one and only one parent node.
5. A tree with N nodes has N-1 edges.

2. Some Basic Terms of a Tree#

1. Degree of a Node: The number of child nodes a node has.
2. Degree of a Tree: The maximum degree of the nodes in the tree.
3. Leaf Node: A node with a degree of 0.
4. Parent Node: If a node has a previous node, the previous node is called its parent node. If there is no previous node, the attribute has no parent node.
5. Child Node: If node A is the parent node of node B, then node B is called the child node of node A; the child node is also called a child node.
6. Sibling Node: Nodes with the same parent node are called sibling nodes.
7. Path and Path Length: A path from node n1 to nk is a node sequence n1, n2, ..., nk, where ni is the parent node of ni+1. The number of edges in a path is the length of the path.
8. Ancestor Node: All nodes along the path from the root to a certain node are ancestor nodes of that node.
9. Descendant Node: All nodes in the subtree of a certain node are descendants of that node.
10. Level of a Node: The root node is defined as level 1, and the level of any other node is the level of its parent node plus 1.
11. Depth of a Tree: The maximum level of all nodes in the tree is the depth of the tree.
12. Forest: A collection of m disjoint trees.

2. Representation of a Tree#

1. Child-Sibling Representation#

3. Binary Tree#

1. Definition#

Binary Tree T: A finite set of nodes.
This node can be empty.
If it is not empty, it consists of a root node and two disjoint binary trees called its left subtree TL and right subtree TR. There are five basic forms of binary trees: a empty tree, a tree with only one node, a tree with one node and a left subtree, a tree with one node and a right subtree, and a tree with one node and both left and right subtrees.

PS: The order of left and right subtrees matters in a binary tree

Several special binary trees

Abstract Data Type Definition of Binary Tree
Type Name: Binary Tree
Data Object Set: A finite set of nodes.
If it is not empty, it consists of a root node and its left and right binary subtrees.
Operation Set: BT∈BinTree, Item∈ElementType, important operations include:

1. Boolean IsEmpty(BinTree BT); //Determine if BT is empty
2. void Traversal(BinTree BT); //Traverse the tree and visit a node in a certain order;
3. BinTree CreatBinTree(); //Create a binary tree

Common traversal methods include:

• void PreOrderTraversal(BinTree BT); //Pre-order traversal - root, left subtree, right subtree
• void InOrderTraversal(BinTree BT); //In-order traversal - left subtree, root, right subtree
• void PostOrderTraversal(BinTree BT); //Post-order traversal - left subtree, right subtree, root
• void LevelOrderTraversal(BinTree BT); //Level-order traversal - from top to bottom, from left to right

2. Several Important Properties of Binary Trees#

• The maximum number of nodes in the i-th level of a binary tree is 2^i-1^, where i≥1.
• The maximum total number of nodes in a binary tree with depth k is 2^k^-1, where k≥1.
• For any non-empty binary tree T, if n0 represents the number of leaf nodes and n2 represents the number of non-leaf nodes with a degree of 2, then n0=n2+1.
• The depth k of a complete binary tree with n nodes must be log~2~n+1.

3. Storage Structure of Binary Trees#

1. Sequential Storage Structure#

Complete Binary Tree: Store the parent-child relationship of n nodes in a complete binary tree in order from top to bottom and from left to right.

• The parent node (index i > 1) has a parent node with an index of [i / 2] (rounded down).
• The left child node (index i) has an index of 2i (2i ≤ n, otherwise there is no left child).
• The right child node (index i) has an index of 2i+1 (2i + 1 ≤ n, otherwise there is no right child).

This sequential storage structure can also be used for general binary trees, but it may cause space waste.

Full Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

2. Linked Storage#

(1) Definition#

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
		ElementType Data;
		BinTree Left;
		BinTree Right;
}

(2) Traversal (Recursive Implementation)#

Pre-order Traversal:

1. Visit the root node first.
2. Pre-order traverse its left subtree.
3. Pre-order traverse its right subtree.

void PreOrderTraversal(BinTree BT) {
	if(BT) {
		printf("%d", BT->Data);
		PreOrderTraversal( BT->Left);
		PreOrderTraversal( BT->Right);
	}
}

In-order Traversal:

1. In-order traverse its left subtree.
2. Visit the root node.
3. In-order traverse its right subtree.

void InOrderTraversal(BinTree BT) {
	if(BT) {
		InOrderTraversal( BT->Left);
		printf("%d", BT->Data);
		InOrderTraversal( BT->Right);
	}
}

Post-order Traversal:

1. Post-order traverse its left subtree.
2. Post-order traverse its right subtree.
3. Visit the root node.

void PostOrderTraversal(BinTree BT) {
	if(BT) {
		PostOrderTraversal( BT->Left);
		PostOrderTraversal( BT->Right);
		printf("%d", BT->Data);
	}
}

(2) Traversal (Non-Recursive Implementation)#

Basic idea: Use a stack or queue

In-order Traversal (Non-Recursive)

• When encountering a node, push it onto the stack and traverse its left subtree.
• After the left subtree traversal is finished, pop the node from the stack and visit it.
• Then go to the right subtree of the node and in-order traverse it.

void InOrderTraversal(BinTree BT) {
	BinTree T = BT;
	Stack S = CreatStack(MaxSize); // Create and initialize stack S
	while( T || !IsEmpty(S) ) {
		while(T) { // Go left and push nodes along the way onto the stack
			Push(S, T);
			T = T->Left;
		}
		if( !IsEmpty(S) ) {
			T = Pop(S); // Pop the node from the stack
			printf("%5d", T->Data); // Visit the node
			T = T->Right; // Go to the right subtree
		}
	}
}

Level-order Traversal

• Need a data structure to store temporarily unvisited nodes (stack or queue)
  Queue implementation: Start the traversal from the root node, first enqueue the root node, and then start the loop: dequeue a node, visit the node, enqueue its left and right children.

1. Enqueue the root node.
2. Dequeue an element from the queue.
3. Visit the node pointed by the element.
4. If the left and right children of the node are not empty, enqueue them.

void LevelOrderTraversal(BinTree BT) {
	Queue Q;  BinTreee T;
	if ( !BT ) return; // Return directly if it is an empty tree
	Q = CreateQueue(MaxSize); // Create and initialize queue Q
	AddQ(Q, BT);
	while( !IsEmpty(Q) ) {
		T = DeleteQ(Q);
		printf("%d\n", T->Data); // Visit the node
		if(T->Left) AddQ(Q, T->Left); // Enqueue the left child
		if(T->Right) AddQ(Q, T->Right); // Enqueue the right child
	}
}

Additional Knowledge
Basic Operations of Data Management - Search: Find the records in a set R with a given key K. It can be divided into static search and dynamic search.
Static Search: The records in the set are fixed, and there are no insert and delete operations, only search operations.
Method 1: Sequential Search (Sentinel concept: set a value at the boundary of the array, and the loop can end when encountering the sentinel, which can reduce one branch judgment) Complexity: O(n);
Method 2: Binary Search (Prerequisite: the array is continuous and ordered)
Dynamic Search: The records in the set are dynamically changing, and there may be insert and delete operations in addition to search.