织梦手机网站怎么做,征婚网站上拉业务做恒指期货,网站单页制作教程,网站搭建服务合同二叉搜索树#xff1a;
树不是线性的#xff0c;是层级结构。基本单位是节点#xff0c;每个节点最多2个子节点。有序。每个节点#xff0c;其左子节点都比它小#xff0c;其右子节点都比它大。每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。可以是空树。…二叉搜索树
树不是线性的是层级结构。基本单位是节点每个节点最多2个子节点。有序。每个节点其左子节点都比它小其右子节点都比它大。每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。可以是空树。 添加元素从根节点开始比对数值。若比它小往左子树比对若比它大往右子树比对直到找到为空则为新元素的位置。
删除元素
若删除的节点为叶子节点即无子节点则直接删除。若删除的节点只有左子节点则左子节点替代删除节点。若删除的节点只有右子节点则右子节点替代删除节点。若删除的节点既有左子节点又有右子节点则找到直接前驱即删除节点的左子树中的最大值即删除节点的左子节点的最右节点直接前驱的值替代删除节点的值删除直接前驱节点。 遍历元素可使用递归
前序遍历顺序根节点、左子节点、右子节点。中序遍历顺序左子节点、根节点、右子节点。后序遍历顺序左子节点、右子节点、根节点。 查找元素从根节点开始比对数值。若比它小往左子树查找若比它大往右子树查找直到找到该元素则返回1true若没有则返回0false。 C语言实现使用链表实现 创建结构体数据类型记录二叉搜索树的根节点和数据个数
typedef struct Link
{LinkNode *root; // 根节点int length; // 统计有多少数据
} LinkBST; // 别名
创建二叉搜索树并初始化
LinkBST bst;
bst.root NULL; // 根节点初始化为NULL
bst.length 0; // 数据个数初始化为0
创建节点结构体数据类型并创建具体节点实例的函数
// 节点结构体数据类型
typedef struct Node
{int value; // 数据类型为整型struct Node *left; // 左子节点struct Node *right; // 右子节点
}LinkNode; // 别名
// 函数创建节点
LinkNode *createNode(int data)
{LinkNode *node (LinkNode *)malloc(sizeof(LinkNode)); // 分配节点内存空间if(node NULL){perror(Memory allocation failed);exit(-1);}node-value data; // 数据node-left NULL; // 左子节点初始化为NULLnode-right NULL; // 右子节点初始化为NULLreturn node;
}
添加元素
void add(LinkBST *bst, int data) // add element
{// 函数往二叉搜索树中添加元素 LinkNode *addNode(LinkNode *node, int data){if(node NULL){LinkNode *newnode createNode(data);node newnode;bst-length; // 每添加一个元素length1return node;}if(data node-value) node-left addNode(node-left, data);else if(data node-value) node-right addNode(node-right, data);return node;}// 从根节点开始比对root指针始终指向二叉搜索树的根节点bst-root addNode(bst-root, data);
}
删除元素
void delete(LinkBST *bst, int data) // delete element
{// 函数删除节点 LinkNode *del(LinkNode *node){ // 若只有右子节点则右子节点替代删除节点if(node-left NULL){bst-length--; // 每删除一个元素length-1return node-right;}// 若只有左子节点则左子节点替代删除节点else if(node-right NULL){bst-length--; // 每删除一个元素length-1return node-left;}// 左右子节点都有则直接前驱(左子节点的最右节点)替代删除节点并删除直接前驱else if(node-left node-right){LinkNode *tmp node, *cur node-left;while(cur-right){tmp cur;cur cur-right;}node-value cur-value;if(tmp ! node) tmp-right cur-left;else tmp-left cur-left;bst-length--; // 每删除一个元素length-1return node;}}// 函数找到将要删除的节点LinkNode *delNode(LinkNode *node, int data){if(node NULL) return node;if(data node-value) node del(node);else if(data node-value) node-left delNode(node-left, data);else if(data node-value) node-right delNode(node-right, data);return node;} // 从根节点开始比对。root指针始终指向二叉搜索树的根节点bst-root delNode(bst-root, data);
}
遍历元素使用递归
// 前序遍历根左右
void pretravel(LinkNode *node)
{if(node NULL) return ;printf(%d , node-value);pretravel(node-left);pretravel(node-right);
}
// 中序遍历左根右
void midtravel(LinkNode *node)
{if(node NULL) return ;midtravel(node-left);printf(%d , node-value);midtravel(node-right);
}
// 后序遍历左右根
void posttravel(LinkNode *node)
{if(node NULL) return ;posttravel(node-left);posttravel(node-right);printf(%d , node-value);
}
查找元素
找到元素返回1(true)没找到返回0(false)。
int find(LinkNode *node, int data)
{if(node NULL) return 0;if(data node-value) return 1;if(data node-value) find(node-left, data);else if(data node-value) find(node-right, data);
} 完整代码bst.c
#include stdio.h
#include stdlib.h
#include stdbool.h/* structure */
typedef struct Node // linkedlist node
{int value; // value type is integerstruct Node *left; // left child nodestruct Node *right; // right child node
}LinkNode;typedef struct Link // binary search tree
{LinkNode *root; // root node of the treeint length; // the number of the tree
} LinkBST;/* function prototype */
void add(LinkBST *, int); // add element to the tree
void delete(LinkBST *, int); // delete element from the tree
void pretravel(LinkNode *); // show element one by one,(root,left,right)
void midtravel(LinkNode *); // show element one by one,(left,root,right)
void posttravel(LinkNode *); // show element one by one,(left,right,root)
int find(LinkNode *, int); // if find data,return 1(true),or return 0(false)/* main function */
int main(void)
{// create binary search tree and initializationLinkBST bst;bst.root NULL;bst.length 0;printf(isempty(1:true, 0:false): %d, length is %d\n, bst.rootNULL, bst.length);add(bst, 15);add(bst, 8);add(bst, 23);add(bst, 10);add(bst, 12);add(bst, 19);add(bst, 6);printf(isempty(1:true, 0:false): %d, length is %d\n, bst.rootNULL, bst.length);printf(midtravel: );midtravel(bst.root);printf(\n);printf(pretravel: );pretravel(bst.root);printf(\n);printf(posttravel: );posttravel(bst.root);printf(\n);printf(find 10 (1:true, 0:false): %d\n, find(bst.root, 10));printf(find 9 (1:true, 0:false): %d\n, find(bst.root, 9));delete(bst, 23);delete(bst, 15);delete(bst, 6);printf(isempty(1:true, 0:false): %d, length is %d\n, bst.rootNULL, bst.length);printf(midtravel: );midtravel(bst.root);printf(\n);printf(pretravel: );pretravel(bst.root);printf(\n);printf(posttravel: );posttravel(bst.root);printf(\n);return 0;
}/* subfunction */
LinkNode *createNode(int data) // create a node
{LinkNode *node (LinkNode *)malloc(sizeof(LinkNode));if(node NULL){perror(Memory allocation failed);exit(-1);}node-value data;node-left NULL;node-right NULL;return node;
}void add(LinkBST *bst, int data) // add element
{// subfunction(recursion): add element to the binary search tree LinkNode *addNode(LinkNode *node, int data){if(node NULL){LinkNode *newnode createNode(data);node newnode;bst-length;return node;}if(data node-value) node-left addNode(node-left, data);else if(data node-value) node-right addNode(node-right, data);return node;}// root node receive the resultbst-root addNode(bst-root, data);
}void delete(LinkBST *bst, int data) // delete element
{// subfunction(recursion): delete element from the binary search tree LinkNode *del(LinkNode *node){if(node-left NULL){bst-length--;return node-right;}else if(node-right NULL){bst-length--;return node-left;}else if(node-left node-right){LinkNode *tmp node, *cur node-left;while(cur-right){tmp cur;cur cur-right;}node-value cur-value;if(tmp ! node) tmp-right cur-left;else tmp-left cur-left;bst-length--;return node;}}// subfunction: find delete node,return nodeLinkNode *delNode(LinkNode *node, int data){if(node NULL) return node;if(data node-value) node del(node);else if(data node-value) node-left delNode(node-left, data);else if(data node-value) node-right delNode(node-right, data);return node;} // root node receive the resultbst-root delNode(bst-root, data);
}void pretravel(LinkNode *node) // show element one by one,(root,left,right)
{if(node NULL) return ;printf(%d , node-value);pretravel(node-left);pretravel(node-right);
}void midtravel(LinkNode *node) // show element one by one,(left,root,right)
{if(node NULL) return ;midtravel(node-left);printf(%d , node-value);midtravel(node-right);
}void posttravel(LinkNode *node) // show element one by one,(left,right,root)
{if(node NULL) return ;posttravel(node-left);posttravel(node-right);printf(%d , node-value);
}int find(LinkNode *node, int data) // if find data,return 1(true),or return 0(false)
{if(node NULL) return 0;if(data node-value) return 1;if(data node-value) find(node-left, data);else if(data node-value) find(node-right, data);
} 编译链接 gcc -o bst bst.c 执行可执行文件 ./bst
