数据结构——树的遍历

灰太狼 2022-06-17 03:36 261阅读 0赞

## 二叉树的遍历 ##

### 1.深度优先遍历 ###

#### 1.1先序遍历 ####

按照“根节点 - 左孩子 - 右孩子”的顺序进行访问  
先序遍历的递归实现代码如下：

void pre_traverse(BTree pTree)
    {
        if(PtRee)
        {
            printf("%c ",pTree->data);
            if(pTree->pLchild)
                pre_traverse(pTree->pLchild);
            if(pTree->pRchild)
                pre_traverse(pTree->pRchild);
        }
    }

先序遍历的非递归实现：  
实现思路如下：  
对于任一节点P，

1.  输出节点P，然后将其入栈，再看P的左孩子是否为空；
2.  若P的左孩子不为空，则置P的左孩子为当前节点，重复 1 的操作；
3.  若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4.  若不为空，则循环至 1 操作；
5.  如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复 4 和 5 的操作；
6.  直到当前节点P为NULL并且栈空，遍历结束。

void pre_traverse(BTree pTree)
    {
        BTree stack[100];         
        Btree node_pop;          //用来保存出栈节点
        Btree pCur = pTree;        //用来指向当前访问的节点的指针
        int size = -1;
        while(pCur != NULL || size != -1)
        {
            printf("%c ",pCur->data);
            size++;
            stack[size] = pCur;
            pCur = pCur->left;
            while(pCur == NULL && size == -1)
            {
                node_pop = stack[size];
                size--;
                pCur = node_pop->right;
            }
        }
    }

#### 1.2中序遍历 ####

按照“左孩子 - 根节点 - 右孩子”的顺序进行访问

中序遍历的递归实现代码：

void in_traverse(Tree tree)
    {
        if(tree)
        {
            if(tree->left)
                in_traverse(tree->left);
            printf("%c ",tree->data);
            if(tree->right)
                in_traverse(tree->right);
        }
    }

中序遍历的非递归实现：  
实现思路：  
对于任一节点P，

1.  若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2.  若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3.  若不为空，则重复 1 和 2 的操作；
4.  若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看其是否为空，重复 3 和 4 的操作；
5.  知道当前节点P为NULL并且栈为空，则遍历结束。

void in_praverse(Tree tree)
    {
        Tree stack[100];
        Tree node_pop;                
        Tree pCur = tree;            //指向当前节点
        int size = -1;
        while(pCur != NULL || size != -1)
        {
            if(pCur->left != NULL)
            {
                size++;
                stack[size] = pCur;
                pCur = pCur->left;
            }
            else
            {
                printf("%c ",pCur->data);
                pCur = pCur->right;
                while(pCur == NULL && size != -1)
                {
                    node_pop = stack[size];
                    size--;
                    printf("%c ",node_pop->data);
                    pCur = node_pop->right;
    
                }
            }
        }
    }

#### 1.3后序遍历 ####

按照“左孩子 - 右孩子 - 根节点”的顺序进行访问

后序遍历的递归方法实现代码：

void beh_traverse(Tree tree)
    {
        if(tree)
        {
            if(tree->left)
                beh_traverse(tree->left);
            if(tree->right)
                beh_traverse(tree->right);
            printf("%c ",tree->data);
        }
    }

后序遍历的非递归方法实现：

实现思路如下：  
对于任一节点P，

1.  先将节点P入栈；
2.  若P不存在左孩子和右孩子，或者存在左孩子或者右孩子，但是左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶节点设为当前节点；
3.  若不满足 2 中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶节点，之后重复操作 2 ；
4.  直到栈空，遍历结束。

void beh_traverse(Tree tree)
    {
        Tree stack[100];
        Tree node_pop;
        Tree pCur = tree;                    //指向当前节点
        Tree pre = NULL;                     //指向上一个访问的节点
        int size = 0;
        stack[size] = pCur;
        while(size != -1)
        {
            if((pCur->left == NULL && pCur->right == NULL)||
                (pre!=NULL && (pCur->left == pre || pCur->right == pre)))
            {
                printf("%c ",pCur->data);
                node_pop = stack[size];
                size--;
                pre = node_pop;
            }
            else
            {
                if(pCur->right != NULL)
                {
                    size++;
                    stack[size] = pCur->right;
                }
                if(pCur->left != NULL)
                {
                    size++;
                    stack[size] = pCur_left;
                }
            }
        }
    }

### 2.广度优先遍历 ###

对于广度优先遍历二叉树，也就是按层次的去遍历，依次遍历根节点，然后是左孩子和右孩子，所以要遍历完当前节点的所有孩子。

二叉树的广度优先遍历代码：

void BreadthFirstTravel(Tree* root)
    {
        queue<Tree*> data;
        data.push(root);
        while(!data.empty()) {
            Tree* tmp = data.front();
            if(tmp->left) 
                data.push(tmp->left);
            if(tmp->right) 
                data.push(tmp->right);
            cout<<tmp->value<<emdl;
            data.pop();
        }
    }