天天看點

Data Structure1.在實作二叉樹碰到的問題Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType));2.二叉樹的順序存儲實作(存儲在數組中)3.這個版本的二叉樹順序實作比較好了解

Data Structure FQA

文章目錄

  • 1.在實作二叉樹碰到的問題Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
  • 2.二叉樹的順序存儲實作(存儲在數組中)
  • 3.這個版本的二叉樹順序實作比較好了解

1.在實作二叉樹碰到的問題Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType));

Status(Visit)(TElemType)這是函數指針

本質是一個指針,該指針的位址指向了一個函數,是以它是指向函數的指針。我們知道,函數的定義是存在于代碼段,是以,每個函數在代碼段中,也有着自己的入口位址,函數指針就是指向代碼段中函數入口位址的指針。

函數指針的聲明方法為:

傳回值類型 ( * 指針變量名) ([形參清單]);

注1:“傳回值類型”說明函數的傳回類型,“(指針變量名 )”中的括号不能省,括号改變了運算符的優先級。若省略整體則成為一個函數說明,說明了一個傳回的資料類型是指針的函數,後面的“形參清單”表示指針變量指向的函數所帶的參數清單。例如:

int func(int x); /* 聲明一個函數 */

int (*f) (int x); /* 聲明一個函數指針 */

f=func; /* 将func函數的首位址賦給指針f */

或者使用下面的方法将函數位址賦給函數指針:

f = &func;

指派時函數func不帶括号,也不帶參數,由于func代表函數的首位址,是以經過指派以後,指針f就指向函數func(x)的代碼的首位址。

注2:函數括号中的形參可有可無,視情況而定。
           

詳細内容移步

(*visit)(TElemType e )函數指針了解

2.二叉樹的順序存儲實作(存儲在數組中)

在輸入過程中,前序序列必須輸入完整帶空結點^的序列

#include <stdio.h>
#include <stdlib.h>    
#include <string.h>    
#include <math.h>      
/* 狀态碼 */
#define TRUE        1   // 真/是
#define FALSE       0   // 假/否
#define OK          1   // 通過/成功
#define ERROR       0   // 錯誤/失敗

#define MAX_TREE_SIZE 1024 
/* 狀态碼類型 */
typedef int Status;

typedef char TElemType;

typedef TElemType SqBiTree[MAX_TREE_SIZE];

     

// 測試函數,列印元素
Status PrintElem(TElemType c) {
    printf("%c", c);
    return OK;
}


// 先序周遊的内部實作
static Status PreTraverse(SqBiTree T, Status(Visit)(TElemType), int i) {
    // 越界
    if(i >= MAX_TREE_SIZE) {
        return ERROR;
    }
    
    if(T[i]) {
        if(Visit(T[i])) {
            if(PreTraverse(T, Visit, 2 * i + 1)) {
                if(PreTraverse(T, Visit, 2 * i + 2)) {
                    return OK;
                }
            }
        }
    
        return ERROR;
    
        // 遇到空樹則無需繼續計算
    } else {
        return OK;
    }
}

// 中序周遊的内部實作
static Status InTraverse(SqBiTree T, Status(Visit)(TElemType), int i) {
    // 越界
    if(i >= MAX_TREE_SIZE) {
        return ERROR;
    }
    
    if(T[i]) {
        if(InTraverse(T, Visit, 2 * i + 1)) {
            if(Visit(T[i])) {
                if(InTraverse(T, Visit, 2 * i + 2)) {
                    return OK;
                }
            }
            
        }
        
        return ERROR;
        
        // 遇到空樹則無需繼續計算
    } else {
        return OK;
    }
}

// 後序周遊的内部實作
static Status PostTraverse(SqBiTree T, Status(Visit)(TElemType), int i) {
    // 越界
    if(i >= MAX_TREE_SIZE) {
        return ERROR;
    }
    
    if(T[i]) {
        if(PostTraverse(T, Visit, 2 * i + 1)) {
            if(PostTraverse(T, Visit, 2 * i + 2)) {
                if(Visit(T[i])) {
                    return OK;
                }
                
            }
        }
        
        return ERROR;
        
        // 遇到空樹則無需繼續計算
    } else {
        return OK;
    }
}




Status InitBiTree(SqBiTree T){
	memset(T, '\0', sizeof(SqBiTree));
	return 1;
}

int DestroyBiTree(SqBiTree T) {
    // 二叉樹的順序存儲結構無法銷毀
    return 0;
}

Status ClearBiTree(SqBiTree T) {
    // 使用空字元填充二叉樹的順序結構
    memset(T, '\0', sizeof(SqBiTree));
    
    return OK;
}

// 建立二叉樹的内部函數
static void CreateTree(SqBiTree T, int i) {
 	
    char ch;
    scanf("%c", &ch);
    
    if(ch == '^') {
        T[i] = '\0';
    } else {
        T[i] = ch;
        printf("%c",T[i]);
        CreateTree(T, 2 * i + 1); // 建立左子樹
        CreateTree(T, 2 * i + 2); // 建立右子樹
    }
}



Status CreateBiTree(SqBiTree T) { 
    printf("請輸入二叉樹的先序序列,如果沒有子結點,使用^代替:\n");
    CreateTree(T, 0);  
    return OK;
}




Status BiTreeEmpty(SqBiTree T) {
    return T[0] == '\0' ? 1 : 0;
}


// 求二叉樹深度的内部函數
static int TreeDepth(SqBiTree T, int i) {
    int ld, rd;     // 記錄左右子樹的深度
    
    if(T[i] == '\0') {
        return 0;
    } else {
        ld = TreeDepth(T, 2 * i + 1);
        rd = TreeDepth(T, 2 * i + 2);
        
        return (ld >= rd ? ld : rd) + 1;
    }
}

int BiTreeDepth(SqBiTree T) {
    return TreeDepth(T, 0);
}



Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
    Status status;
    status = PreTraverse(T, Visit, 0);
    printf("\n");
    
    return status;
}

/*
 * 中序周遊
 */
Status InOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
    Status status;
    
    status = InTraverse(T, Visit, 0);
    printf("\n");
    
    return status;
}

/*
 * 後序周遊
 */
Status PostOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
    Status status;
    
    status = PostTraverse(T, Visit, 0);
    printf("\n");
    
    return status;
}

/*
 * 層序周遊
 */
Status LevelOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
    int i;
    int deep;
    int len;
    
    // 二叉樹層數
    deep = BiTreeDepth(T);
    if(deep == 0) {
        return OK;
    }
    
    // 二叉樹元素數量(最大值)
    len = (int) pow(2, deep) - 1;
    
    for(i = 0; i < len; i++) {
        if(T[i] != '\0') {
            if(!Visit(T[i])) {
                // 如果遇到通路錯誤,會即時傳回
                return ERROR;
            }
        }
    }
    
    printf("\n");
    
    return OK;
}

// 傳回二叉樹結點e的索引号,i是結點p的索引号
static int EIndex(SqBiTree T, TElemType e, int i) {
    int cl, cr;
    
    // 已經越界
    if(i >= MAX_TREE_SIZE) {
        return -1;
    }
    
    // e的值不合規
    if(e == '\0') {
        return -1;
    }
    
    // 找到了元素e
    if(T[i] == e) {
        return i;
    }
    
    // 在左子樹中查找
    cl = EIndex(T, e, 2 * i + 1);
    if(cl != -1) {
        return cl;
    }
    
    // 在右子樹中查找
    cr = EIndex(T, e, 2 * i + 2);
    if(cr != -1) {
        return cr;
    }
    
    return -1;
}

// 摘下二叉樹T中的子樹i,将其插入為二叉樹R的子樹j
static void Transfer(SqBiTree T, int i, SqBiTree R, int j) {
    R[j] = T[i];
    
    if(T[i] != '\0') {
        Transfer(T, 2 * i + 1, R, 2 * j + 1);
        Transfer(T, 2 * i + 2, R, 2 * j + 2);
        T[i] = '\0';
    }
}

// 删除二叉樹T中的子樹i
static void Delete(SqBiTree T, int i) {
    if(T[i] != '\0') {
        T[i] = '\0';
        Delete(T, 2 * i + 1);
        Delete(T, 2 * i + 2);
    }
}


/*
 * 取值
 *
 * 傳回二叉樹中指定結點的值。
 */
TElemType Value(SqBiTree T, TElemType e) {
    int index;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return '\0';
    } else {
        return T[index];
    }
}

/*
 * 指派
 *
 * 為二叉樹指定的結點指派。
 */
Status Assign(SqBiTree T, TElemType e, TElemType value) {
    int index;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return ERROR;
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return ERROR;
    } else {
        // 進行指派
        T[index] = value;
        return OK;
    }
}

/*
 * 根
 *
 * 傳回二叉樹的根結點。
 */
TElemType Root(SqBiTree T) {
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    return T[0];
}

/*
 * 雙親
 *
 * 傳回二叉樹中結點e的雙親結點。
 */
TElemType Parent(SqBiTree T, TElemType e) {
    int index;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return '\0';
        
        // 如果e是根結點
    } else if(index == 0) {
        return '\0';
    } else {
        // 傳回父結點
        return T[(index - 1) / 2];
    }
}

/*
 * 左孩子
 *
 * 傳回二叉樹中結點e的左孩子結點。
 */
TElemType LeftChild(SqBiTree T, TElemType e) {
    int index;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return '\0';
    } else {
        // 傳回左孩子
        return T[2 * index + 1];
    }
}

/*
 * 右孩子
 *
 * 傳回二叉樹中結點e的右孩子結點。
 */
TElemType RightChild(SqBiTree T, TElemType e) {
    int index;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return '\0';
    } else {
        // 傳回右孩子
        return T[2 * index + 2];
    }
}

/*
 * 左兄弟
 *
 * 傳回二叉樹中結點e的左兄弟結點。
 */
TElemType LeftSibling(SqBiTree T, TElemType e) {
    int index, p;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return '\0';
        
        // 如果e是根結點
    } else if(index == 0) {
        return '\0';
    } else {
        // 擷取父結點的索引
        p = (index - 1) / 2;
        
        // 如果結點e是右孩子,則傳回其左兄弟
        if(T[2 * p + 2] == e) {
            return T[2 * p + 1];
        } else {
            return '\0';
        }
    }
}

/*
 * 右兄弟
 *
 * 傳回二叉樹中結點e的右兄弟結點。
 */
TElemType RightSibling(SqBiTree T, TElemType e) {
    int index, p;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return '\0';
    }
    
    // 擷取結點e的索引
    index = EIndex(T, e, 0);
    
    // 如果沒有找到元素e
    if(index == -1) {
        return '\0';
        
        // 如果e是根結點
    } else if(index == 0) {
        return '\0';
    } else {
        // 擷取父結點的索引
        p = (index - 1) / 2;
        
        // 如果結點e是左孩子,則傳回其右兄弟
        if(T[2 * p + 1] == e) {
            return T[2 * p + 2];
        } else {
            return '\0';
        }
    }
}

/*
 * 插入
 *
 * 已知c為與T不相交的非空二叉樹,且c的右子樹為空,
 * 根據LR的取值(0或1),将c插入為T中結點p的左子樹/右子樹,
 * 并且,将p結點原有的左子樹/右子樹嫁接為二叉樹c的右子樹。
 */
Status InsertChild(SqBiTree T, TElemType p, int LR, SqBiTree c) {
    int index;
    
    // 如果待插入的樹為空樹則無需繼續計算
    if(BiTreeEmpty(c)) {
        return ERROR;
    }
    
    // 擷取結點p的索引
    index = EIndex(T, p, 0);
    
    // 如果p結點不存在,則傳回錯誤提示
    if(index == -1) {
        return ERROR;
    }
    
    // 将c插入為p的左子樹
    if(LR==0) {
        // 如果p處存在左子樹
        if(T[2*index+1]!='\0') {
            // 将p的左子樹插入為c的右子樹
            Transfer(T, 2*index+1, c, 2);
        }
    
        Transfer(c, 0, T, 2*index+1);
        
        // 将c插入為p的右子樹
    } else {
        // 如果p處存在右子樹
        if(T[2*index+2]!='\0') {
            // 将p的右子樹插入為c的右子樹
            Transfer(T, 2*index+2, c, 2);
        }
    
        Transfer(c, 0, T, 2*index+2);
    }
    
    return OK;
}

/*
 * 删除
 *
 * 根據LR的取值(0或1),删除結點p的左子樹/右子樹。
 */
Status DeleteChild(SqBiTree T, TElemType p, int LR) {
    int index;
    
    // 如果待删除的樹為空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        return ERROR;
    }
    
    // 擷取結點p的索引
    index = EIndex(T, p, 0);
    
    // 如果待删除結點不存在,則傳回錯誤提示
    if(index == -1) {
        return ERROR;
    }
    
    // 如果需要删除p的左子樹
    if(LR == 0) {
        Delete(T, 2 * index + 1);
        
        // 如果需要删除p的右子樹
    } else {
        Delete(T, 2 * index + 2);
    }
    
    return OK;
}










void PrintTree(SqBiTree T) {
    int level, width;
    int i, j, k, w;
    int begin;
    int distance;
    TElemType** tmp;
    
    // 遇到空樹則無需繼續計算
    if(BiTreeEmpty(T)) {
        printf("\n");
        return;
    }
    
    level = BiTreeDepth(T);         // (完全)二叉樹結構高度
    width = (int)pow(2, level)-1;   // (完全)二叉樹結構寬度
    
    // 動态建立行
    tmp = (TElemType**)malloc(level* sizeof(TElemType*));
    
    // 動态建立列
    for(i = 0; i < level; i++) {
        tmp[i] = (TElemType*)malloc(width* sizeof(TElemType));
    
        // 初始化記憶體值為空字元
        memset(tmp[i], '\0', width);
    }
    
    // 周遊樹中所有元素,将其安排到二維數組tmp中合适的位置
    for(i = 0; i < level; i++) {
        w        = (int) pow(2, i);             // 二叉樹目前層的寬度
        distance = width / w;                   // 二叉樹目前層的元素間隔
        begin    = width / (int) pow(2, i + 1); // 二叉樹目前層首個元素之前的空格數
        
        for(k = 0; k < w; k++) {
            j = begin + k * (1 + distance);
            tmp[i][j] = T[(int) pow(2, i) + k - 1];
        }
    }

    for(i = 0; i < level; i++) {
        for(j = 0; j < width; j++) {
            if(tmp[i][j] != '\0') {
                printf("%c", tmp[i][j]);
            } else {
                printf(" ");
            }
        }
        printf("\n");
    }
}



int main(){
	SqBiTree T;
	 printf("████████ InitBiTree \n");
    {
        printf("█ 初始化空二叉樹 T ...\n");
        int a;
        a = InitBiTree(T);
        printf("%d\n",a);
    }

    
    printf("████████ CreateBiTree \n");
    {
        printf("█ 按先序序列建立二叉樹 T ...\n");
		CreateBiTree(T);   
    }
    
    printf("████████ BiTreeDepth \n");
    {
        printf("█ 二叉樹 T 的深度為:%d \n", BiTreeDepth(T));
    }
    
    printf("████████ PrintTree \n");
    {
        printf("█ 按二叉樹的結構列印樹 T ...\n");
        PrintTree(T);
    }
    
        printf("████████ PreOrderTraverse \n");
    {
        printf("█ 前序周遊二叉樹 T = ");
        PreOrderTraverse(T, PrintElem);
    }

    
    
    printf("████████ InOrderTraverse \n");
    {
        printf("█ 中序周遊二叉樹 T = ");
        InOrderTraverse(T, PrintElem);
    }

    
    
    printf("████████ PostOrderTraverse \n");
    {
        printf("█ 後序周遊二叉樹 T = ");
        PostOrderTraverse(T, PrintElem);
    }

    
    
    printf("████████ LevelOrderTraverse \n");
    {
        printf("█ 層序周遊二叉樹 T = ");
        LevelOrderTraverse(T, PrintElem);
    }

    
    
    printf("████████ Value \n");
    {
        TElemType e = 'F';
        printf("█ 結點 %c 的值為 %c\n", e, Value(T, e));
    }

    
    
    printf("████████ Assign \n");
    {
        TElemType e = 'F';
        TElemType value = 'X';
        printf("█ 将結點 %c 指派為 %c 後,T = \n", e, value);
        Assign(T, e, value);
        PrintTree(T);
    }

    
    
    printf("████████ Root \n");
    {
        printf("█ T 的根結點為 %c\n", Root(T));
    }

    
    
    printf("████████ Parent \n");
    {
        TElemType e = 'E';
        printf("█ 結點 %c 的雙親為:%c \n", e, Parent(T, e));
    }

    
    
    printf("████████ LeftChild、RightChild \n");
    {
        TElemType e = 'E';
        printf("█ 結點 %c 的左孩子結點值為:%c ,右孩子結點值為:%c\n", e, LeftChild(T, e), RightChild(T, e));
    }

    
    
    printf("████████ LeftSibling \n");
    {
        TElemType e = 'I';
        printf("█ 結點 %c 的左兄弟為:%c\n", e, LeftSibling(T, e));
    }

    
    
    printf("████████ RightSibling \n");
    {
        TElemType e = 'H';
        printf("█ 結點 %c 的右兄弟為:%c\n", e, RightSibling(T, e));
    }
    return 0;
}
           

3.這個版本的二叉樹順序實作比較好了解

代碼實作來自部落格Mogon_girl

#include<stdio.h>
#include<stdlib.h> 
#include <string.h> 
#include<cmath>
#include <math.h>      
/* 狀态碼 */
#define TRUE        1   // 真/是             ABCDE^F^^G    A B D E G C F
#define FALSE       0   // 假/否
#define OK          1   // 通過/成功
#define ERROR       0   // 錯誤/失敗
typedef int Status;


#define MAX_TREE_SIZE 100//二叉樹的最大結點數 
typedef char ElemType;
typedef ElemType SqBiTree[MAX_TREE_SIZE];//0号單元存儲根節點
//typedef struct{
//	int level;//結點所在層 
//	int order;//結點在本層序号(按完全二叉樹計算) 
//}Pos; 

//1.構造空二叉樹T
void InitBiTree_Sq(SqBiTree &T){
	for(int i=0;i<MAX_TREE_SIZE;i++){
		T[i]='\0';//空樹無結點,以空字元填充數組 
	}
}
//5.按層序序列構造二叉樹
void CreateBiTree_Le_Sq(SqBiTree &T){
	char ch;
	int i=0;
	while(1){
		ch=getchar();
		if(ch=='\n')break;
		if(ch=='^'){
			T[i++]='\0';
		}else{
			T[i++]=ch;
		}
	}
}
//7.傳回二叉樹長度
int BiTreeLength_Sq(SqBiTree T){
	int len; 
	for(len=MAX_TREE_SIZE;len-1>=0;len--){
		if(T[len-1]!='\0'){	
			break;
		}
	}
	return len;
} 
 
//8.傳回二叉樹深度(層數)
BiTreeDepth_Sq(SqBiTree T){
	int level=0;
	while((int)pow(2,level)-1<BiTreeLength_Sq(T)){
		level++;
	}
	return level;
}
//17.層次周遊二叉樹 
void LevelOrderTraverse_Sq(SqBiTree T){
	int len=BiTreeLength_Sq(T);
	for(int i=0;i<len;i++){
		if(T[i]!='\0'){
			printf("%c ",T[i]);
		}
	}
	printf("\n");
}
//18.前序周遊二叉樹
void PreOrderTraverse_Sq(SqBiTree T,int i){
	if(T[i]!='\0'){
		printf("%c ",T[i]);
		PreOrderTraverse_Sq(T,2*i+1);
		PreOrderTraverse_Sq(T,2*i+2);
	} 
}
//19.中序周遊二叉樹
void InOrderTraverse_Sq(SqBiTree T,int i){
	if(T[i]!='\0'){
		InOrderTraverse_Sq(T,2*i+1);
		printf("%c ",T[i]);
		InOrderTraverse_Sq(T,2*i+2);
	} 
} 
//20.後序周遊二叉樹
void PostOrderTraverse_Sq(SqBiTree T,int i){
	if(T[i]!='\0'){
		PostOrderTraverse_Sq(T,2*i+1);
		PostOrderTraverse_Sq(T,2*i+2);
		printf("%c ",T[i]);
	} 
}

void PrintTree(SqBiTree T) {
    int level, width;
    int i, j, k, w;
    int begin;
    int distance;
    ElemType** tmp;
    
    
    level =BiTreeDepth_Sq(T);         // (完全)二叉樹結構高度
    width = (int)pow(2, level)-1;   // (完全)二叉樹結構寬度
    
    // 動态建立行
    tmp = (ElemType**)malloc(level* sizeof(ElemType*));
    
    // 動态建立列
    for(i = 0; i < level; i++) {
        tmp[i] = (ElemType*)malloc(width* sizeof(ElemType));
    
        // 初始化記憶體值為空字元
        memset(tmp[i], '\0', width);
    }
    
    // 周遊樹中所有元素,将其安排到二維數組tmp中合适的位置
    for(i = 0; i < level; i++) {
        w        = (int) pow(2, i);             // 二叉樹目前層的寬度
        distance = width / w;                   // 二叉樹目前層的元素間隔
        begin    = width / (int) pow(2, i + 1); // 二叉樹目前層首個元素之前的空格數
        
        for(k = 0; k < w; k++) {
            j = begin + k * (1 + distance);
            tmp[i][j] = T[(int) pow(2, i) + k - 1];
        }
    }

    for(i = 0; i < level; i++) {
        for(j = 0; j < width; j++) {
            if(tmp[i][j] != '\0') {
                printf("%c", tmp[i][j]);
            } else {
                printf(" ");
            }
        }
        printf("\n");
    }
}
int main(){
	SqBiTree T;
	printf("————————————————————————————△初始化空二叉樹\n");
	InitBiTree_Sq(T);//初始化 
	printf("————————————————————————————△層次序列建立\n");
	CreateBiTree_Le_Sq(T);
	printf("————————————————————————————△深度和長度\n");
	printf("此時T的長度為:%d,深度為:%d\n",BiTreeLength_Sq(T),BiTreeDepth_Sq(T));
	int len=BiTreeLength_Sq(T);
	printf("————————————————————————————△層序周遊\n");
	LevelOrderTraverse_Sq(T);
	printf("————————————————————————————△前序周遊\n");
	PreOrderTraverse_Sq(T,0);
	printf("\n");
	printf("————————————————————————————△中序周遊\n");
	InOrderTraverse_Sq(T,0);
	printf("\n");
	printf("————————————————————————————△後序周遊\n");
	PostOrderTraverse_Sq(T,0);
	printf("████████ PrintTree \n");
	PrintTree(T);
	return 0;
}