当前位置：首页 > article >正文

数据结构：二叉树的遍历和线索二叉树

article 2024/9/29 23:51:05

二叉树的遍历

二叉树的遍历是二叉树的一种重要的操作，指按照某种顺序访问树中的每个节点，并且每个节点仅被访问一次。常见的遍历方式有四种：前序遍历、中序遍历、后序遍历和层次遍历（或称为广度优先遍历）。

二叉树的定义类型：

typedef struct
{
    ElemType data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

前序遍历（Preorder Traversal）：

首先访问根节点，然后递归地进行前序遍历左子树，最后递归地进行前序遍历右子树。

//pre
void preorder(BiTree T){
    if(T!=NULL){
        visit(T);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

非递归算法：

void preorder2(BiTree T){
    InitStack(S);
    BiTree p=t;
    if(p||isEmpty(S)){
        if (p)
        {
            visit(p);
            push(S,p);
            p=p->lchild;
        }else{
            pop(S,p);
            p=p->rchild;
        }
        
    }
}

中序遍历（Inorder Traversal）：

首先递归地进行中序遍历左子树，然后访问根节点，最后递归地进行中序遍历右子树。

void inorder(BiTree T){
    if(T!=NULL){
        inorder(T->lchild);
        visit(T);
        inorder(T->rchild)
    }
}

非递归算法：

void inprder2(BiTree T){
    InitStack(S);
    BiTree P=T;
    if(p||isEmpty(S)){
        if(P){
            push(S,P);
            P=P->lchild;
        }else{
            pop(S,P);
            visit(P);
            P=P->rchild;
            }
    }
}

后序遍历（Postorder Traversal）：

首先递归地进行后序遍历左子树，然后递归地进行后序遍历右子树，最后访问根节点。

void postorder(BiTree T){
    if(T!=NULL){
        postorder(T->lchild);
        postorder(T->rchild);
        visit(T);
    }
}

层次遍历（Level-order Traversal）：

从上到下、从左到右依次访问树的每个节点。这通常需要使用队列来实现。

void levelorder(BiTree T){
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild)
        EnQueue(Q,p->lchild);
        else if(p->rchild)
        EnQueue(p->rchild);
    }
}

线索二叉树（存储结构）

线索二叉树是二叉树的一种变种，主要用于解决二叉树在遍历过程中“指针空域”的浪费问题。在普通二叉树中，每个节点有两个指针域，分别指向左右子节点，但在很多情况下，这两个指针域可能为空，这些空指针域就称为“空域”。线索二叉树就是将这些空域利用起来，存储指向该节点在某种遍历次序下的前驱和后继节点的指针（或线索）。

线索二叉树的实现

线索化：将二叉树中的空指针域改为线索的过程称为线索化。根据遍历方式的不同，可以构造出前序线索二叉树、中序线索二叉树和后序线索二叉树。

//线索二叉树定义的类型
typedef struct{
    `ElemType data;
    struct TreadNode * lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

//中序遍历线索化二叉树
void inthread(ThreadTree &p,ThreadTree &pre){
    if(p!=NULL){
        inthread(p->lchild,pre);
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;

        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        inthread(p->rchild,pre);
    }
}

//中序遍历构造线索二叉树
void createinorder(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){
        inthread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
    
}

//求线索二叉树的第一个结点
ThreadNode *FirstNode(ThreadNode *T){
    while(T->ltag!=1){
        T=T->lchild;
    }
    return T;
}

//求线索二叉树的结点的下一个结点
ThreadNode *NextNode(ThreadNode *T){
    if(T->rtag==0)
    return FirstNode(T->rchild);
    else
    return T->rchild;
}

//中序遍历线索二叉树
void inorder(ThreadNode *T){
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){
        visit(p);
    }
}

线索的表示：
- 引入两个布尔标志，ltag 和 rtag，分别表示左指针域和右指针域是否为线索。若 ltag=1，则 lchild 指向前驱；若 ltag=0，则 lchild 指向左子树。同理，若 rtag=1，则 rchild 指向后继；若 rtag=0，则 rchild 指向右子树。
遍历：在中序线索二叉树中，从根节点开始，若 ltag=1，则直接通过 lchild 访问前驱节点；否则，递归遍历左子树。遍历完左子树后，访问根节点，然后根据 rtag 决定是否直接通过 rchild 访问后继节点或递归遍历右子树。