中序遍历

编辑:敬礼网互动百科 时间:2020-04-04 00:25:27
编辑 锁定
中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游,可记做左根右。
中文名
中序遍历
外文名
LDR
解    释
二叉树遍历的一种
也叫做
中根遍历

中序遍历简介

编辑
中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。即:
二叉树为空则结束返回
否则:
(1)中序遍历左子树。
(2)访问根结点。
(3)中序遍历右子树。
中序遍历 中序遍历
注意的是:遍历左右子树时仍然采用中序遍历方法。
如右图所示二叉树
中序遍历结果:DBEAFC
中序遍历的时间复杂度为:O(n)。
如果一棵二叉排序树的节点值是数值,中序遍历的结果为升序排列的数组。可以利用该性质检测一棵树是否为二叉排序数。
已知前序遍历和后序遍历,不能确定唯一的中序遍历。

中序遍历投影法

编辑
计算中序遍历拥有比较简单直观的投影法,如图
中序遍历的投影法 中序遍历的投影法

中序遍历程序实现

编辑

中序遍历c++版本

树中节点结构为:
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
} TreeNode;

void middle_order(TreeNode *Node) {
    if(Node != NULL) {
        middle_order(Node->left);
        printf("%d ", Node->data);
        middle_order(Node->right);
    }
}

调用时: middle_order(Root); //Root为树的根

中序遍历Java版本

class TreeNode{
    public int data;
    public TreeNode leftChild;
    public TreeNode rightChild;
    public static void inOrderTraversal(TreeNode node){
        if(node == null){
            return;
        }else{
            inOrderTraversal(node.leftChild);
        System.out.println(node.data);
        inOrderTRaversal(node.rightChild);
        }
    }
}

中序遍历pascal版本

核心代码:
procedure mid(bt:tree);
begin
    if bt<>nil then begin
        mid (bt^.left);
        write(bt^.data);
        mid (bt^.right);
    end;
end;
词条标签:
计算机学