数据结构——树(下)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

数据结构——树(下)

简介: 二叉树、先序遍历、中序遍历、后序遍历、递归遍历、非递归遍历

1、二叉树的递归遍历

1、先序遍历

数据结构——树(下)图1.png

图示为

数据结构——树(下)图2.png

代码实现为

void PreOrderTraversal(BinTree BT){
    if (BT){
        cout << BT->Data;
        PreOrderTraversal(BT->left);
        PreOrderTraversal(BT->right);
    }

2、中序遍历

数据结构——树(下)图3.png

图示为

数据结构——树(下)图4.png

代码实现为

void InOrderTraversal(BinTree BT){
    if (BT){
        InOrderTraversal(BT);
        cout << BT->Data;
        InOrderTraversal(BT);
    }
}

3、后序遍历

数据结构——树(下)图5.png

图示为

数据结构——树(下)图6.png

代码实现为

void PostOrderTraversal(BinTree BT){
    if (BT){
        PostOrderTraversal(BT);
        PostOrderTraversal(BT);
        cout << BT->Data;
    }
}

重点说明:先序、前序和后序只是遍历过程中的访问各结点的顺序不同,但是经过的路线是一样的

2、二叉树的非递归遍历

​ 非递归算法的实现基本思路:使用堆栈

1、中序遍历非递归遍历方法

具体方法:

  • 遇到一个结点,就压栈,再去遍历它的左子树
  • 当左子树遍历完成时,从栈顶弹出这个结点并访问它
  • 然后按其右指针再去中序遍历该结点的右子树

代码实现为

void InOrderTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack(MAXSIZE);
    while (T || IsEmpty(S)) {
        while(T) {
            Push(S, T);
            T = T->left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S);
            cout << T->Data;
            T = T->right;
        }
    }
}

2、先序遍历非递归遍历方法

具体方法:

  • 当遇到一个结点,第一次遇到时直接输出,再去遍历它的左子树
  • 当左子树遍历完成,弹出左子树,再遍历右子树
  • 当右子树遍历完成,返回结点

代码实现为

void PreOrderTraversalTest(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack(MAXSIZE);
    while (T || IsEmpty(S)) {
        while(T) {
            Push(S, T);
                        cout << T->Data;
            T = T->left;
        }
        if (!IsEmpty(S)){
            T = Pop(S);
            T = T->right;
        }
    }
}

3、后序遍历非递归遍历方法

具体方法:

  • 从结点开始,一直压栈,直到最左子树
  • 弹出最左子树,返回结点,遍历右子树
  • 右子树遍历完毕,返回结点

代码实现为:

void PostOrdeTraversal(BinTree BT) {
    BinTree T = BT;
    BinTree pre = nullptr;        //储存当前结点的前一个结点 
    BinTree Ttop;        //储存栈顶元素
    Stack S = CreatStack(MAXSIZE);
    while(T || IsEmpty(s)) {
        while(T) {
            Push(T, S);
            T = T->left;
        }
        Ttop = Top(S);        //查看当前栈顶元素 
        if(Ttop->right == nullptr || Ttop->left == pre){
            //当前结点没有右子树或已被访问 
            cout << Ttop->Data;
            pre = Ttop;        //更新前一个结点的位置 
            Pop(S);
        }else{
            T = Ttop->right;        //开始访问右子树 
        }
    } 
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章