C语言数据结构——遍历二叉树

古城微笑少年丶 2022-06-13 22:16 189阅读 0赞

1、二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每个节点被访问依次且仅被访问一次。

2、前序遍历：  
规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。  
![前序遍历][SouthEast]  
遍历的顺序为：1 2 4 8 5 3 6 9 10 7

/*前序遍历算法*/
    void PreOderTraverse(BiTree T)
    {
        if(T==NULL)
            return;
        printf("%c",T->data);  //显示结点数据，可以更改为其他对结点操作
        PreOderTraverse(T->lchild);   //先遍历左子树
        PreOderTraverse(T->rchild);    //最后遍历右子树 
     }

【操作】：调用PreOderTraverse(T)，T的结点不为NULL，所以执行printf,打印数字1；调用PreOderTraverse(T->lchild),调访问1的左孩子，不为NULL，执行printf显示数字2…….

3、中序遍历：  
若树为空树，则空操作返回，否则从根节点开始，中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。  
![中序遍历][SouthEast 1]  
遍历顺序为：4 8 2 5 1 9 6 10 3 7

/*中序遍历递归算法*/
    void InOderTraverse(BiTree T)
    {
        if(T==NULL)
            return ;
        InOderTraverse(T->lchild);   //中序遍历左子树
        printf("%c",T->data);   //显示结点数据，可以更改为其他对结点的操作
        InOderTraverse(T->rchild);  //最后中序遍历右子树 
     }

【操作】：调用InOderTraverse(T)，T的根节点不为NULL，于是调用InOderTraverse(T->lchild)，访问结点2.当前指针不为NULL,继续调用InOderTraverse(T->lchild)，访问结点4，不为NULL,继续调用InOderTraverse(T->lchild)，访问4的左孩子，发现当前指针为NULL,于是返回，打印当前结点4。然后调用InOderTraverse(T->rchild)，访问4的右孩子8，因为8没有左孩子，所以打印8，有因为8没有右孩子，返回，打印结点4的函数执行完毕，返回打印数字2。。。。。。

4、后序遍历：  
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。  
![后序遍历][SouthEast 2]  
遍历顺序为：8 4 5 2 9 10 6 7 3 1

/*后序遍历递归算法*/
    void PostOderTraverse(T)
    {
        if(T==NULL)
            return;
        PostOderTraverse(T->lchild);   //先遍历左子树 
        PostsOderTraverse(T->rchild);  //再遍历右子树 
        printf("%c",T->data);    //显示结点数可以更改为其他对结点数据 
     }

【操作】：由根节点1-2-4，结点4没有左孩子，再看结点4的右孩子8，由于8没有左右孩子，打印8，返回。。。。。。

5、层序遍历：  
若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。  
![层序遍历][SouthEast 3]  
遍历的顺序为：A B C D E F G H I

/*层序遍历*/
    void Tree<T>::Level_Order_Traverse(Tree_Node<T>* node)
    {
        queue<Tree_Node<T>*> Visit_Queue;
        Tree_Node<T>* temp;
        assert(node == root);
        Visit_Queue.push(node);//根节点入队
        while (Visit_Queue.size())
        {
                //输出队头元素
                temp = Visit_Queue.front();
                cout << temp->data<< " ";
                //弹出队头元素
                Visit_Queue.pop();
                //左右节点非空入队
                if (temp->left_node != NULL) Visit_Queue.push(temp->left_node);
                if (temp->right_node != NULL) Visit_Queue.push(temp->right_node);
        }
    
    }

[SouthEast]: /images/20220614/6bdb2b6bef8c444b903f8d950ad23322.png
[SouthEast 1]: /images/20220614/be2450ce6a024dcaac79b5d0e6a431cd.png
[SouthEast 2]: /images/20220614/0ad586f992a04790bd561ebc27f490a4.png
[SouthEast 3]: /images/20220614/21d60b3ddc7f4704812ca18577928c53.png