博客

1、编写程序，从键盘输入10个整数，逐个插入到二叉排序树中。根据你输入的整数序列，在草稿纸上画出该树。

（1）分别用先序、中序、后序遍历该树并输出结果，检查结果是否正确。

（2）输出该树的高度，检查结果是否正确。

（3）输出结点总数，检查结果是否正确。

（4）从树中删除一个整数，遍历该树并输出，检查结果是否正确。

#include<stdio.h>
#include<stdlib.h>
struct TreeNode { 
    int Data;
    struct TreeNode * Left;
    struct TreeNode * Right;
};
struct TreeNode* creattree(int x){
	struct TreeNode* T;
	T=(TreeNode*)malloc(sizeof(struct TreeNode));
	T->Data=x;
	T->Left=NULL;
	T->Right=NULL;
	return T;	
}
int paixutree(struct TreeNode* T,int x){
	if(x>T->Data){
		if(T->Right==NULL)
		T->Right=creattree(x);
		else
		T=T->Right;
		paixutree(T,x);		
	} 
	else if(x<T->Data){
		if(T->Left==NULL)
		T->Left=creattree(x);
		else
		T=T->Left;
		paixutree(T,x);		
	} 
	else
	return 0;
}
void PreOrder(struct TreeNode *T) {
    if (T != NULL) {
        printf("%d ", T->Data); /* 假设数据为整数 */
        PreOrder(T->Left);
        PreOrder(T->Right);
    }
    
}
void InOrder(struct TreeNode *T) {
    if (T != NULL) {
        InOrder(T->Left);
        printf("%d ", T->Data); /* 假设数据为整数 */
        InOrder(T->Right);
    }
    
}
void PostOrder(struct TreeNode *T) {
    if (T != NULL) {
        PostOrder(T->Left);
        PostOrder(T->Right);
        printf("%d ", T->Data); /* 假设数据为整数 */
    }
    
}

int Height(struct TreeNode *T) {
    if (T == NULL)
        return 0;
    else{
	int l=Height(T->Left);
	int r=Height(T->Right);
        if(l>r)
		return l+1;
		else return r+1;}
}
int Count(struct TreeNode *T) {
    if (T == NULL)
        return 0;
    return 1 + Count(T->Left) + Count(T->Right);
}

struct TreeNode * FindMin(struct TreeNode *T) {
    if (T == NULL)
        return NULL;
    return (T->Left == NULL) ? T : FindMin(T->Left);
}

struct TreeNode * Delete(struct TreeNode *T, int X) {
    struct TreeNode *q;

    if (T == NULL)
        return T;
    else if (X < T->Data)
        T->Left = Delete(T->Left, X);
    else if (X > T->Data)
        T->Right = Delete(T->Right, X);
    else  { /* X == T->Data */
        if (T->Left != NULL && T->Right != NULL) { /* 左右子树不空 */
            q = FindMin(T->Right);
            T->Data = q->Data;
            T->Right = Delete(T->Right, q->Data);
        } else { /* 左右子树至少有一个为空 */
            q = T;
            if (T->Left == NULL)
                T = T->Right;
            else if (T->Right == NULL)
                T = T->Left;
            free(q);
        }
    }

    return T;
}


int main(){
	int a;
	struct TreeNode* T;
    printf("请输入十个数后回车:\n");
	scanf("%d",&a);
	T=creattree(a);
	
	for(int i=0;i<9;i++){
		scanf("%d",&a);
		paixutree(T,a);
	}
	printf("请输入要删除的数字:\n");
	scanf("%d",&a);
	Delete(T,a);
	printf("先序排列为:\n");
	PreOrder(T);
	printf("\n");
	printf("中序排列为:\n");
	InOrder(T);
	printf("\n");
	printf("后序排列为:\n");
	PostOrder(T);
	printf("\n");
	printf("高度为:\n");
	printf("%d\n",Height(T));
	printf("结点数为:\n");
	printf("%d\n",Count(T));	
}

2.假设二叉树结点的数据为字符，即

struct TreeNode {


char Data;

struct TreeNode * Left;

struct TreeNode * Right;

};

如果对该二叉树遍历打印，并且以#代表空树，那么可以得到一个字符串，例如下面的二叉树：（注：设二叉树的结点数据不能为字符#）



先序遍历结果为：ABC##DE##F###

编写程序，输入一个类似于上面先序遍历结果的字符串，根据此字符串建立二叉树。（算法可参考教材126页）验证该二叉树是否正确。

#include<stdio.h>
#include<stdlib.h>
struct TreeNode { 
    char Data;
    struct TreeNode * Left;
    struct TreeNode * Right;
};
int sn=0;
struct TreeNode* creatT(char x){
	struct TreeNode* T;
	if(x=='#')
	return T=NULL;
	else{
	T=(TreeNode*)malloc(sizeof(struct TreeNode));
	T->Data=x;
	T->Left=NULL;
	T->Right=NULL;
	return T;}
}

struct TreeNode* creattree(){
char x;
scanf("%c",&x);
struct TreeNode *T;

if(x=='#')
T=NULL;

else{T=creatT(x);	 
	T->Left=creattree();
	T->Right=creattree();
}
	return T;
}

void PreOrder(struct TreeNode *T) {
    if (T != NULL) {
        printf("%c ", T->Data); /* 假设数据为字符 */
        PreOrder(T->Left);
        PreOrder(T->Right);
    }
    
}
int main(){
	struct TreeNode* T;
T=creattree();
	PreOrder(T);
}