二叉排序树的实现、插入并中序遍历
#include
#include
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int InitBiTree(BiTree *T)
{
*T = NULL;
return 1;
}
int SearchBST(BiTree T,TElemType e,BiTree f,BiTree *p)
{
if(!T)
{
*p = f;
return 0;
}
else
{
if(e==T->data)
{
*p = T;
return 1;
}
else
if(edata)
return SearchBST(T->lchild,e,T,p);
else
return SearchBST(T->rchild,e,T,p);
}
}
int InsertBST(BiTree *T,TElemType e)
{
BiTree s,p;
if(!SearchBST(*T,e,NULL,&p))
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = e;
s->lchild = s->rchild = NULL;
if(!p)
*T = s;
else
{
if(edata)
p->lchild = s;
else
p->rchild = s;
}
return 1;
}
else
return 0;
}
int Visit(TElemType e)
{
printf("%d ",e);
return 1;
}
int InOrderTraverse(BiTree T,int (* Visit)(TElemType e))//递归中序遍历二叉树
{
if(T)
{
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return 1;
return 0;
}
else
return 1;
}
int CreateBST(BiTree *T)
{
TElemType e;
scanf("%d",&e);
while(e!=-1)
{
InsertBST(T,e);
scanf("%d",&e);
}
return 1;
}
void main()
{
BiTree T;
InitBiTree(&T);
CreateBST(&T);
InOrderTraverse(T,Visit);
}
/*设计一个读入一串整数构成一棵二叉排序树的程序，并对其中序遍历*/#include "stdafx.h"#include "stdio.h"#include "malloc.h"typedef struct node{ struct node* lchild,* rchild; int data;}BitNode,*BiTree;void newT(BiTree &T){ T=(BiTree)malloc(sizeof(BitNode)); T->lchild=NULL; T->rchild=NULL;}void InsertTree(BiTree &T,int a){ if(T==NULL) { T=(BiTree)malloc(sizeof(BitNode)); T->lchild=NULL; T->rchild=NULL; T->data=a;} else { if(adata) {InsertTree(T->lchild,a);} else if(a>T->data) {InsertTree(T->rchild,a);} }}void BuildTree(BiTree &T){ int a; printf("请输入待排序数据,以0为结束标志：
"); scanf("%d",&a); while(a!=0) { InsertTree(T,a); // fflush(stdin); scanf("%d",&a); }}void midTras(BiTree T){ if(T) { midTras(T->lchild); printf("%d ",T->data); midTras(T->rchild); }}
/*
*二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。
*其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
*①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
*②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
*③左、右子树本身又各是一棵二叉排序树。
*上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。
*/
#ifndef _BINARYSORTTREEADT_H
#define _BINARYSORTTREEADT_H
/* 声明结点的值的类型 */
typedef int KeyType;
/* 声明结点类型 */
typedef struct CBSTNode
{
KeyType m_ktKey;
struct CBSTNode * m_pCBSTNLeft;
struct CBSTNode * m_pCBSTNRight;
}CBSTNode, *PCBSTNode, *CBSTree;
/* 向二叉排序树中加入一个结点 */
extern int InsertNode(CBSTree *, KeyType);
/* 通过值查找并删除一个结点 */
extern int DelNode(CBSTree *, KeyType);
/* 通过值查找结点并返回结点的指针（设为常量指针） */
extern const CBSTNode * SearchNode(CBSTree *, KeyType);
/* 中序遍历二叉排序树的结点 */
extern void PrintAllNodeMid(CBSTree);
/* 后序方式释放结点 */
extern void FreeBSTree(CBSTree);
#endif
BinarySortTreeADT.cpp
#include "BinarySortTreeADT.h"
#include <stdlib.h>
#include <stdio.h>
/* 向二叉排序树中加入一个结点 */
int InsertNode(CBSTree * tree, KeyType key)
{
PCBSTNode p = NULL, parent = NULL;
PCBSTNode pNewNode = (PCBSTNode)malloc(sizeof(CBSTNode));
if (NULL == pNewNode)
{
return -1;
}
/* 新建结点赋值，特别是左右子结点指针要赋值为NULL */
pNewNode->m_ktKey = key;
pNewNode->m_pCBSTNLeft = NULL;
pNewNode->m_pCBSTNRight = NULL;
/* 二叉排序树是空树 */
if (NULL == *tree)
{
*tree = pNewNode;
return 0;
}
else
{
p = *tree;
/* 寻找插入位置 */
while (NULL != p)
{
/* key值已在二叉排序树中 */
if (p->m_ktKey == key)
{
return 0;
}
else
{
parent = p;
p = (p->m_ktKey < key) ? p->m_pCBSTNRight : p->m_pCBSTNLeft;
}
}
if (parent->m_ktKey < key)
{
parent->m_pCBSTNRight = pNewNode;
}
else
{
parent->m_pCBSTNLeft = pNewNode;
}
return 0;
}
}
/* 通过值查找并删除一个结点 */
int DelNode(CBSTree * tree, KeyType key)
{
PCBSTNode p = NULL, q = NULL, parent = NULL, child = NULL;
p = *tree;
/* parent为NULL表示根结点的父亲为NULL */
while (NULL != p)
{
if (p->m_ktKey == key)
{
break;
}
else
{ parent = p;
p = (p->m_ktKey < key) ? p->m_pCBSTNRight : p->m_pCBSTNLeft;
}
}
/* p为NULL时， 表示没有找到结点值为key的结点 */
if (NULL == p)
{
return 0;
}
/* p, q现在都是保存了待删结点指针 */
q = p;
/* 待删结点有两个儿子结点，进行一下转化 */
if (NULL != p->m_pCBSTNLeft && NULL != p->m_pCBSTNRight)
{
parent = p;
p = p->m_pCBSTNRight;
while (NULL != p->m_pCBSTNLeft)
{
parent = p;
p = p->m_pCBSTNLeft;
}
/* p中保存了待删结点右子树中最左下的结点指针， parent中就保存了该结点父亲指针 */
child = p->m_pCBSTNRight;
}
/* parent保存待删结点的父亲结点指针， child保存了待删结点的儿子结点
指针（待删结点至多只有一个儿子， 有两个会转化为0个或1个右结点）*/
/* 待删结点是根结点 */
if (NULL == parent)
{
*tree = child;
}
else
{
/*待删结点是父亲结点的左儿子*/
if (parent->m_pCBSTNLeft == p)
{
parent->m_pCBSTNLeft = child;
}
else
{
parent->m_pCBSTNRight = child;
}
/*待删结点有两个儿子结点， 转化后需要交换两个结点值 */
if (p != q)
{
q->m_ktKey = p->m_ktKey;
}
}
free(p);
return 0;
}
/* 通过值查找结点并返回结点的指针（设为常量指针） */
const CBSTNode * SearchNode(CBSTree * tree, KeyType key)
{
PCBSTNode p = *tree;
while (NULL != p)
{
if (p->m_ktKey == key)
{
break;
}
else
{
p = (p->m_ktKey < key) ? p->m_pCBSTNRight : p->m_pCBSTNLeft;
}
}
return p;
}
/* 中序遍历二叉排序树的结点 */
void PrintAllNodeMid(CBSTree tree)
{
if (NULL != tree)
{
PrintAllNodeMid(tree->m_pCBSTNLeft);
printf("%d is accessed.\n", tree->m_ktKey);
PrintAllNodeMid(tree->m_pCBSTNRight);
}
}
/* 后序方式释放结点 */
void FreeBSTree(CBSTree tree)
{
if (NULL != tree)
{
FreeBSTree(tree->m_pCBSTNLeft);
FreeBSTree(tree->m_pCBSTNRight);
printf("%d is free.\n", tree->m_ktKey);
free(tree);
}
}
数据结构课程设计:二叉排序树的实现
答：/*以下是用c++ 实现的二叉排序树的源代码*/ include<iostream.h> typedef struct TreeNode { int key;struct TreeNode *left;struct TreeNode *right;}treeNode;class BiSortTree { public:BiSortTree(void);void desplayTree(void);//显示这个树 void insertTree(int key);//在树中插入一个值...
从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序...
答：void inorder(BiTNode *BT){//中序遍历二叉树 if(BT!=NULL){ inorder(BT->lchild );printf("%c ",BT->data);inorder(BT->rchild );} } void DeleteBtree(BiTNode *BT){//删除二叉树的所有的节点 if(BT!=NULL){ DeleteBtree(BT->lchild );DeleteBtree(BT->rchild );free(BT);} }...
二叉排序树的前序、中序、后序遍历分别是什么?
答：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回。因此，A是根结点，B是A的左子树，F是A的右子树。E是B的左子树，C是B的右子树，...
二叉排序树的插入算法
答：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。 //在二叉排序树中插入查找关键字keyvoidInsertBST(t，key){ if(t==NULL) { t=newBiTree; t...
生成二叉排序树(c++写代码, 数据结构)
答：// 二叉排序树 class BSTree { friend BSTree *CreateBSTree(const ElemType *a);public:BSTree() : root(NULL) {} ~BSTree() { CleanUp(); } void CleanUp(BSTNode *r);void InOrder(BSTNode *r) const; // 中序遍历 void PostOrder(BSTNode *r) const; // 后序遍历 void CleanUp...
BST二叉排序树
答：二叉排序树的存储结构通常使用如下的结构定义：typedef int KeyType;typedef struct { KeyType key; InfoType otherinfo; struct node *lchild, *rchild, *parent;} BSTNode;typedef BSTNode *BSTree;基础操作包括： 中序遍历所有元素 查找指定元素 查找最小和最大元素 求后继节点 插入...
数据结构,二叉排序树
答：二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：若左子树不空，则左子树上所有节点的值均小于它的根节点的值 若右子树不空，则右字数上...
二叉排序树的建立、插入、删除和查找 给出一组关键值,建立相应的二叉排 ...
答：BSTNode *bt=NULL; //初始时bt为空树 int i=0;while (i<n){ InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中 i++;} return bt; //返回建立的二叉排序树的根指针 } void main(){ BSTNode *bt,*p,*f;int n=9;KeyType a[]={1,12,5,8,3,10,7,13,9};...
二叉排序树可以中序遍历吗?
答：对的，中序遍历一棵二叉排序树的结点就可得到排好序的结点序列这句话是没有错误的，因为二叉排序树的根节点大于左子树，小于右子树，然后使用中序遍历算法，中序遍历算法先遍历左子树，然后是根节点，然后是右子树。根据遍历的特性，所有的先遍历的结点，一定是小于后边遍历的结点，所以说中序遍历一棵...
二叉排序树的实现(c语言)
答：/*二叉树的基本运算与实现*/ include <stdio.h> include <malloc.h> define MAXNODE 256 typedef int datatype;typedef struct BiTNode { datatype data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;typedef struct { BiTree link;int flag;}stacktype;void menu();int Initiate(BiTree *bt...
