This is the second day of my participation in the Novembermore Challenge.The final text challenge in 2021

The countdown to postgraduate entrance examination: 53 days

Reference materials: Wang Dao data structure examination review guidance day qin data structure high score notes

This paper first summarizes the basic concept of tree and calculation, binary tree traversal and clue binary tree content.

The second part summarizes the tree and forest, and the application (binary sorting tree, balanced binary tree, Huffman tree).

The nature of the tree

  1. The number of nodes in the tree is equal to the degree of all nodes plus 1.
  2. A tree of degree M has at most mi−1m^{i-1}mi−1 node at the i-layer (I >=1).
  3. A tree of height h and degree M has at most MH −1m−1\ FRAc {m^{h}-1}{m-1} M − 1MH −1.

(Derivation of sum formula using geometric sequence)

  1. The minimum height of a tree with sum nodes and degree m is ⌈logm(sum(m−1)+1)⌉\ LCeil log_m(sum(m-1)+1) \rceil⌈logm(sum(m−1)+1)⌉

(Use the third formula to get h, rounded up)

Properties of binary trees

  1. There are at most 2i−12^{i-1} 2I −1 nodes on the i-th layer of a binary tree
  2. A binary tree of depth K has at most 2k−12^ K-12K −1 nodes.
  3. For a non-empty binary tree, if the number of leaf nodes is
    m 0 m_0     , knot number of degree 2
    m 2 m_2     , there are
    m 0 = m 2 + 1 m_0=m_2+1

(Emphasis often encountered in multiple choice questions!!)

  1. The depth of a complete binary tree with N nodes is ⌊log2n⌋+1\ lFloor log_2 n \rfloor+1⌊log2n⌋+1
  2. Any complete binary tree with a node number of 1 either has one node or none.

Traversal of binary trees

Here are three types of recursion code for traversal, which will be used to develop many of the following questions.

// Binary tree storage structure
typedef struct BTNode{
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}

// Start by traversing the left and right sides of the root
void preorder(BTNode *p){
    if(p! =NULL){
        Visit(p);// call p. For example, print the value of ppreorder(p->lchild); preorder(p->rchild); }}// Middle order traverses left root right
void inorder(BTNode *p){
    if(p! =NULL){ inorder(p->lchild); Visit(p); inorder(p->rchild); }}// go through the left and right roots
void postorder(BTNode *p){
    if(p! =NULL){ postorder(p->lchild); postorder(p->rchild); Visit(p); }}Copy the code

Related to the topic

  1. The expression (A -(b+ C))*(d/e) is stored in a binary tree with a binary list as storage structure, and the program is written to find the value of the expression. (Hint, if the left and right subtrees are not empty, it is an expression. If the left and right subtrees are empty, it is a value.)
  2. Find the depth of a binary tree. (The maximum depth of left and right subtrees +1)
  3. Find if there is a node equal to key in the binary tree.
  4. A binary tree cannot be determined from a pre – and post-traversal sequence
  5. Outputs the value of the KTH node in the sequence traversed first (middle/last)
  6. Describe sequential code using non-recursive algorithms (using stacks)

Below is the code for hierarchical traversal

// Hierarchy traversal
void level(BTNode *p){
    int front,rear;
    BTNode *que[maxSize];  // Define a loop queue
    front=rear=0;
    BTNode *q;
    if(p! =NULL){
        rear=(rear+1)%maxSize;
        que[rear]=p;                    // the root node joins the queue
        while(front! =rear){ front=(front+1)%maxSize;
            q=que[front];               // The queue head exits
            Visit(q);
            if(q->lchild! =NULL) {// The left subtree is not empty. The root of the left subtree is enqueued
                rear=(rear+1)%maxSize;
                que[rear]=q->lchild;
            }
            if(q->rchild! =NULL) {// The root of the right subtree is enqueued
                rear=(rear+1)%maxSize; que[rear]=q->rchild; }}}}Copy the code

Cue binary tree

There is a binary tree with n nodes, which is stored as a binary linked list. There are n+1 null pointer fields in binary linked lists.

These null Pointers can be used for cueing.

If the left subtree of a node is empty, the left child pointer of the node points to its precursor.

If the right subtree of a node is empty, the pointer to the right child of the node points to its successor.

Photo by Chilan Yuk

“Problem”

[2010年408]

Click to see the answer

D did it right XDM!

[2014年408]

Click to see the answer

And that’s choice D!

Part of the content to be added to improve ~

If wrong, please correct more!