Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery Data Structure Chapter 5-Tree and Binary Tree

Data Structure Chapter 5-Tree and Binary Tree

Chapter 5 of "Data Structure" - sorting out the knowledge of trees and binary trees, including the basic concepts of trees, the concept of binary trees, binary tree traversal and clue binary trees, etc.

Edited at 2022-11-23 16:07:00

PlotWizard

Recent works View more works>>

Data Structure Chapter 5-Tree and Binary Tree

PlotWizard

Recent works View more works>>

Recommended to you
Outline

data structure
- 10
PlotWizard

Numbers and Binary Trees

Basic concepts of trees

definition

A tree is a finite set of n nodes. A non-empty tree should satisfy:

There is only one root node

When n>1, the remaining nodes can be divided into m disjoint finite sets Ti, each set is a subtree of the root.

basic terminology

ancestors, descendants, parents, children, brothers

Degree: the number of children of the node

The maximum degree of a node is called the degree of the tree

Leaf nodes (terminal nodes), branch nodes (non-terminal nodes)

The sum of the node degrees of the tree = the sum of the number of branches = the number of nodes - 1

Depth: starting from the root node and accumulating layer by layer from top to bottom.

Height: starting from the leaf node and accumulating layer by layer from bottom to top.

Ordered tree, unordered tree

path, path length

Forest: a collection of m disjoint trees

nature

The number of nodes in the tree = the sum of the degrees of all nodes 1

There are at most m^(i-1) nodes on the i-th level of a tree of degree m.

An m-ary tree with height h has at most (m^h-1)/(m-1) nodes.

The minimum height of an m-ary tree with n nodes is:

Binary tree concept

Definition and characteristics

Definition: Each node has at most two subtrees, and the subtrees can be divided into left and right subtrees.

special binary tree

full binary tree

The height is h and the number of nodes is 2^h-1

For the node numbered i

parents:

Left child: 2i

Right child: 2i 1

complete binary tree

The number of each node corresponds to a full binary tree (that is, only the leaf node on the right is empty)

nature

①If i≤Ln/2", then node i is a branch node, otherwise it is a leaf node.

②Leaf nodes can only appear on the two largest levels. The leaf nodes in the largest level are arranged in sequence at the leftmost position of the level.

③If there is a node with degree 1, there can only be one, and the node has only left children but no right children.

④After numbering in hierarchical order, once a node (numbered i) appears as a leaf node or has only a left child, the number is greater than i The nodes are all leaf nodes.

⑤ If n is an odd number, then each branch node has a left child and a right child; if r is an even number, the branch node with the largest number (numbered n/2) has only a left child and no right child, and the other branch nodes have There are children who click left and right.

⑥The height of a complete binary tree with n nodes is:

Binary sorting tree

Left subtree keyword<root node<right subtree

The left and right subtrees are each a binary sorting tree.

balanced binary tree

The depth difference between the left subtree and the right subtree of any node in the tree does not exceed 1

Properties of binary trees

The number of leaf nodes on a non-empty binary tree = the number of nodes with degree 2 1, that is, n0=n2 1

There are at most 2^(k-1) nodes on the k-th level of a non-empty binary tree.

A binary tree of height h has at most 2^h-1 nodes.

Binary tree storage structure

sequential storage structure

chain storage structure

Binary tree traversal and clue binary trees

Binary tree traversal

Preorder traversal (NLR)

In-order traversal (LNR)

Postorder traversal (LRN)

Recursive algorithm → non-recursive (with the help of stack)

Non-recursive algorithm for in-order traversal

Level traversal (with the help of queues)

Construct a binary tree from a traversal sequence

A binary tree can be uniquely determined by its preorder (or postorder) sequence and inorder sequence.

The first node of the preorder sequence must be the root node, and the root node divides the inorder sequence into two sequences: the left and right subtrees.

Find the left and right subtrees in the preorder according to the left and right subtrees in the inorder, and repeat the above steps recursively.

A binary tree can be uniquely determined by its hierarchical sequence and in-order sequence.

According to the pre-order and post-order sequences of the binary tree, the ancestral relationship of some nodes can be determined: if the pre-order is aX and the post-order is Xa, then the nodes in the set If they are brothers, the order should be consistent, that is, the left brother comes first)

clue binary tree

concept

Construct in-order clue binary tree

Clue binary tree with leading node

Traversal of binary trees with inorder clues

Find the first node under the inorder sequence in the inorder clue binary tree

Find the successor of node p in the in-order clue binary tree under the in-order sequence

In-order traversal algorithm for in-order clued binary trees without head node

Pre-order clue binary tree and post-order clue binary tree

Find node successor in preorder clue binary tree

If there is a left child, he will be his successor

If there is no left child but there is a right child, the second child will be the successor.

Otherwise, the right chain domain points to the successor

Finding the successor of a node in a binary tree using postorder clues

If x is the root of a binary tree, then the successor is empty

If x is the right child of both parents, or the left child of both parents and the parents have no descendants, then the successor is his parents

If x is the left child of the parent, and the parent has a right child, the successor is the first node listed in the descending order traversal on the right subtree of the parent.

Applications of trees and binary trees

Huffman trees and Huffman coding

definition

Weighted path length: The product of the path length (number of edges passed) from the root of the tree to any node and the weight of the node

The weighted path length of the tree: the sum of the weighted path lengths of all leaf nodes in the tree

Huffman tree: Among the binary trees containing n weighted leaf nodes, the binary tree with the smallest weighted path length (WPL) is also called the optimal binary tree.

The structure of Huffman tree

construction process

Given n nodes with weights w1, w2,...,wn, the algorithm for constructing a Huffman tree is described as follows:

1) Treat these n nodes as n binary trees containing only one node to form a forest F.

2) Construct a new node, select the two trees with the smallest root node weights from F as the left and right subtrees of the new node, and set the weights of the new node to the roots of the left and right subtrees. The sum of the node weights.

3) Delete the two trees just selected from F and add the newly obtained trees to F.

4) Repeat steps 2) and 3) until there is only one tree left in F.

Features

1) Each initial node eventually becomes a leaf node, and the smaller the weight, the greater the path length from the node to the root node.

2) A total of n-1 new nodes (double-branch nodes) are created during the construction process, so the total number of nodes of the Huffman tree is 2n-1.

3) Each construction selects 2 trees as the children of the new node, so there is no node with degree 1 in the Huffman tree.

Huffman coding

variable length encoding

Different characters are represented by binary bits of unequal length; low-frequency characters are assigned longer codes, and high-frequency characters are assigned shorter codes.

prefix encoding

No encoding is a prefix of another, so decoding is very simple

Huffman coding is a data compression coding designed using variable length and prefix coding.

Huffman tree→Huffman coding

1) Treat each appearing character as an independent node, its weight is equal to the frequency of occurrence (number of times), and construct the corresponding Huffman tree

2) Interpret the encoding of a character as a sequence of edge markers on the path from the root to the character; where an edge marker of 0 means "turn to the left child", and an edge mark of 1 means "turn to the right child"

And search the collection

Basic idea

Usually the parent representation of a tree (forest) is used as the storage structure of the union-find set, and each sub-set is represented by a tree. All trees representing sub-sets form a forest representing the entire set and are stored in the parent representation array. Usually, the subscript of the array element is used to represent the element name, and the subscript of the root node is used to represent the sub-collection name. The parent node of the root node is a negative number.

operate

1) Initial(S): Initialize each element in the set s to a subset with only a single element.

2) Union(S, Root1, Root2): Merge the sub-set Root2 in the set S into the sub-set Root1. Require Root1 and Root2 are disjoint with each other, otherwise the merge will not be performed.

3) Find(S,x): Find the subset where the single element x is located in the set s, and return the root node of the subset.

tree, forest

tree storage structure

parent representation

A set of continuous spaces is used to store nodes; at the same time, a pseudo pointer is added to each node to indicate the location of the parents.

You can quickly get the parent nodes of a node, but you need to traverse the array to find the children of the node.

child representation

Connect the child nodes of each node with a single linked list, n nodes correspond to n linked lists

Finding children is simple, but finding parents requires traversing n linked lists

Child brother representation (binary tree representation)

Using a binary linked list as the storage structure of the tree

Node

node value

Pointer to the first child of the node

Pointer to the node's next sibling node

It is easy to find children, but it is more troublesome to find parent nodes (parent pointer can be added)

Conversion of trees, forests and binary trees

tree ↔ binary tree

Using a binary linked list as a medium, there is a unique binary tree corresponding to each tree (and vice versa)

Conversion rule: "Left child, right brother"

Root-first traversal sequence: ABEFCDG

Post-root traversal sequence: EFBCGDA

Forest ↔ Binary tree

Similar to the above conversion, each tree is first converted into a binary tree, and then the root of the n-th tree is regarded as the right sibling of the root of the n-th tree.

Preorder traversal of sequence: ABCDEFGHI

In-order traversal sequence: BCDAFEHIG

Tree and forest traversal

tree traversal

Root traversal first

First visit the root node, then visit each subtree in turn

The traversal sequence is the same as the preorder sequence of the corresponding binary tree

back root traversal

First visit each subtree in turn, then visit the root node

The traversal sequence is the same as the in-order sequence of the corresponding binary tree

Level traversal

Traveling through the forest

preorder traversal

Visit the root node of the first tree in the forest

Pre-order traverse the subtree forest of the root node in the first tree

Preorder traverse the remaining forest after removing the first tree

inorder traversal

In-order traversal traverses the subtree forest of the root node of the first tree in the forest.

Visit the root node of the first tree

In-order traversal of the forest consisting of the remaining trees after removing the first tree