目錄

求二叉樹(shù)高度

二叉樹(shù)的遍歷

先序輸出葉結(jié)點(diǎn)

統(tǒng)計(jì)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)

統(tǒng)計(jì)二叉樹(shù)葉子結(jié)點(diǎn)個(gè)數(shù)

直接插入排序

冒泡排序

簡(jiǎn)單選擇排序

折半插入排序

折半查找

有序數(shù)組的插入

本題要求給定二叉樹(shù)的高度。

函數(shù)接口定義：

int GetHeight( BinTree BT );

其中BinTree結(jié)構(gòu)定義如下：

typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };

要求函數(shù)返回給定二叉樹(shù)BT的高度值。

int GetHeight( BinTree BT ){
  if(BT == NULL){
    return 0;
  }
  int left = 1 + GetHeight(BT->Left);
  int right = 1 + GetHeight(BT->Right);
  return 1 +  left>right?left:right;
}

本題要求給定二叉樹(shù)的4種遍歷。

#define MAXSIZE 50
void InorderTraversal( BinTree BT )//中序遍歷 左根右 
{
 if(BT)
 {
  InorderTraversal(BT->Left);
  printf(" %c",BT->Data);
  InorderTraversal(BT->Right); 
 }
 } 
 void PreorderTraversal( BinTree BT )//先序遍歷(根左右)
 {
  if(BT){
	   printf(" %c",BT->Data);
	   PreorderTraversal(BT->Left);
	   PreorderTraversal(BT->Right);
	}
  } 
void PostorderTraversal( BinTree BT )//后序  左右根 
{
 if(BT)
 {
	  PostorderTraversal(BT->Left);
	  PostorderTraversal(BT->Right);
	  printf(" %c",BT->Data);
   }
}  
void LevelorderTraversal( BinTree BT )//第一種方法，若實(shí)現(xiàn)需要加上一些函數(shù)
{
 Queue Q;
 BinTree T;
 
 if(!BT) return ;
 
 Q = CreatQueue();
 AddQ(Q, BT);
 
 while(!IsEmpty(Q))
       {
	  T = DeleteQ(Q);
	  printf(" %c",T->Data);
	  if(T->Left)  AddQ(Q,T->Left);
	  if(T->Right) AddQ(Q,T->Right);
	}
}

本題要求按照先序遍歷的順序輸出給定二叉樹(shù)的葉結(jié)點(diǎn)。

void PreorderPrintLeaves( BinTree BT )
{
    if(BT==NULL)return;
    if(BT->Left==NULL && BT->Right==NULL)printf(" %c",BT->Data);//葉子結(jié)點(diǎn)就是左右都為空的結(jié)點(diǎn)
    PreorderPrintLeaves(BT->Left);
    PreorderPrintLeaves(BT->Right);
}

本題要求實(shí)現(xiàn)一個(gè)函數(shù)，可統(tǒng)計(jì)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)。

int NodeCount ( BiTree T){
	int cnt = 0;
	if(T!=NULL){
		cnt++;//如果不為空則先自加1 
		cnt += NodeCount(T->lchild);//加上左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) 
		cnt += NodeCount(T->rchild);//加上右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) 
	}
	return cnt;//返回總的結(jié)點(diǎn)個(gè)數(shù) 
}

本題要求實(shí)現(xiàn)一個(gè)函數(shù)，可統(tǒng)計(jì)二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)。

int LeafCount ( BiTree T)
{
    int count=0;
    
    if(T==NULL){//空樹(shù)
        return 0;
    }else if(T->lchild==NULL && T->rchild==NULL){//只有一個(gè)根節(jié)點(diǎn)
        return count+1;
    }else {
        count=LeafCount(T->lchild)+LeafCount(T->rchild);//關(guān)系為左右相加求和
        return count;
    }
}

本題要求實(shí)現(xiàn)直接插入排序函數(shù)，待排序列的長(zhǎng)度1<=n<=1000。

void  InsertSort(SqList L){
    int i,j;
    int temp;
    for(i=1;i<=L.Length;i++){
        for(j=i+1;j<=L.Length;j++){
            if(L.elem[i]>L.elem[j]){
                temp = L.elem[j];
                L.elem[j] = L.elem[i];
                L.elem[i] = temp;
            }
        }
    }
}

本題要求實(shí)現(xiàn)冒泡排序函數(shù)，待排序列的長(zhǎng)度1<=n<=1000。

void bubble_sort(SqList L){//創(chuàng)作不易，點(diǎn)個(gè)贊吧，新春快樂(lè)~
	int len = L.Length;
	for(int i=1; iL.elem[j+1]){
				int temp = L.elem[j];
				L.elem[j] = L.elem[j+1];
				L.elem[j+1] = temp;
			}
		}
	}
}

本題要求實(shí)現(xiàn)簡(jiǎn)單選擇排序函數(shù)，待排序列的長(zhǎng)度1<=n<=1000。

void  SelectSort(SqList L){
    int i, j, k, temp;
    for(i=1; i

void BInsertSort(SqList &L){//創(chuàng)作不易，點(diǎn)個(gè)贊吧，新春快樂(lè)~
	int low, high;
	for(int i=2; i<=L.length; i++){
		L.r[0] = L.r[i];
		low = 1;
		high = i-1;
		while(low<= high){
			int mid = (low+high)/2;
			if(L.r[0].key< L.r[mid].key)
				high = mid - 1;
			else
				low = mid + 1;
		}
		for(int j=i-1; j>=high+1; --j)
			L.r[j+1] = L.r[j];
		L.r[high+1] = L.r[0];
	}
}

int  Search_Bin(SSTable T, KeyType k)
{
	int Low, Mid, High;        //    設(shè)立low，Mid，H igh標(biāo)志
	Low = 1; High = T.length;    
	while (Lowk)
				High = Mid - 1;
			else
				return Mid;
	}
	return 0;
}

Position BinarySearch( List L, ElementType X )
{
 int low = 1, high = L->Last+1,mid;
 while (low<= high)
 {
       mid = (low + high) / 2;
        if (L->Data[mid]Data[mid]>X)
            low = mid + 1;
        else
            return 1;
 }
 return 0;

}
bool Insert(List L, ElementType X)
{
 int pos,i,j;
 if (L->Last + 1 >= MAXSIZE||1==BinarySearch(L, X)) return false;
    
 for ( i = 0; i<= L->Last; ++i)
  if (L->Data[i]<= X) break;
  pos=i;
 for (int j = L->Last;j>=pos; j--){
     L->Data[j+1] = L->Data[j];
 }  
  L->Data[pos] = X;
  L->Last++;
 return true;
}