Data structure —— Tree (traversal and construction of binary tree)

Article directory

  • One, tree
  • 2. Tree storage structure
    • 1. Expression of parents
    • 2. Child representation
    • 3. Representation of children’s brothers
  • Three, binary tree
    • 1. Characteristics of binary trees
    • 2. Special binary tree
      • (1) leaning tree
      • (2) Full binary tree
      • (3) Complete binary tree
    • 3. Storage structure of binary tree
      • 1. Linked storage structure of binary tree
        • (1) Binary tree traversal
          • ① Preorder traversal
          • ②In-order traversal
          • ③Post-order traversal
        • (2) Construction of binary tree
        • (3) Find the depth of the binary tree
      • 2. Sequential storage structure of binary tree
  • Summarize

One, tree

The data structures we have learned before are all one-to-one linear structures, while trees are one-to-many structures.
The following figure shows some basic terms for trees.

2. Tree storage structure

1. Parental representation

// 1. Parental representation

typedef struct PTNode
{<!-- -->
ElemType data; //data
int parent; //subscript of parents
}PTNode;

typedef struct
{<!-- -->
PTNode nodes[MAX_SIZE]; //Structure array, which contains the corresponding data and the location of the parents.
int root,num; //root --- The position of the root node num The total number of nodes
}PTree;

It records the subscripts of the parents and the data corresponding to itself.

2. Child representation

//2. Child representation

typedef struct CTNode
{<!-- -->
int child; //The subscript of the current child
struct CTNode* next; //Next child
}CTNode;


typedef struct
{<!-- -->
ElemType data; //data of current node
CTNode* fristchild; //The first child of the current node
}CTBox;
 
typedef struct
{<!-- -->
CTBox nodes[MAX_SIZE]; //Structure array, which contains the corresponding data and the child linked list.
int root,num; //Root node, total number of nodes
}CTree;

The child notation seems to define a lot of things, but it is not. Let’s look at them one by one:
The first CTNode is actually just a singly linked list.
The following is the same as the parent representation method, except that the index of the parent is replaced by the singly linked list defined above.

3. Notation of children’s brothers

//3. Child brother representation

typedef struct CSTNode
{<!-- -->
ElemType data;
struct CSTNode* fristnode, *rightsib; //The first child has brothers.
}CSTree;

data is the data field, and the pointer fields are the first child and its right brother respectively.
This is the representation of children’s brothers. In fact, it is very close to a kind of tree —– Binary tree.

Three, binary tree

1. Characteristics of binary trees

  • A node can have at most two children
  • The left and right subtrees are ordered and cannot be reversed.
  • Even if a node in the tree has only one child, it is necessary to distinguish whether it is a left subtree or a right subtree.

2. Special binary tree

(1) Inclined tree

It just fell to one side. The root of a singly linked list is similar, but not because it differentiates between left and right.

(2) Full binary tree

A full binary tree means that all nodes have two left and right children, except leaf nodes. Quite beautiful!

(3) Complete binary tree

The following is a complete binary tree,

The following pictures are not complete binary trees. The purple box indicates that the node does not exist.


We can find that as long as there is a missing number in the middle, or a discontinuous node, it is not a complete binary tree.

  1. Leaf nodes can only appear in the last two levels
  2. The leaf nodes of the last layer are all on the left half.
  3. If there is a leaf node on the penultimate layer, it must be on the right half.
  4. If the node has a child, it must be the left child.

3. Storage structure of binary tree

The storage structure of a binary tree can also be stored separately in right-chain and sequential order.

1. Linked storage structure of binary tree

The following is the definition of a binary tree, which is quite similar to the child brother representation above.
I also need some global variables here, which will be used later in constructing a binary tree.
You can automatically construct a binary tree, or you can choose to enter it manually.

typedef char ElemType;


int treeindex = 0;
char str[] = "abdh##i##ej##k##cf##g##";
ElemType NIL = '#';

typedef struct BTNode
{<!-- -->
ElemType data;
struct BTNode* rchild,*lchild; //left and right children
}BTNode,*BTree;
(1) Binary tree traversal

I did not write how to construct the binary tree first, because the construction of the binary tree makes full use of the traversal of the binary tree. As long as you understand traversal, the construction of a binary tree will naturally be OK.
There are three types of binary tree traversal: pre-order traversal, in-order traversal, and subsequent traversal.

① Preorder traversal

Root left and right These three words serve as the entire content of the binary tree traversal.

  • First, if the root is not empty, access its root. After accessing it, find its left subtree.
  • Then it is found that the passed one is still the root, and the previous step is repeated. Until there are no left children. Pass in theright child.
  • The child on the right comes over and is still the root, and repeats the above two operations.

This is actually a recursive process, but it’s a bit convoluted and a bit much. In fact, it’s not that convoluted when you write it down.

//Preorder traversal
void PreOrderTraverse(BTree* T)
{<!-- -->
if(*T != NULL)
{<!-- -->
//print root
PrintNode(*T);
//left child
if((*T) -> lchild != NULL)
PreOrderTraverse( & amp;(*T) -> lchild);
//right child
if( (*T) -> rchild != NULL)
PreOrderTraverse( & amp;(*T) -> rchild);
}
}

With just this bit of code, you can debug it and feel how the program runs step by step. With preorder traversal, inorder traversal and postorder are even simpler.

②In-order traversal

Left Root Right

//In-order traversal
void InOrderTraverse(BTree* T)
{<!-- -->
if(*T != NULL)
{<!-- -->
\t\t
//Visit the left child first
if((*T) -> lchild != NULL)
InOrderTraverse( & amp;(*T) -> lchild);
\t\t
//Print the root again
PrintNode(*T);

//Then on the right child
if( (*T) -> rchild != NULL)
InOrderTraverse( & amp;(*T) -> rchild);
}
}
③Post-order traversal

Left and right roots

//Subsequent traversal
void PostOrderTraverse(BTree* T)
{<!-- -->
\t
if(*T != NULL)
{<!-- -->
\t\t
\t\t\t\t
if((*T) -> lchild != NULL)
PostOrderTraverse( & amp;(*T) -> lchild);
\t\t\t
if( (*T) -> rchild != NULL)
PostOrderTraverse( & amp;(*T) -> rchild);
\t
PrintNode(*T);
}
\t
}

Look, around the root, these three characters are changing back and forth, and the corresponding codes have not changed, but the corresponding positions have been adjusted.
I feel that binary tree traversal is actually the essence of binary trees.

(2) Construction of binary tree

Once you understand binary tree traversal, the structure will be easier to understand.
In fact, if you think about it carefully, it is very simple. The traversal of a binary tree is to access the data of the node. To construct a binary tree, it is not to traverse the binary tree. If you want to assign a value to an array, don’t you also traverse each unit one by one to traverse the array and write Enter data, so the same is true for constructing a binary tree.

The following is to construct a binary tree according to the pre-order traversal method. Of course, you can also choose in-order and subsequent. Either way can be successful.

(*T) = (BTree)malloc(sizeof(BTNode));
if(*T == NULL)
exit(-1);
(*T) -> data = ch;
BTreeCreate( & amp;(*T) -> lchild);
BTreeCreate( & amp;(*T) -> rchild);

The above is the core content, the following is the complete code

//Construct a binary tree according to preorder traversal
void BTreeCreate(BTree* T)
{
ElemType ch;
ch = str[treeindex + + ];
\t
//scanf("%c", & amp;ch);
\t
//NIL == '#' means the node does not exist.
if(ch == NIL)
{
(*T) = NULL;
}
else
{
(*T) = (BTree)malloc(sizeof(BTNode));
if(*T == NULL)
exit(-1);
(*T) -> data = ch;
BTreeCreate( & amp;(*T) -> lchild);
BTreeCreate( & amp;(*T) -> rchild);
}
\t
}
(3) Find the depth of a binary tree

The following code is actually also a pre-order traversal of a binary tree.

//Return the depth of the tree
int BTreeDepth(BTree T)
{<!-- -->
int i,j;
\t
if(T == NULL)
{<!-- -->
return 0;
}
\t
if( T -> lchild != NULL)
{<!-- -->
i = BTreeDepth(T -> lchild);
}
else
{<!-- -->
i = 0;
}
\t
if( T -> rchild != NULL)
{<!-- -->
j = BTreeDepth(T -> rchild);
}
else
{<!-- -->
j = 0;
}
\t
return i > j ? i + 1 : j + 1;
}

2. Sequential storage structure of binary tree

The sequential storage structure of a binary tree is actually stored in an array and then accessed using subscripts. The root chain operation is similar. The implementation is found in the source code below.

I chose to store it in cell No. 1 of the array. I assume that the current subscript is e, then the left child of the current node is 2 *e and the right child is (2 * e) + 1.

Summary

The article here actually mainly talks about the traversal of binary trees. This is also an operation that I personally think is very important. In fact, there are other operations, such as returning the left child, returning the parents, returning the right child, modifying the value of so and so, when When you can really understand binary tree traversal thoroughly, when you look back at these problems, it is actually not that difficult.
thanks for watching

Binary tree two storage structures source code link