Home / Algorithm

Next Store With Full Binary Tree

1.2. Some concepts of trees

- Degree: The number of children of a node is called the degree of that node (figure 6.1: A has 3 children, which is level 3).

o A node with zero degree (a node with no children) is called a leaf (Figure 6.1: E, F, C,.. are leaves)

o The highest level of a node in a tree is called the level of the tree. (Figure 6.1: Level is 3).

- Level: The root of the tree has one level.

Maybe you are interested!

If the parent node has level i, then the child node has level i+1 (Figure 6.1: A has level 1, D has level 2, G has level 3,...).

- The height (Height) or depth (Depth) of a tree is the maximum number of levels of a node in that tree. (Figure 6.1: the maximum number of levels is 4, so the tree has a height of 4).

- Path: If we have a sequence of nodes n1,n2,...,nk on a tree and satisfy ni is the parent of ni+1 then that sequence is called a path on that tree. Path length: Is the number of nodes on the path minus one.

- If the order of the subtrees of a node is important, then the tree under consideration is an ordered tree, otherwise it is an unordered tree. Usually the order of the subtrees of a node is placed from left to right.

- If there is a finite set of distinct trees, we call that set a forest (note: The concept of forest here must be understood in its own sense: There is a tree, if we remove the root node, we will have a forest).

2. Binary tree

2.1. Concept of binary tree


Is an important form of tree structure.

The characteristic is that every node in the tree has at most two children.

For the subtree of a node, one also distinguishes between the left subtree and the right subtree.

A


B C


DE FG


HIJK


Figure 6.3: Binary tree


2.2. Some properties of binary trees

- The characteristics mentioned in section 1.2 also hold true for binary trees.

- The maximum number of nodes at level i on a binary tree is 2 (i-1) . (i>=1)

- The maximum number of nodes on a binary tree of height h is: 2 h – 1 (h>=1)

- Some special forms of binary trees


Zigzag tree

left skewed tree

Right-leaning tree

f) Complete binary tree

Complete binary tree


Figure 6.4: Special binary tree

o Complete binary tree: Nodes corresponding to levels except the last level are maximized (e, f is a complete binary tree).

o Complete binary tree has minimum height.

o Degenerate binary tree (a, b, c, d) has the largest height.


2.3. Binary tree representation.

2.3.1. Storing trees using successive vectors (successive storage):

Use a storage vector V consisting of MaxSize successive memory elements to store the nodes in the tree.


Figure 6.5: Binary tree storage vector

a. Storage principles

- If the father has the order number i, then the son has the order number 2i and 2i+1

- If the child has the serial number j, then the father has the serial number j/2 (take the bottom integer)

- The father-child relationship is determined by this serial number.

- Use vector V to store nodes on the tree according to the principle that the i-th node of the tree is stored by vector V[i].

 Consider a complete binary tree: Number the nodes in the tree in order from level 1 up, from level to level and within each level from left to right.

ABCDEFG-0123456


Figure 6.6: Full stamen tree

Node 0 is stored by element V0, node 1 is stored by element V1 …


Figure 6.7: Successive storage with full binary tree


 Consider an incomplete complete binary tree



Figure 6.8: Incomplete complete binary tree


Corresponding storage vector:


Figure 6.9: Successive storage with complete binary tree

Comment :

- Advantage:

• With this storage method, the parent-child relationship is completely determined through the index of the storage vector.

• With a full binary tree, this storage method is quite convenient.

• Direct access to tree nodes via element index

- Disadvantages:

• Incomplete binary trees and especially degenerate binary trees cause memory waste because there are many empty nodes.

• If the tree is always changing (there are frequent additions and removals, this storage method shows more disadvantages).

Thus, successive storage is usually used only for full or complete binary trees.

b. Declare structure.

To implement a general binary tree using the next storage vector, we use an array of nodes with a maximum length of MaxSize elements. Each node of the tree is represented by a record consisting of three fields. The first field info is of type Item (Item can be a simple data type or a structured data type), the second and third fields Lchild and Rchild contain the indices of the left and right child nodes.

Declare the structure of the list using an array: const int MaxSize=100

typedef struct node

{ Item info;

int Lchild, Rchild;

};

node tree[MaxSize];

2.3.2. Storing trees using linked lists:

To overcome the disadvantages of sequential storage, people often use linked lists to store with binary trees.

a. Storage principles

- Only store nodes that exist in the tree

- With the hook storage method, the above disadvantages will be overcome and the natural shape of the tree will be reflected.

- Use a pointer T that always points to the root node of the tree to help us access the tree. When the tree is empty T=NULL

- Specifications:


Figure 6.10: Storing a node on a binary tree

o Info field: Stores the corresponding information on the tree

o Lchild field: Points to the corresponding left child tree of the node

o Rchild field: Points to the corresponding right subtree of the node

 Suppose we have a complete binary tree as shown in Figure 6.8 Linked storage image



Figure 6.11: Storing links with binary tree Figure 6.9

Comment:

- Advantages: Saves memory

- Disadvantage: Sequential access starts from parent node to child nodes

b. Structure declaration

Implement a general binary tree using a linked list, each node of the tree is represented by a record of 3 fields. The first field info is of type ElementType (ElementType can be simple data types or structured data types), the second and third fields are Lchild and Rchild which have node pointer data type containing the addresses of the left child node and right child node.

In particular, a pointer T is needed to always contain the address of the root node of the tree. T is NULL when the tree is empty.

Declare the structure of a tree using a linked list:

struct node

{ ElementType info; node *Lchild;

node *Rchild;

};

typedef struct node* TreeNode; TreeNode T;

3. Binary tree traversal operations.

The process of processing each node of a tree in a certain order is called a tree traversal. There are usually three tree traversals:

- Traverse the tree in pre-order.

- Traverse the tree in middle order.

- Traverse the tree in the following order.

In each tree traversal, we must visit the nodes in turn so that each node is visited only once. Suppose we have the following binary tree, we will have a different sequence of nodes corresponding to each tree traversal.


Figure 6.12: Complete binary tree

3.1. Preorder traversal .

3.1.1. Approval.

The traversal is performed by visiting the root first, specifically in the following order:

- Visit the root.

- Traverse the left subtree in order.

- Traverse the subtree in order first.

3.1.2. Algorithm:

With the binary tree structure implemented using a linked list as follows:

typedef char ElementType; struct node

{ ElementType info; node *Lchild;

node *Rchild;

};

typedef struct node* TreeNode; TreeNode T;

The PreOrder algorithm is implemented recursively as follows:

// The formal parameter T is a pointer containing the address of the root node of the tree

void PreOrder(TreeNode T)

{ if (T != NULL)

{ printf(“% c ”, T->info); //print the value of the info field to the screen

PreOrder (T-> Lchild) PreOrder (T-> Rchild)

}

}

The sequence of nodes of the binary tree in Figure 6.12 corresponding to the pre-order traversal of the tree is: ABDEHICFGJ.

3.2. Inorder traversal .

3.2.1. Approval.

The traversal is performed by visiting the root after visiting all the nodes of the left subtree, specifically as follows:

- Traverse the left subtree in middle order.

- Visit the root.

- Traverse the subtree in middle order.

3.2.2. Algorithm:

The recursive algorithm of InOrder is implemented similarly as follows:

// The formal parameter T is a pointer containing the address of the root node of the tree

void InOrder(TreeNode T)

{ if (T != NULL)

{ InOrder (T-> Lchild)

printf(“% c ”, T->info); //print the value of the info field to the screen

InOrder (T-> Rchild)

}

}

The sequence of nodes of the binary tree in Figure 6.12 corresponding to the middle-order traversal of the tree is: DBHEIAFCGJ.

3.3. Postorder traversal .

3.3.1. Approval.

The traversal is performed by visiting the root last, after having visited all the nodes of the left subtree and the nodes of the right subtree in the following order:

- Browse the left subtree in the following order.

- The subtree must be traversed in the following order.

- Visit the root.

3.3.2. Algorithm:

The recursive algorithm of PostOrder is implemented similarly as follows:

// The formal parameter T is a pointer containing the address of the root node of the tree

void PostOrder(TreeNode T)

{ if (T != NULL)

{ PostOrder (T-> Lchild) PostOrder (T-> Rchild)

printf(“% c ”, T->info); //print the value of the info field to the screen

}

}

The sequence of nodes of the binary tree in Figure 6.12 corresponding to the following order of tree traversal is: DHIEBFJGCA

Tree traversals are implemented quite easily using recursive algorithms because it reflects the exact form of tree traversal definitions. The visit to each node here is to display the value of the node's info field.

3.4. Application examples.

Use a binary tree structure to store an arithmetic expression, with the rule that parent nodes contain operators and leaf nodes contain operands.

Suppose we have the expression:

Comment


Agree Privacy Policy *