6.3二叉树的遍历和线索（1）

Chilan Yu: “数据结构”目录链接zhuanlan.zhihu.com

6.3.1遍历二叉树

关于根: A，B，D，F，G，C，E二叉树的线索化，H

/*先序遍历二叉树（根左右）*/
void PreOrder(BiTree root){//先序遍历二叉树,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        Visit(root->data);//访问根结点
        PreOrder(root->LChild);//先序遍历左子树
        PreOrder(root->RChild);//先序遍历右子树
    }
}

注意: visit（）函数可以替换为其他一些必需的操作.

从左到右: B，F，D，G，A，C，E，H

/*中序遍历二叉树（左根右）*/
void InOrder(BiTree root){//中序遍历二叉树,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        InOrder(root->LChild);//中序遍历左子树
        Visit(root->data);//访问根结点
        InOrder(root->RChild);//中序遍历右子树
    }
}

注意: visit（）函数可以替换为其他一些必需的操作.

3. 后遍历（LRD）

左右根: F，G，D二叉树的线索化，B，H，E，C，A

/*后序遍历二叉树（左根右）*/
void PostOrder(BiTree root){//后序遍历二叉树,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        PostOrder(root->LChild);//后序遍历左子树
        PostOrder(root->RChild);//后序遍历右子树
        Visit(root->data);//访问根结点
    }
}

注意: visit（）函数可以替换为其他一些必需的操作.

4. 二叉树遍历的性质

知道前后遍历后，就不可能确定二叉树.

5. 得出遍历结果

众所周知，二叉树的前遍历序列是ABCDEF，而中层遍历序列CBAEDF. 该二叉树的后遍历结果是什么？

所以后遍历的结果是: CBEFDA

Chilan Yu: “数据结构”目录链接zhuanlan.zhihu.com

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-239483-1.html