CC++ ＜树＞二叉搜索树

二叉搜索树

树的结构定义1)插入数据2)遍历数据3)删除数据4)查找数据正在更新中。。。

树的结构定义

头文件代码页 tree.h

#ifndef __TREE_H__ #define __TREE_H__ #define MAX_NODE 1024 #define isLess(a, b) (a<b) #define isGreater(a, b) (a>b) #define isEqual(a, b) (a==b) typedef int ElemType; typedef struct _Bnode{ ElemType data; //元素类型 struct _Bnode* lchild, * rchild;//指向左右孩子节点 }Bnode, Btree; #endif

1)插入数据

bool InsertBtree(Btree** root, Bnode* node) { Bnode* tmp = NULL; Bnode* parent = NULL; bool isOK = false; if (!node) { return false; } else { node->lchild = NULL; node->rchild = NULL; } if ((*root)) { tmp = (*root); } else { *root = node; return true; } while (tmp != NULL) { parent = tmp; if (tmp && isLess(node->data, tmp->data)) { tmp = tmp->lchild; isOK = true; } if (tmp && isGreater(node->data, tmp->data)) { tmp = tmp->rchild; isOK = false; } } if (isOK) { parent->lchild = node; } else { parent->rchild = node; } return true; }

2)遍历数据

void PreOrderRec(Btree* root) { if (root == NULL) { return; } printf("【 %d 】", root->data); PreOrderRec(root->lchild); PreOrderRec(root->rchild); }

3)删除数据

删除节点存在左右子节点，则取左子树上最大节点或右子树上最小节点替换删除节点

Btree* DeleteNode(Btree* root, int key, Bnode*& deletedNode) { if (root == NULL)return NULL; if (root->data > key) { root->lchild = DeleteNode(root->lchild, key, deletedNode); return root; } if (root->data < key) { root->rchild = DeleteNode(root->rchild, key, deletedNode); return root; } deletedNode = root; //删除节点不存在左右子节点，即为叶子节点，直接删除 if (root->lchild == NULL && root->rchild == NULL)return NULL; //删除节点存在右子节点，直接用右子节点取代删除节点 if (root->lchild == NULL && root->rchild != NULL)return root->rchild; //删除节点存在左子节点，直接用左子节点取代删除节点 if (root->lchild != NULL && root->rchild == NULL)return root->lchild; 删除节点存在左右子节点，直接用左子节点最大值取代删除节点 int val = findMax(root->lchild); root->data = val; root->lchild = DeleteNode(root->lchild, val, deletedNode); return root; } printf("删除节点15\n"); Bnode* deletedNode = NULL; root = DeleteNode(root, 15, deletedNode); printf("二叉搜索树删除节点15,%s\n", deletedNode ? "删除成功" : "删除不成功，节点不存在"); if (deletedNode) delete deletedNode;

4)查找数据

正在更新中。。。