二叉樹的操作(一)

二叉樹的操作

• • • • 二叉樹的周遊
      • • • 中序周遊
          • 先序周遊
          • 後序周遊
          • 層序周遊
      • 二叉樹葉結點的輸出算法
      • 二叉樹的高度算法

二叉樹的周遊

中序周遊

它是指對樹中任一結點的通路實在周遊玩其左子樹後進行的，通路此結點後，再對其右子數周遊。其周遊過程為：

1.中序周遊其左子樹

2.通路根結點

3.中序周遊其右子樹

代碼：

void InorderTraversal(BinTree BT)
{
	if(BT)
	{
		InorderTraversal(BT->Left);
		//此處假設對BT結點的通路就是列印資料
		printf("%d",BT->Data);//雞舍資料為整型
		InorderTraversal(BT->Right); 
	}
}
           

如圖所示：

先序周遊

它是指對結點的通路是在其左、右子樹周遊之前進行的，其周遊過程為：

1.通路根結點

2.先序周遊其左子樹

2.先序周遊其右子數

代碼：

void PreorderTraversal(BinTree BT)
{
	if(BT)
	{
		printf("%d",BT->Data);
		PreorderTraversal(BT->Left);
		PreorderTraversal(BT->Right);
	}
}
           

如圖所示：

後序周遊

它是指結點左右子樹的周遊先進行，然後才是對此結點的通路，其周遊過程為：

1.後序周遊其左子樹

2.後序周遊其右子樹

3.通路根結點

代碼

void PostorderTraversal(BinTree BT)
{
	if(BT)
	{
		PostorderTraversal(BT->Left);
		PostorderTraversal(BT->Right);
		printf("%d",BT->Data);
	}
}
           

如圖所示：

層序周遊

層序周遊的特點是從上到下，從左到右，其周遊過程為：（詳見“二叉樹的周遊–PTA”）

二叉樹葉結點的輸出算法

void PreorderPrintLeaves( BinTree BT )
{
    if(BT){
        if(!BT->Left&&!BT->Right)printf(" %c",BT->Data);
        if(BT->Left)PreorderPrintLeaves(BT->Left);
        if(BT->Right)PreorderPrintLeaves(BT->Right);
        
    }
}
           

二叉樹的高度算法

代碼

int GetHeight( BinTree BT )
{
	int HL,HR,MaxH;
	if(BT)
	{
		HL=GetHeight(BT->Left);
		HR=GetHeight(BT->Right);
		MaxH=HL>HR? HL:HR;
		return (MaxH+1);
	}
	else return 0;
}