数据结构二叉树与二叉搜索树c实现代码

二叉树

#include <stdio.h>
#include <stdlib.h>




#define MAXNODE 100
typedef int ElementType;



/*----------结构体-------------*/
typedef struct BinNode {
	ElementType Element;
	struct BinNode *lchild, *rchild;
} BinNode, *BinTree;




/*------------先序遍历--------------*/
void PreOrder(BinTree T) {
	if (T) {
		printf("%c", T->Element);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}



/*----------中序遍历---------------*/
void InOrder(BinTree T) {
	if (T) {
		InOrder(T->lchild);
		printf("%c", T->Element);
		InOrder(T->rchild);
	}
}


/*-------------后序遍历---------------*/
void PostOrder(BinTree T) {
	if (T) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		printf("%c", T->Element);
	}
}



/*-----------层级遍历---------------*/
void LevelOrder(BinTree T) {
	if (!T) return;
	
	// 创建队列
	BinTree queue[MAXNODE];  // 树节点不超过MAXNODE个
	int front = 0, rear = 0;
	
	// 根节点入队
	queue[rear++] = T;
	
	// 当队列不为空时循环
	while (front < rear) {
		// 出队并访问
		BinTree current = queue[front++];
		printf("%c", current->Element);
		
		// 左子树入队
		if (current->lchild)
			queue[rear++] = current->lchild;
			
		// 右子树入队
		if (current->rchild)
			queue[rear++] = current->rchild;
	}
}



/*-----------创建新节点---------------*/
BinTree CreateNode(ElementType value) {
    BinTree newNode = (BinTree)malloc(sizeof(BinNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return NULL;
    }
    newNode->Element = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    return newNode;
}

/*-----------创建空树---------------*/
BinTree CreateEmptyTree() {
    return NULL;
}

/*-----------构建二叉树（通过前序遍历输入）---------------*/
BinTree BuildTree() {
    char ch;
    scanf(" %c", &ch);  // 读取一个字符，忽略空白
    
    if (ch == '#') {  // 使用 '#' 表示空节点
        return NULL;
    } else {
        BinTree T = CreateNode(ch);
        printf("输入 %c 的左子树：", ch);
        T->lchild = BuildTree();
        printf("输入 %c 的右子树：", ch);
        T->rchild = BuildTree();
        return T;
    }
}

/*-----------插入节点（这里实现为二叉搜索树的插入）---------------*/
BinTree InsertNode(BinTree T, ElementType value) {
    if (T == NULL) {
        return CreateNode(value);
    }
    
    if (value < T->Element) {
        T->lchild = InsertNode(T->lchild, value);
    } else if (value > T->Element) {
        T->rchild = InsertNode(T->rchild, value);
    }
    // 如果值相等，不插入（假设不允许重复值）
    
    return T;
}

/*-----------查找节点---------------*/
BinTree FindNode(BinTree T, ElementType value) {
    if (T == NULL || T->Element == value) {
        return T;
    }
    
    if (value < T->Element) {
        return FindNode(T->lchild, value);
    } else {
        return FindNode(T->rchild, value);
    }
}

/*-----------获取树高度---------------*/
int GetHeight(BinTree T) {
    if (T == NULL) {
        return 0;
    }
    
    int leftHeight = GetHeight(T->lchild);
    int rightHeight = GetHeight(T->rchild);
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

/*-----------获取节点数量---------------*/
int GetNodeCount(BinTree T) {
    if (T == NULL) {
        return 0;
    }
    
    return GetNodeCount(T->lchild) + GetNodeCount(T->rchild) + 1;
}

/*-----------获取叶子节点数量---------------*/
int GetLeafCount(BinTree T) {
    if (T == NULL) {
        return 0;
    }
    
    if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    }
    
    return GetLeafCount(T->lchild) + GetLeafCount(T->rchild);
}

/*-----------判断是否为空树---------------*/
int IsEmpty(BinTree T) {
    return T == NULL;
}

/*-----------判断是否为完全二叉树---------------*/
int IsComplete(BinTree T) {
    if (T == NULL) {
        return 1; // 空树视为完全二叉树
    }
    
    BinTree queue[MAXNODE];
    int front = 0, rear = 0;
    int flag = 0; // 标记是否遇到了非满节点
    
    queue[rear++] = T;
    
    while (front < rear) {
        BinTree current = queue[front++];
        
        if (current->lchild) {
            if (flag) return 0; // 已经遇到过非满节点，但又发现了新节点
            queue[rear++] = current->lchild;
        } else {
            flag = 1; // 遇到非满节点
        }
        
        if (current->rchild) {
            if (flag) return 0; // 已经遇到过非满节点，但又发现了新节点
            queue[rear++] = current->rchild;
        } else {
            flag = 1; // 遇到非满节点
        }
    }
    
    return 1;
}

/*-----------判断是否为满二叉树---------------*/
int IsFull(BinTree T) {
    if (T == NULL) {
        return 1; // 空树视为满二叉树
    }
    
    int height = GetHeight(T);
    int nodeCount = GetNodeCount(T);
    
    // 满二叉树的节点数 = 2^height - 1
    return nodeCount == (1 << height) - 1;
}

/*-----------销毁树---------------*/
void DestroyTree(BinTree T) {
    if (T == NULL) {
        return;
    }
    
    DestroyTree(T->lchild);
    DestroyTree(T->rchild);
    free(T);
}

/*-----------复制树---------------*/
BinTree CopyTree(BinTree T) {
    if (T == NULL) {
        return NULL;
    }
    
    BinTree newTree = CreateNode(T->Element);
    newTree->lchild = CopyTree(T->lchild);
    newTree->rchild = CopyTree(T->rchild);
    
    return newTree;
}

/*-----------镜像/翻转树---------------*/
void MirrorTree(BinTree T) {
    if (T == NULL) {
        return;
    }
    
    // 交换左右子树
    BinTree temp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = temp;
    
    // 递归镜像左右子树
    MirrorTree(T->lchild);
    MirrorTree(T->rchild);
}

二叉搜索树

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef  int ElementType;


typedef struct TreeNode
{
    ElementType data;
    struct TreeNode *left;
    struct TreeNode *right;
}*SearchTree,*position;



/*-----插入结点-----*/
SearchTree Insert(ElementType x,SearchTree T){
    if(T==NULL){
        T=(SearchTree)malloc((sizeof(struct TreeNode)));
        T->data=x;
        T->left=NULL;
        T->right=NULL;
    }
    else if(x<T->data){
            T->left=Insert(x,T->left);
        }
    else if (x>T->data){
        T->right=Insert(x,T->right);
    }
    return T;
}



/*----创建二叉搜索树-----*/
SearchTree CreatBST(int a[],int n){
    SearchTree T = NULL;
    int i;
    for(i=0;i<n;i++){
        T = Insert(a[i],T);
    }
    return T;
}




/*----清空二叉搜索树----*/
SearchTree MakeEmpty(SearchTree T){
    if(T!=NULL){
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }
    return NULL;
}


/*----查找指定值----*/
position Find(ElementType x,SearchTree T){
    if(T==NULL){
        return NULL;
    }
    if(x<T->data){
        return Find(x,T->left);
    }
    else if(x>T->data){
        return Find(x,T->right);
    }
    else{
        return T;
    }
}

/*----查找最小值----*/
position FindMin(SearchTree T){
    if (T==NULL){
        return NULL;
    }
    else if(T->left==NULL){
        return T;
    }
    else
        return FindMin(T->left);
}



/*----查找最大值----*/
position FindMax(SearchTree T){
    if(T==NULL){
        return NULL;
    }
    else if(T->right==NULL){
        return T;
    }
    else
        return FindMax(T->right);
}

SearchTree Delete(ElementType x,SearchTree T){
    position Tmpcell;
    if(T==NULL){
        printf("Element Not Found!");
    }
    else if(x<T->data){
        T->left=Delete(x,T->left);
    }
    else if(x>T->data){
        T->right=Delete(x,T->right);
    }
    else{
        if(T->left && T->right){
            Tmpcell=FindMin(T->right);
            T->data=Tmpcell->data;
            T->right=Delete(T->data,T->right);
        }
        else{
            Tmpcell=T;
            if(T->left==NULL){
                T=T->right;
            }
            else if (T->right==NULL){
                T=T->left;
            }
        }
        free(Tmpcell);
    }
    return T;
}

/* ----判断树是否为空---- */
int IsEmpty(SearchTree T) {
    return T == NULL;
}

/* ----计算树的高度---- */
int Height(SearchTree T) {
    int leftHeight, rightHeight;
    if (T == NULL) {
        return -1; /* 空树高度为-1 */
    }
    leftHeight = Height(T->left);
    rightHeight = Height(T->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

/* ----计算节点数量---- */
int CountNodes(SearchTree T) {
    if (T == NULL) {
        return 0;
    }
    return CountNodes(T->left) + CountNodes(T->right) + 1;
}

/* ----中序遍历---- */
void InorderTraversal(SearchTree T) {
    if (T != NULL) {
        InorderTraversal(T->left);
        printf("%d ", T->data);
        InorderTraversal(T->right);
    }
}

/* ----前序遍历---- */
void PreorderTraversal(SearchTree T) {
    if (T != NULL) {
        printf("%d ", T->data);
        PreorderTraversal(T->left);
        PreorderTraversal(T->right);
    }
}

/* ----后序遍历---- */
void PostorderTraversal(SearchTree T) {
    if (T != NULL) {
        PostorderTraversal(T->left);
        PostorderTraversal(T->right);
        printf("%d ", T->data);
    }
}

/* ----验证是否为有效的二叉搜索树----*/
int IsBSTUtil(SearchTree T, ElementType min, ElementType max);
int IsBST(SearchTree T) {
    return IsBSTUtil(T, INT_MIN, INT_MAX);
}

/*----辅助函数，检查树是否满足二叉搜索树性质----*/
int IsBSTUtil(SearchTree T, ElementType min, ElementType max) {
    if (T == NULL) {
        return 1;
    }
    
    if (T->data < min || T->data > max) {
        return 0;
    }
    
    return IsBSTUtil(T->left, min, T->data - 1) && 
           IsBSTUtil(T->right, T->data + 1, max);
}

/*----寻找后继节点（中序遍历的下一个节点-----*/
position FindSuccessor(SearchTree T, ElementType x) {
    position current, successor, temp;
    
    current = Find(x, T);
    if (current == NULL) {
        return NULL;
    }
    if (current->right != NULL) {
        return FindMin(current->right);
    }
    successor = NULL;
    temp = T;
    
    while (temp != current) {
        if (current->data < temp->data) {
            successor = temp;
            temp = temp->left;
        } else {
            temp = temp->right;
        }
    }
    
    return successor;
}

/*------寻找前驱节点（中序遍历的上一个节点）--------*/
position FindPredecessor(SearchTree T, ElementType x) {
    position current, predecessor, temp;
    
    current = Find(x, T);
    if (current == NULL) {
        return NULL;
    }
    

    if (current->left != NULL) {
        return FindMax(current->left);
    }

    predecessor = NULL;
    temp = T;
    
    while (temp != current) {
        if (current->data > temp->data) {
            predecessor = temp;
            temp = temp->right;
        } else {
            temp = temp->left;
        }
    }
    
    return predecessor;
}

/* 打印树结构（中序遍历带层级） */
void PrintTreeUtil(SearchTree T, int level);
void PrintTree(SearchTree T) {
    PrintTreeUtil(T, 0);
}

/* 辅助函数，用于缩进式打印树 */
void PrintTreeUtil(SearchTree T, int level) {
    int i;
    if (T != NULL) {
        PrintTreeUtil(T->right, level + 1);
        for (i = 0; i < level; i++) {
            printf("    ");
        }
        printf("%d\n", T->data);
        PrintTreeUtil(T->left, level + 1);
    }
}