中序遍历知识讲解.docx

中序遍历目录1程序实现C++版本1 Java版本展开1程序实现C++版本1 Java版本展开中序遍历（LDR ）中序遍历也叫做中根遍历,可记做左根右 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树在遍历左、右子 树时，仍然先遍历左子树，再访问根结点，最后遍历右子树即： 若三叉树为空则结束返回， 否则： （1 ）中序遍历左子树 （2 ）访问根结点 （3 ）中序遍历右子树 注意的是：遍历左右子树时仍然采用中序遍历方法即左子树（B D E ）还是左边开始（D ）,然后是（B ）,再是右边（E），完 后经过（A），接着右子树（C F ）还是左边开始（F ）,再是中间（C ）, 即顺序是DBEAFC 中序遍历的时间复杂度为：0（n） 如果一颗二叉排序树的节点值是数值，中序遍历的结果为升序排 列的数组可以利用该性质检测一棵树是否为二叉排序数编辑本段程序实现C++版本树中节点结构为：{ int data; TreeNode TreeNode * parent; middle_order(TreeNode * Node) { middle_order(Node->left); middle_order(Node->right); middle_order(Root); //RootJava版本class TreeNode{TreeNode leftChild;public static void node){null){ return; }else{typedef struct TreeNode left; TreeNode * right; }TreeNode; void{ if(Node != NULL) printf(”％d ", Node->data); } 调用时：public int data; publicpublic TreeNode rightChild; inOrderTraversal(TreeNode if(node ==inOrderTraversal(node」eftC System.out.println(node.data);}为树的根hild);inOrderTRaversal(node.rightChild);。