BST二叉查找树
<ol>二叉查找树的创建以及初始化
二叉查找树节点插入<ul>
二叉查找树：左lchild=NULL; Root->rchild=NULL; return Root;}//创建新的结点，并对新结点举行初始化（数据域 + 指针域）BSTNode_t * BSTree_NewNode(BSTNode_t *Root,DataType_t data){ //为新节点申请堆内存空间 BSTNode_t *New=(BSTNode_t*)calloc(1,sizeof(BSTNode_t)); if(Null==New) { perror("calloc for New memory is Failed!!! "); exit(-1); } //对新节点初始化 New->data=data; New->lchild=NULL; New->rchild=NULL; return New; }//向BST二叉树中插入新节点 规则：根节点的左子树的键值都是比根节点小的，根节点的右子树的键值都是比根节点大的bool BSTree_InsertNode(BSTNode_t *Root,DataType_t destval){ //为了避免根节点地址丢失，所以需要对地址举行备份 BSTnode_t *Proot = Root; //1.为新节点申请内存空间 New=BSTree_NewNode(Root,destval); if (NULL == New) { printf("Create NewNode Error\n"); return false; } //2.判断根节点是否存在,根节点不存在，新插入的节点作为根节点 if(Root==NULL) { Root=New; } else// { while(Proot)//根节点存在，如果新节点的值比根的值大，就在右子树找，反则就在左子树找 { if(Proot->data==destval)//如果和根节点的值相等，插入失败 { printf("Can Not Insert\n"); return false; } else { if(Proot->data>destval) { if(Proot->lchild==NULL) { Proot->lchild=New; break; } Proot=Proot->lchild; } else { if(Proot->rchild==NULL) { Proot->rchild=New; break; } Proot=Proot->rchild; } } } } return true;}//BST二叉树节点的数量int BSTree_NodeNum(BSTNode_t *Root){ int n1,n2;//n1为左子树节点数量，n2为右子树节点数量 //1.判断树是否为空，如果为空返回0 if(Root==NULL) { return 0; } n1=BSTree_NodeNum(Root->lchild); n2=BSTree_NodeNum(Root->rchild); return n1+n2+1;}//叶子节点数量int BSTree_LeafNodeNum(BSTNode_t *Root){ int n1,n2;记录左右叶子节点数量 //终止条件 if(Root=NULL) { return 0; } elseif(Root->lchild=NULL&&Root->rchild) { return 1; } else { n1=BSTree_LeafNodeNum(Root->lchild); n2=BSTree_LeafNodeNum(Root->rchild); } return n1+n2;}//树的深度int BSTree_GetDepth(Root){ int n1,n2;//定义左右子树的高度 //1.定义左右子树的结束条件 if(Root=NULL) { //空树，返回0 return 0; } elseif(Root->lchild==NULL&&Root->rchild->NULL) { //只有根节点返回1 return 1; } else { n1=BSTree_GetDepth(Root->lchild); n2=BSTree_GetDepth(Root->rchild); } return (n1>n2?n1:n2)+1;}//先序遍历 根左右bool BSTree_PreOrder(BSTNode_t Root){ //使用递归函数，写好终止条件 if(NULL=Root) { return false; } //输出根节点 printf("keyval=%d\n",Root->data); //输出左子树 BSTree_PreOrder(Root->lchild); //输出右子树 BSTree_PreOrder(Root->rchild);}//中序遍历 左根右bool BSTree_InOrder(BSTNode_t Root){ //使用递归函数，写好终止条件 if(NULL=Root) { return false; } //输出左子树 BSTree_PreOrder(Root->lchild); //输出根节点 printf("keyval=%d\n",Root->data); //输出右子树 BSTree_PreOrder(Root->rchild);}//后序遍历 左右根bool BSTree_PostOrder(BSTNode_t Root){ //使用递归函数，写好终止条件 if(NULL=Root) { return false; } //输出左子树 BSTree_PreOrder(Root->lchild); //输出右子树 BSTree_PreOrder(Root->rchild); //输出根节点 printf("keyval=%d\n",Root->data); }int main(){ return 0;}[/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
