二叉排序树中结点的结构体定义如下: ypedef struct node DataType data; struct node *left child struct node *right Child BiTreenode;
二叉排序树中结点的结构体定义如下： typedef struct node { DataType data; struct node *leftChild; struct node *rightChild; } BiTreeNode;
下图所示就是一棵二叉排序树 410 394 35 190 476 760 146 6 800
381 12 410 9 40 394 540 35 190 146 476 760 445 600 800 下图所示就是一棵二叉排序树
三、二叉排享树的查找算法 int Search(BiTreeNode *root, DataType item) BiTreeNode“p; if(root ! NULL) p= root while(p!= NULL) if(p->data key== item. key) return 1; if(item. key> p->data key)p=p->rightChild else p= p->leftchild; return 0
二、二叉排序树的查找算法 int Search(BiTreeNode *root, DataType item) { BiTreeNode *p; if(root != NULL) { p = root; while(p != NULL) { if(p->data.key == item.key) return 1; if(item.key > p->data.key) p = p->rightChild; else p = p->leftChild; } } return 0; }
、插入算法 插入操作要求首先查找数据元素是否在二叉排序树中存在 若存在则返回;若不存在,插入查找失败时结点的左指针或右 指针上。所插新结点一定在叶结点上 插入算法设计如下:
三、插入算法 插入操作要求首先查找数据元素是否在二叉排序树中存在， 若存在则返回；若不存在，插入查找失败时结点的左指针或右 指针上。所插新结点一定在叶结点上。 插入算法设计如下:
int Insert(BiTreeNode ** root, DataType item) BiTreeNode* current, parent- NUEL, p; current= *root while(current!= NULL) if(current->data key== item. key)return 0; parent= current if(current->data key< item. key current= current->rightChild; Ise current= current->left child /生成新结点* p=(BiTreeNode )malloc(sizeof(Bitreenode)) p->data= item; p->leftChild= NUll; p->rightChild-= null; if(parent-=NULL)*root=p; else if(item. key parent->data key) parent->left Child=p else parent->right Child= p return 1
int Insert(BiTreeNode **root, DataType item) { BiTreeNode *current, *parent = NULL, *p; current = *root; while(current!= NULL) { if(current->data.key== item.key) return 0; parent = current; if(current->data.key< item.key) current = current->rightChild; else current = current->leftChild; } /*生成新结点*/ p = (BiTreeNode *)malloc(sizeof(BiTreeNode)); p->data = item; p->leftChild = NULL; p->rightChild = NULL; if(parent == NULL) *root = p; else if(item.key < parent->data.key) parent->leftChild = p; else parent->rightChild = p; return 1; }