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:

- The tree has a special node called the "
**root**", represented by r. - 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. - The subtrees are
**disjoint**. - Except for the root node, each node has one and only one parent node.
- 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:

- Boolean IsEmpty(BinTree BT); //Determine if BT is empty
- void Traversal(BinTree BT); //Traverse the tree and visit a node in a certain order;
- 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:

- Visit the root node first.
- Pre-order traverse its left subtree.
- 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:

- In-order traverse its left subtree.
- Visit the root node.
- 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:

- Post-order traverse its left subtree.
- Post-order traverse its right subtree.
- 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**.

- Enqueue the root node.
**Dequeue**an element from the queue.**Visit**the node pointed by the element.- 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.