数据结构函数题-创新互联

目录

求二叉树高度

二叉树的遍历

先序输出叶结点

统计二叉树结点个数

统计二叉树叶子结点个数

直接插入排序

冒泡排序

简单选择排序

折半插入排序

折半查找

有序数组的插入

本题要求给定二叉树的高度。

函数接口定义：

int GetHeight( BinTree BT );

其中BinTree结构定义如下：

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

要求函数返回给定二叉树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;
}

本题要求给定二叉树的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 )//第一种方法，若实现需要加上一些函数
{
 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);
	}
}

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。

void PreorderPrintLeaves( BinTree BT )
{
    if(BT==NULL)return;
    if(BT->Left==NULL && BT->Right==NULL)printf(" %c",BT->Data);//叶子结点就是左右都为空的结点
    PreorderPrintLeaves(BT->Left);
    PreorderPrintLeaves(BT->Right);
}

本题要求实现一个函数，可统计二叉树的结点个数。

int NodeCount ( BiTree T){
	int cnt = 0;
	if(T!=NULL){
		cnt++;//如果不为空则先自加1 
		cnt += NodeCount(T->lchild);//加上左子树的结点个数 
		cnt += NodeCount(T->rchild);//加上右子树的结点个数 
	}
	return cnt;//返回总的结点个数 
}

本题要求实现一个函数，可统计二叉树的叶子结点个数。

int LeafCount ( BiTree T)
{
    int count=0;
    
    if(T==NULL){//空树
        return 0;
    }else if(T->lchild==NULL && T->rchild==NULL){//只有一个根节点
        return count+1;
    }else {
        count=LeafCount(T->lchild)+LeafCount(T->rchild);//关系为左右相加求和
        return count;
    }
}

本题要求实现直接插入排序函数，待排序列的长度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;
            }
        }
    }
}

本题要求实现冒泡排序函数，待排序列的长度1<=n<=1000。

void bubble_sort(SqList 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;
			}
		}
	}
}

本题要求实现简单选择排序函数，待排序列的长度1<=n<=1000。

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

void BInsertSort(SqList &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;        //    设立low，Mid，H igh标志
	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;
}