This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Definition 1.

  • Tree: a set of n finite data elements (n>=0)

Its tree-related terms:

Nodes: There are six nodes in the figure

Degree of node: The number of children of a node is the degree of node such as B is 2

Leaf nodes: nodes with degree zero or nodes without children as shown in D,E, and F

Branch nodes: nodes whose degree is not 0 (A,B,C)

Sibling: nodes with the same parent such as D and E

The number of layers of the tree: the root node of the tree is the first layer and the layers of the other nodes are the number of parent node layers plus 1

Tree depth: The depth of the maximum number of layers of nodes in the tree

Figure a.

2. The binary tree

  • Binary tree: each node has at most two subtrees (the degree of the node is less than or equal to 2) and the binary tree can be divided into left and right and cannot be arbitrarily reversed order
  • Full binary tree: a binary tree with depth K and 2K-1 nodes has the maximum number of nodes at each level
  • Complete binary tree: The nodes of a full binary tree are numbered consecutively, starting from the root, top-down, and from left to right. A binary tree with depth of K and n nodes is called a complete binary tree if and only if each node corresponds to nodes numbered from 1 to n in a full binary tree with depth of K

3. Properties of binary trees:

1. At most 2^(I -1) at the I level of the binary tree

2. A binary tree of depth K has at most 2^ K – 1 nodes

3. For any binary tree T, if the number of nodes with degree 0 is N0 and the number of nodes with degree 2 is n2, then N0 = n2 + 1

4. The depth of a complete binary tree with n nodes is ⌊log2n⌋+1

  1. For a complete binary tree with N nodes numbered in sequence, for any node I (1<= I <=n), we can get:

(1) If I =1, then node I is the root of the binary tree without parents; If I >1, the parent is ⌊ I /2⌋

(2) If 2i>n, node I has no left child (node I is a leaf node); If 2i<=n, the left child of I is 2i

(3) if 2i+1>n, node I has no right child; 2i+1<=n otherwise its right child is 2i+1

4. Storage structure

  • The sequential storage structure uses a set of contiguous storage cells to store the nodes of the binary tree, as shown in Figure A

#define MaxSize 100
typedef struct {
  char tree[MaxSize];
  int treeNum;
}BiTreec
Copy the code
  • Linked storage represents a binary tree in a linked list and by the nature of a binary tree, we know that a node should have three parts a pointer to the child to the left a pointer to the child and a data field

typedef struct node{
 char data;
 struct node *lchild,*rchild;
}BiTree;
Copy the code

4. Binary tree traversal (recursive implementation)

  • The premise
typedef struct Node{ char Data; struct Node *left,*right; }BiTNode; Void createBiTree(BiTree *T){int data; scanf("%c",&data); if(data=="*"){ T=NULL; }else{*T= (BiTree) malloc(sizeof(BiTNode)); (*T)->data = data; createBiTree((*T)->lchild); createBiTree((*T)->rchild); }}Copy the code
  • The former sequence traversal
 void preOrder(BiTree T){
   if(T==NULL) retrun ;
   printf("%c",T->data);
   preOrder(T->lchild);
   preOrder(T->rchild)
 }
Copy the code
  • In the sequence traversal
 void midOrder(BiTree T){
   if(T==NULL) retrun ;
   midOrder(T->lchild);
   printf("%c",T->data);
   midOrder(T->rchild)
 }
Copy the code
  • After the sequence traversal
 void rearOrder(BiTree T){
   if(T==NULL) retrun ;
   rearOrder(T->lchild);
   rearOrder(T->rchild)
   printf("%c",T->data);
 }
Copy the code