Data Structure — Tree (2)

This is the 16th day of my participation in Gwen Challenge

The tree

Traversal of binary tree and binary tree of clue

Traversal of binary trees

• Sequential traversal: If the binary tree is not empty,
  • Accessing the root
  • The left subtree is traversed in order
  • The right subtree is traversed in order
• Middle-order traversal: If the binary tree is not empty,
  • Middle order traverses the left subtree
  • Accessing the root node
  • Middle order traverses the right subtree
• Postorder traversal: If the binary tree is not empty,
  • The left subtree is traversed sequentially
  • The right subtree is traversed sequentially
  • Accessing the root node

Ps. The left subtree is first, the right subtree is second, the root node is first, and the middle node is middle

• Conversion between recursive algorithm and non-recursive algorithm

Take the middle order for example

void InOrder2(BiTree T)}{
    // A non-recursive algorithm for sequential traversal in a binary tree, which requires a stackInitStack(S); BiTree *p = T;// Initialize stack, p is traversal pointer
    while(p|| ! isEmpty(S)){// If p is not null or S is not null
        if(p){
            push(S,p);
            p = p->lchild;
        }else{ Pop(S,p); visit(p); p=p->prchild; }}}Copy the code

• Level traversal

• Construct binary tree from traversal sequence

A unique binary tree cannot be determined by preordering and postordering sequences

Cue binary tree

Traditional chain storage can only reflect a parent-child relationship and can not directly get the precursor and successor of nodes in traversal. The binary tree represented by binary linked list has a large number of null Pointers, which can be used to build the precursor and successor of nodes.

As mentioned earlier, a binary tree of n nodes has n null Pointers

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
Copy the code

Construction of binary tree of clue

// Middle order traversal to binary tree cueing
void InThread(ThreadTree &p.ThreadTree &pre){
    if(p! =null){ InThread(p->lchild,pre);// Recursively cue the left subtree
        if(p->lchild == NULL) {// The left subtree is empty, creating a precursor clue
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre! =NULL&&pre->rchild ==NULL){
            pre->rchild =p; // create a successor clue to the precursor
            pre->rtag = 1; } pre = p; InThread(p->rchild,pre); }}Copy the code

void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T! =NULL){
        InThread(T,pre);
        pre->rchild = NULL;
        pre->rtag = 1; }}Copy the code

You can set a header node whose Lchild field points to the root node of the binary tree and whose rChild field points to the last node visited by the middle traversal. At the same time, the pointer of lchild field of the first node and rchild field of the last node in the binary tree point to the head node. The binary tree can be traversed in two directions

Traversal of binary trees

// Find the first node under the middle sequence in the binary tree
ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag == 0)p=p->lchild; // Not necessarily a leaf
    return p;
}
// Find the next node of node P in the middle order binary tree
ThreadNode *Nextnode(ThreadNode *p){
    if(p->tag == 0) return Firstnode(p->rchild);
    else return p->rchild;
}
// middle order traversal
void Inorder(ThreadNode *T){
    for(ThreadNode *p = Firstnode(T); p! =NULL; p=Nextnode(p)) visit(p); }Copy the code