-
中序遍歷
鎖定
中序遍歷定義
中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。若二叉樹為空則結束返回，否則：
圖1
（2）訪問根結點
（3）中序遍歷右子樹
如圖1所示二叉樹，中序遍歷結果：DBEAFC
中序遍歷數學表達式形式
當對一棵數學表達式樹進行中序，前序和後序遍歷時，就分別得到表達式的中綴、前綴和後綴形式。中綴（infix）形式即平時所書寫的數學表達式形式，在這種形式中，每個二元操作符（也就是有兩個操作數的操作符）出現在左操作數之後，右操作數之前。在使用中綴形式時，可能會產生一些歧義。例如，x+y ×z可以理解為(x+y) ×z或x+ (y ×z)。為了避免這種歧義，可對操作符賦於優先級並採用優先級規則來分析中綴表達式。在完全括號化的中綴表達式中，每個操作符和相應的操作數都用一對括號括起來。更甚者把操作符的每個操作數也都用一對括號括起來。如( (x) + (y) )，( (x) + ( (y) * (z) ) )和( ( (x) + (y) ) * ( (y) + (z) ) ) * (w)。
[1]
中序遍歷複雜性
設二叉樹中元素數目為n，中序遍歷算法的空間複雜性均為O (n)，時間複雜性為(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);
}
}
}
中序遍歷C#版本
/*
public class BTNode //二叉樹節點類型
{
public BTNode lchild;
public BTNode rchild;
public char data;
}
*/
/*
public string btstr //全局變量
*/
public string InOrder(BTNode t)
{
btstr="";
InOrder1(r);
return btstr;
}
public string InOrder1(BTNode t)
{
if(t!=null)
{
InOrder(t.lchild);
bster+=t.data.ToString()+" ";
InOrder(t.rchild);
}
}中序遍歷pascal版本
核心代碼：
procedure mid(bt:tree); begin if bt<>nil then begin mid (bt^.left); write(bt^.data); mid (bt^.right); end; end;
