二叉树-先序遍历(JAVA)

《二叉树-先序遍历(JAVA)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、9.1二叉树的遍历操作遍历操作：无重复无遗漏的访问二叉树的遍历：指的是从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次前序遍历中序遍历后序遍历9.1二叉树的遍历操作前序遍历（根遍历DLR）递归算法实现前序遍历也叫做先根遍历、先序遍历，可记做根左右。若二叉树为空，则空操作返回，否则（1）访问根节点（2）前序遍历根节点的左子树（3）前序遍历根节点的右子树注意的是：遍历左右子树时仍然采用前序遍历方法。BCDA若二叉树为空，则空操作返回，否则{（1）打印根节点B（2）DLR(D)（3）

2、DLR(NULL)}DLR（B）{}若二叉树为空，则空操作返回，否则{（1）打印根节点D（2）DLR(NULL)（3）DLR(NULL)}DLR（D）{}若二叉树为空，则空操作返回，否则{（1）打印根节点A（2）DLR(B)（3）DLR(C)}DLR（A）{}前序遍历（根遍历DLR）递归算法演示9.1二叉树的遍历操作preorder(binode*root){if(root==NULL)return;else{printf(“%d”,root->data);preorder(root->lchild);preorder

3、(“root->rchild”);}}前序遍历的递归算法ABCDEFGHK先序序列：ABCDEHGKF练习前序遍历下列二叉树，写出前序遍历序列ACBEDFGHIJ12435768910非递归前序遍历BCDELA前序的程序实现（非递归）：1、根结点进栈2、结点出栈，被访问3、结点的右、左儿子（非空）进栈4、反复执行2、3，至栈空为止。前序：A、L、B、E、C、De.g:A出栈访问L出栈访问B出栈访问E出栈访问C出栈访问D出栈访问后，栈空结束A进栈C、L进栈

4、E、B进栈D进栈分析：p的前序的直接后继q:1、p有左儿子，则q=该左儿子；2、p无左儿子，有右儿子，则q=该右儿子；3、p无左儿子、右儿子，搜索其祖先结点的右儿子送q。找不到结束。ABCFEDH步骤访问节点栈S的内容指针root初始空A1AAB2BABD3DABDNULL4ABH5HABHNULL6ABNULL7ANULL8空C9CCE10FCFNULL11CNULL12空E13EENULL14空NULLroot前序遍历9.1二叉树的遍历操作前序遍历（根遍历DLR）12387654109前序遍历的序列为：124895

5、103679.1二叉树的遍历操作前序分析：结点的左儿子、左孙子、左后代、……将连续输出。结点的右儿子将在结点、结点的左子树全部输出之后才输出。