数据结构二叉树与二叉搜索树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 - 1return 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;}elsereturn FindMin(T->left);
}/*----查找最大值----*/
position FindMax(SearchTree T){if(T==NULL){return NULL;}else if(T->right==NULL){return T;}elsereturn 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);}
}