二叉排序树c语言实现
1. 用c语言实现二叉排序树排序，并按递减顺序打印各个数据
#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据域
struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *&p,KeyType k)
{
if (p==NULL) //原树为空, 新插入的记录为根结点
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) //树中存在相同关键字的结点,返回0
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k); //插入到*p的左子树中
else
return InsertBST(p->rchild,k); //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}
void DispInDescrease(BSTNode *bt){ //按从小到大输出查找树中的内容，对该树中序遍历即可
if(bt){
DispInDescrease(bt->lchild);
printf("%d\t",bt->key);
DispInDescrease(bt->rchild);
}
}
void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
DispInDescrease(bt);
}
//已上机验证成功
2. 二叉排序树的C语言实现
两处编译错误 已修改
见代码中注释([flczzhang]->XXX)
#include<stdio.h>
#include<stdlib.h>
typedefintKeyType;
typedefstructnode
{
KeyTypekey;
structnode*lchild,*rchild;
}BSTNode;
typedefBSTNode*BSTree;
//二叉排序树插入
//若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回
voidInsertBST(BSTree*TPtr,KeyTypekey)
{
BSTNode*f,*p;
p=*TPtr; //p的初值指向根结点
while(p) //查找插入位置
{
if(p->key==key) //树中已有key，无须插入
{
return;
}
f=p; //f保存当前查找的结点
//若key<p->key，则在左子树中查找，否则在右子树中查找
p=(key<p->key)?p->lchild:p->rchild;
}
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=key;
p->lchild=p->rchild=NULL; //生成新结点
if(*TPtr==NULL) //原树为空
{
*TPtr=p; //新插入的结点为新的根
}
else//原树非空时将新结点p作为f的左孩子或右孩子插入
{
if(key<f->key)
{
f->lchild=p;
}
else
{
f->rchild=p;
}
}//[flczzhang]->missa}
}
//创建二叉排序树
//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTreeCreateBST(void)
{
BSTreeT=NULL;
KeyTypekey;
scanf("%d",&key);
while(key) //假设key=0是输人结束标志
{
InsertBST(&T,key); //将key插入二叉排序树T
scanf("%d",&key); //读人下一关键字
}
returnT;
}
//查找二叉排序树T中是否存在指定的key
//指针f指向T的双亲,f初始值为NULL
//若查找成功返回1，指针p指向该数据元素结点，否则返回0，p指向查找过程中的最后一个结点
intSearchBST(BSTreeT,intkey,BSTreef,BSTree*p)
{
if(!T)
{
*p=f;
return0;
}
elseif(T->key==key)
{
*p=T;
return1;
}
elseif(T->key>key)
{
returnSearchBST(T->lchild,key,T,p);
}
else
{
returnSearchBST(T->rchild,key,T,p);
}
}
//访问节点数据
voidvisit(KeyTypec,intlevel)
{
printf("%d在第%d层 ",c,level);
}
//前序遍历树节点
voidPreorderTraverse(BSTreeT,intlevel)
{
if(T)
{
visit(T->key,level);
PreorderTraverse(T->lchild,level+1);
PreorderTraverse(T->rchild,level+1);
}
}
intmain()
{
intlevel=1;
BSTreeT;
T=CreateBST();//[flczzhang]->(missinge)
PreorderTraverse(T,level);
return0;
}
3. 急求二叉排序树的实现 用c语言写出代码
程序按你的要求改写，去掉了不少功能，大大简化，但总体功能依旧强大。
先要选择0，创建一棵树，然后程序提示你要输入的数组数字的个数，比如要输入10个数字，输入10，然后再分别输入各个数字。要注意看程序提示。
一个完整的c程序如下,程序在win-tc和Dev-c++下都调试通过。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node {
int value;
struct node* left;
struct node* right;
};
typedef struct node NODE;
typedef struct node* PNODE;
PNODE creat( PNODE tree,PNODE r,int value)
{
if(!r)
{
r = (PNODE)malloc(sizeof(NODE));
if(!r)
{
printf("内存分配失败！");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->value = value;
if(!tree)
return r;
if(value<tree->value)
tree->left = r;
else
tree->right = r;
return r;
}
if(value < r->value)
creat(r,r->left,value);
else
creat(r,r->right,value);
return tree;
}
void new_node (PNODE* n, int value) {
*n = (PNODE)malloc (sizeof(NODE));
if (*n != NULL) {
(*n)->value = value;
(*n)->left = NULL;
(*n)->right = NULL;
}
}
void free_node (PNODE* n) {
if ((*n) != NULL) {
free (*n);
*n = NULL;
}
}
/* 查找结点 */
PNODE find_node (PNODE n, int value) {
if (n == NULL) {
return NULL;
} else if (n->value == value) {
return n;
} else if (value <= n->value) {
return find_node (n->left, value);
} else {
return find_node (n->right, value);
}
}
/* 插入结点 */
void insert_node (PNODE* n, int value) {
if (*n == NULL) {
new_node (n, value);
} else if (value == (*n)->value) {
return;
} else if (value < (*n)->value) {
insert_node (&((*n)->left), value);
} else {
insert_node (&((*n)->right), value);
}
}
/* 删除结点 */
void deletenode (PNODE *n) {
PNODE tmp = NULL;
if (n == NULL) return;
if ((*n)->right == NULL) {
tmp = *n;
*n = (*n)->left;
free_node (n);
} else if ((*n)->left == NULL) {
tmp = *n;
*n = (*n)->right;
free_node (n);
} else {
for (tmp = (*n)->right; tmp->left != NULL; tmp = tmp->left);
tmp->left = (*n)->left;
tmp = (*n);
*n = (*n)->right;
free_node (&tmp);
}
}
void delete_node (PNODE *n, int value) {
PNODE node;
if (n == NULL) return;
node = find_node (*n, value);
if ((*n)->value == value) {
deletenode (n);
} else if (value < (*n)->value) {
delete_node (&((*n)->left), value);
} else {
delete_node(&((*n)->right), value);
}
}
void pre_order_traversal(PNODE n) /* 前序遍历 */
{
if (n != NULL) {
printf ("%i ", n->value);
pre_order_traversal (n->left);
pre_order_traversal( n->right);
}
}
void in_order_traversal (PNODE n) /* 中序遍历 */
{
if (n != NULL) {
in_order_traversal (n->left);
printf ("%i ", n->value);
in_order_traversal ( n->right);
}
}
void post_order_traversal (PNODE n) /* 后序遍历 */
{
if (n != NULL) {
post_order_traversal (n->left);
post_order_traversal (n->right);
printf ("%i ", n->value);
}
}
int get_num_nodes (PNODE n) /* 计算树的节点数 */
{int left = 0;
int right = 0;
if (n == NULL) {
return 0;
}
if (n->left != NULL) {
left = get_num_nodes (n->left);
}
if (n->right != NULL) {
right = get_num_nodes (n->right);
}
return (left + 1 + right);
}
int main() {
char buf[50];
int i,n,option,s[80];
PNODE tree = NULL;/*树的第一个结点*/
PNODE node = NULL;
while (1) {
printf ("--------------------------\n");
printf ("Options are:\n\n");
printf (" 0 Creat tree\n");
printf (" 1 Insert node\n");
printf (" 2 Delete node\n");
printf (" 3 Find node\n");
printf (" 4 Pre order traversal\n"); /* 前序遍历 */
printf (" 5 In order traversal\n"); /* 中序遍历 */
printf (" 6 Post order traversal\n");/* 后序遍历 */
printf (" 7 Node Count\n");
printf (" 8 Exit\n\n");
printf ("--------------------------\n");
printf ("Select an option: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("--------------------------\n");
if (option < 0 || option > 12) {
fprintf (stderr, "Invalid option");
continue;
}
switch (option) {
case 0:
printf ("Enter number of elements of array: ");
scanf("%d",&n);
printf ("Enter %d elements of array:\n",n);
for(i=0;i<n;i++)
{ scanf("%d",&s[i]);
tree = creat(tree,tree,s[i]);
}
fflush(stdin);
break;
case 1:
printf ("Enter number to insert: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
insert_node (&tree, option);
break;
case 2:
printf ("Enter number to delete: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
delete_node (&tree, option);
break;
case 3:
printf ("Enter number to find: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
node = find_node (tree, option);
if (node != NULL) {
printf ("Found node\n\n");
} else {
printf ("There is no node which you input!\n\n");
}
break;
case 4:
printf ("Pre order traversal: ");
pre_order_traversal (tree);
printf ("\n\n");
break;
case 5:
printf ("In order traversal: ");
in_order_traversal (tree);
printf ("\n\n");
break;
case 6:
printf ("Post order traversal: ");
post_order_traversal (tree);
printf ("\n\n");
break;
case 7:
printf ("Node Count is %i\n\n", get_num_nodes (tree));
break;
case 8:
exit (0);
}
}
return 0;
}
4. c语言 二叉排序树 100分
class TREE
{
private:
NODE *root; //树根
ofstream outfile; //输出流
public:
TREE(){root=0;} //构造函数，用来初始化树根
~TREE(){} //析构函数
void build_tree(NODE *&root,long data,float number); //建立二叉树
int search_tree(NODE *root,float number); //搜索二叉树
void print(NODE *root,ofstream outfile); //输出
void destory(NODE *root); //删除root
};
//建立二叉树
void TREE::build_tree(NODE *&root,long data,float number)
{
NODE *temp,*backtemp; //定义当前指针和拖后指针
if(root==0) //定义树根
{
root=new NODE;
root->lchild=root->rchild=0;
root->data=data;
root->number=number;
}
else
{
temp=root;
while(temp!=0)
{
backtemp=temp;
if(number>(temp->number))
temp=temp->lchild;
else temp=temp->rchild;
}
if(number>(backtemp->number))
{
NODE *newdode = new NODE;
newdode->lchild=newdode->rchild=0;
newdode->data=data;
newdode->number=number;
backtemp->lchild=newdode;
}
else
{
NODE *newdode = new NODE;
newdode->lchild=newdode->rchild=0;
newdode->data=data;
newdode->number=number;
backtemp->rchild=newdode;
}
}
}
//输出二叉树，按照中序遍历
void TREE::print(NODE *root,ofstream outfile)
{
if(root!=0)
{
print(root->lchild,outfile);
outfile << (root->data) << " ";
outfile << (root->number) << endl;
print(root->rchild,outfile);
}
}
void TREE::destory(NODE *root)
5. 二叉排序树的实现（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,datatype x);
BiTree InsertL(BiTree bt,datatype x,BiTree parent);
BiTree InsertR(BiTree bt,datatype x,BiTree parent);
BiTree DeleteL(BiTree bt,BiTree parent);
BiTree DeleteR(BiTree bt,BiTree parent);
void PreOrder(BiTree bt);
void InOrder(BiTree bt);
void PostOrder(BiTree bt);
void LevelOrder(BiTree bt);
BiTree Find(BiTree parent,datatype a);
void NRPreOrder(BiTree bt);
void NRInOrder(BiTree bt);
void NRPostOrder(BiTree bt);void main()
{
int n,m=1;
BiTree t; /*clrscr();*/
while(m)
{
menu();
scanf("%d",&n);
switch(n)
{
case 1:{/*初始化*/
int flag;
datatype x;
printf("please input head point x:\n");
scanf("%d",&x);
flag=Initiate(&t,x);
if(flag==1)
printf("\nInitiate success!");
else
printf("\nInitiate fail!");
break;
}
case 2:{/*建树*/
break;
}
case 3:{/*插入结点x作为a的左孩子*/
datatype a,x;/*x作为a的左孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertL(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 4:{/*插入结点x作为a的右孩子*/
datatype a,x;/*x作为a的右孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertR(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 5:{/*删除结点a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteL(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 6:{/*删除结点a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteR(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 7:{/*递归先序遍历*/
PreOrder(t);
break;
}
case 8:{/*递归中序遍历*/
InOrder(t);
break;
}
case 9:{/*递归后序遍历*/
PostOrder(t);
break;
}
case 10:{/*层次遍历*/
LevelOrder(t);
break;
}
case 11:{/*先序遍历的非递归实现*/
NRPreOrder(t);
break;
}
case 12:{/*中序遍历的非递归实现*/
NRInOrder(t);
break;
}
case 13:{/*后序遍历的非递归实现*/
NRPostOrder(t);
break;
}
case 0:m=0;
}
}
}
void menu()
{
/*clrscr();*/
printf("\n");
printf("\t\t1.initiate\n\n");
printf("\t\t2.create thread\n\n");
printf("\t\t3.insert Left\n\n");
printf("\t\t4.insert Right\n\n");
printf("\t\t5.delete Left\n\n");
printf("\t\t6.delete Right\n\n");
printf("\t\t7.preorder\n\n");
printf("\t\t8.inorder\n\n");
printf("\t\t9.postorder\n\n");
printf("\t\t10.levelorder\n\n");
printf("\t\t11.nrpreorder\n\n");
printf("\t\t12.nrinorder\n\n");
printf("\t\t13.nrpostorder\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
int Initiate(BiTree *bt,datatype x)
{
if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0;
(*bt)->data=x;
(*bt)->lchild=NULL;
(*bt)->rchild=NULL;
return 1;
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return bt;
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL)
parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return bt;
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->lchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
free(p);
return bt;
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->rchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
free(p);
return bt;
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return;
printf("%5d",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
void InOrder(BiTree bt)
{
if(bt==NULL)
return;
InOrder(bt->lchild);
printf("%5d",bt->data);
InOrder(bt->rchild);
}
void PostOrder(BiTree bt)
{
if(bt==NULL)
return;
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%5d",bt->data);
}
void LevelOrder(BiTree bt)
{
BiTree Queue[MAXNODE];
int front,rear;
if(bt==NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = bt;
while(front!=rear)
{
front++;
printf("%5d",Queue[front]->data);
if(Queue[front]->lchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->lchild;
}
if(Queue[front]->rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}//end while
}
BiTree Find(BiTree parent,datatype a)
{
BiTree p;
if(parent==NULL)
p=NULL;
else if(parent->data==a)
p=parent;
else
{
p=Find(parent->lchild,a);
if(p==NULL)
p=Find(parent->rchild,a);
}
return p;
}
void NRPreOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
printf("%5d",p->data);
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
p=p->rchild;
} /* end while p && top */
}
void NRInOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
printf("%5d",p->data);
p=p->rchild;
} /* end while p && top */
}
void NRPostOrder(BiTree bt)
{
stacktype stack[MAXNODE];
BiTree p;
int top,sign;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
if(p!=NULL) /*结点第一次入栈*/
{
top++;
stack[top].link=p;
stack[top].flag=1; /*标记第一次入栈*/
p=p->lchild;
} /* end if */
else
{
p=stack[top].link;
sign=stack[top].flag;
top--;
if(sign==1) /*结点第二次入栈*/
{
top++;
stack[top].link=p;
stack[top].flag=2; /*标记第二次入栈*/
p=p->rchild;
} /* end if */
else
{
printf("%5d",p->data);
p=NULL;
} /* end if-else */
} /* end if-else */
} /* end while */
}
6. 二叉排序树的实现(c语言)
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct btnode
{char data; /*suppose the data field's type is char*/
struct btnode *lchild; /*left pointer field */
struct btnode *rchild; /*right pointer field */
}NODE;
void main()
{ NODE *root,*q,n;
NODE *create(NODE *p);
void preorder(NODE *root);
void inorder(NODE *root);
void postorder(NODE *root);
int t;
q=&n;
root=create(q);
printf("At the first,we create a tree\n");
printf("Please input nodes of tree\n");
if (root==NULL) printf("It's an empty tree!\n");
else
{
printf("\n1.The preordetraverse \n");
printf(" 2.The inordertraverse \n");
printf(" 3.The postordertraverse \n");
printf(" Please choose a kind of order\n");
scanf("%d",&t);
switch (t)
{
case 1: preorder(root); break;
case 2: inorder(root); break;
case 3:postorder(root); break;
default: printf(" The error!");
}
}
}
NODE * create(NODE *p) /*create the structure of binary tree */
{ char ch;
NODE *t;
scanf("%c",&ch);
if(ch==' ') p=NULL;
else
{p->data=ch;
t=(NODE *)malloc(sizeof(NODE));
p->lchild=create(t);
t=(NODE*)malloc(sizeof(NODE));
p->rchild=create(t);
}
return p;
}
void preorder(NODE *root) /*travel the tree using preorder */
{ if (root!=NULL)
{ printf( " %c", root->data);
preorder(root->lchild);
preorder(root->rchild);
}
return;
}
void inorder (NODE *root) /*travel the tree using inorder */
{ if (root!=NULL)
{ inorder(root->lchild);
printf(" %c ", root->data);
inorder(root->rchild);
}
return;
}
void postorder(NODE *root) /*travel the tree using postorder */
{ if (root!=NULL)
{ postorder (root->lchild);
postorder (root->rchild);
printf(" %c ", root->data);
}
return;
}
7. 二叉排序树的实现（用C语言实现）,急急急！
typedef struct
{
int v;
NODE *left = NULL;
NODE *right = NULL;
NODE *Lead = NULL;
} NODE;
NODE* InsertValue(NODE *n, value)
{
NODE *p = (NODE *)malloc(sizeof(NODE));
p->left= NULL;
p->right = NULL;
p->v = value;
return InsertNode(n, p);
}
NODE* InsertNode(NODE *pNode, NODE *pNew)
{
if (pNew == NULL)
{
return pNode;
}
// 如果没有节点，那么返回当前新增的节点自己。
if (pNode == NULL)
{
return pNew;
}
//左小右等大的原则。
if (value < v)
{
if (pNode->left == NULL)
{
pNode->left = pNew;
pNew->pLead = pNode;
}
else
{
InsertValue(pNode->left, pNew);
}
}
else
{
if (pNode->right == NULL)
{
pNode->right = pNew;
pNew->pLead = pNode;
}
else
{
InsertValue(pNode->right, pNew);
}
}
return pNode;
}
displayTree(Node *pNode)
{
printf("%d ", pNode->v);
if (pNode->left != NULL)
{
displayTree(pNode->left);
}
if (pNode->right != NULL)
{
displayTree(pNode->right);
}
}
// 如果找到，返回找到的个数，没有返回0
int findAndRemove(Node *pNode, int value)
{
int r = 0;
if (pNode == null)
return 0;
if (pNode -> v == value) // 找到了，就要删除本节点。左右重新从上级节点插树
{
NODE *pOldRight = pNode->right;
Node *pOldLeft = pNode->left;
if (pNode->left != NULL)
{
// 左结点有树，把左结点复制到本结点。把右结点增加到本结点。
pNode->v = pNode->left->v;
pNode->left = pNode->left->left;
pNode->right = pNode->left->right;
free(pOldLeft);
}
else if (pNode->right != NULL)
{
// 只有右结点有树，直接把右结点复制上来
pNode->v = pNode->right->v;
pNode->left = pNode->right->left;
pNode->right = pNode->right->right;
free(pNode->right)
}
r = 1;
}
// 递归
r = r + findAndRemove(pNode->left, value);
r = r + findAndRemove(pNode->right, value);
return r;
}
main()
{
// 以回车('\n')为输入结束标志,输入数列L, 这个过程不是重点内容，又怪麻烦的，我就省了。你自己处理吧。
int a[] = {3,5,2,45,43,7,468,23,32,2,32,65,87,23,543,76};
int i;
NODE *pRoot = NULL;
// 建立树
for(i = 1; i < 16; i ++)
{
pRoot = InsertValue(NULL, ar[i]);
}
// 打印树
displayTree(&root);
// 查询删除
i = findAndRemove(pRoot, 23);
if (i == 0)
{...}
else
{
displayTree(&root);
}
}
8. 二叉树C语言算法,急!!!!
清华大学
严蔚敏
的<数据结构里>都有完整的代码,解释的也很清楚
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
typedef
struct
tree
{
struct
tree
*left;
int
date;
struct
tree
*right;
}treenode,*b_tree;
///////插入节点/////////////////////
b_tree
insert(b_tree
root,int
node)
{
b_tree
newnode;
b_tree
currentnode;
b_tree
parentnode;
newnode=(b_tree)malloc(sizeof(treenode));
newnode->date=node;
newnode->right=NULL;
newnode->left=NULL;
if(root==NULL)
return
newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode->date>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->date>node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return
root;
}
//////建立树///////////////////
b_tree
creat(int
*date,int
len)
{
b_tree
root=NULL;
int
i;
for(i=0;i<len;i++)
root=insert(root,date[i]);
return
root;
}
//////中序打印////////////////
void
print1(b_tree
root)
{if(root!=NULL)
{
print1(root->left);
printf("%d->",root->date);
print1(root->right);
}
}
//////后序打印////////////////
void
print2(b_tree
root)
{if(root!=NULL)
{
print2(root->left);
print2(root->right);
printf("%d->",root->date);
}
}
//////前序打印////////////////
void
print3(b_tree
root)
{if(root!=NULL)
{
printf("%d->",root->date);
print3(root->left);
print3(root->right);
}
}
//////////在二叉树中查找给定关键字
////////////
b_tree
lookfor(b_tree
root,int
e)
{
b_tree
p1,p2;
if(root!=NULL)
{
if(root->date==e)
return
root;
else
p1=lookfor(root->left,e);
p2=lookfor(root->right,e);
if(p1!=NULL)
return
p1;
else
if(p2!=NULL)
return
p2;
else
return
NULL;
}
else
return
NULL;
}
///////测试函数//////////////////
void
main()
{
b_tree
root=NULL;
int
i,index;
int
value;
int
nodelist[20];
cout<<"输入树的节点，输入0结束\n";
index=0;
cin>>value;
while(value!=0)
{
nodelist[index]=value;
index=index+1;
cin>>value;
}
root=creat(nodelist,index);
printf("\n中序打印\n");
print1(root);
printf("\n后序打印\n");
print2(root);
printf("\n前序打印\n");
print3(root);
printf("\n查找的词：\n");
int
a;
scanf("%d",&a);
b_tree
p3=lookfor(root,a);
if(p3!=NULL)
printf("%d\n",p3->date);
else
printf("没你要找的词");
}
9. 二叉排序树创建遍历C语言实现
我给你一个更加完整的吧。
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct BTree{
DataType data;
struct BTree *Tleft;
struct BTree *Tright;
}*BTree;
BTree CreateTree(); //建树
BTree insert(BTree root, DataType data);//插入节点
void InBTree(BTree root); //中序遍历
void PreBTree(BTree root); //先序遍历
void PostBTree(BTree root);//后序遍历
BTree findPostion(BTree root, int deleteNode, int *flags);//寻找合适的插入点
BTree delNode(BTree root, BTree parent, int flags); //删除树节点
int main(){
BTree root = NULL;
int flags = 0;
int deleteNode = 0;
BTree parent = NULL;//所删除节点的父节点
char choiceAgain = 'Y';
root = CreateTree();
printf("\n中序遍历: ");
InBTree(root);
printf("\n前序遍历: ");
PreBTree(root);
printf("\n后序遍历: ");
PostBTree(root);
printf("\n");
do{
printf("需要删掉的节点: ");
scanf("%d", &deleteNode);
parent = findPostion(root, deleteNode, &flags);
root = delNode(root, parent, flags);
printf("删除后的结果: ");
printf("\n中序遍历: ");
InBTree(root);
printf("\n前序遍历: ");
PreBTree(root);
printf("\n后序遍历: ");
PostBTree(root);
choiceAgain = 'N';
printf("\nDelete Again(Y) or N?: ");
getchar();
scanf("%c", &choiceAgain);
}while(choiceAgain == 'Y' || choiceAgain == 'y');
printf("\nDone!\n");
return 0;
}
BTree CreateTree(){
BTree root = NULL;
DataType temp = 0;
printf("请输入节点,以0结尾:\n");
scanf("%d", &temp);
while(temp != 0){
root = insert(root, temp);
scanf("%d", &temp);
}
return root;
}
BTree insert(BTree root, DataType data){
BTree ptr = root;
BTree tempNode;
BTree newNode = (BTree)malloc(sizeof(struct BTree));
newNode->data = data ;
newNode->Tleft = NULL;
newNode->Tright = NULL;
if(ptr == NULL){
return newNode;
}else{
while(ptr != NULL){
tempNode = ptr;
if(ptr->data >= data){
ptr = ptr->Tleft;
}else{
ptr = ptr->Tright;
}
}
if(tempNode->data >= data){
tempNode->Tleft = newNode;
}else{
tempNode->Tright = newNode;
}
}
return root;
}
BTree findPostion(BTree root, int deleteNode, int *flags){
BTree parentNode = root;
BTree temp = root;
*flags = 0;
while(temp != NULL){
if(temp->data == deleteNode){
return parentNode;
}else{
parentNode = temp;
if(temp->data > deleteNode){
temp = temp->Tleft;
*flags = -1;
}else{
temp = temp->Tright;
*flags = 1;
}
}
}
return NULL;
}
BTree delNode(BTree root, BTree parent, int flags){
BTree deleteNode = NULL;
if(parent == NULL){
printf("未找到删除的节点!\n");
return root;
}
switch(flags){
case -1:
deleteNode = parent->Tleft;
break;
case 0:
deleteNode = parent;
break;
case 1:
deleteNode = parent->Tright;
break;
default:
printf("ERROR!\n");
exit(1);
}
if(deleteNode->Tleft == NULL && deleteNode->Tright == NULL){
if(parent->Tleft == deleteNode){
parent->Tleft = NULL;
}else if(parent->Tright == deleteNode){
parent->Tright = NULL;
}else{
parent = NULL;
}
free(deleteNode);
}else if(deleteNode->Tleft == NULL && deleteNode->Tright != NULL){
if(deleteNode->data == root->data){
root = deleteNode->Tright;
}else{
if(parent->Tleft->data == deleteNode->data){
parent->Tleft = deleteNode->Tright;
}else{
parent->Tright = deleteNode->Tright;
}
}
free(deleteNode);
}else if(deleteNode->Tleft != NULL && deleteNode->Tright == NULL){
if(deleteNode->data == root->data){
root = deleteNode->Tleft;
}else{
if(parent->Tleft->data == deleteNode->data){
parent->Tleft = deleteNode->Tleft;
}else{
parent->Tright = deleteNode->Tleft;
}
}
free(deleteNode);
}else{
BTree temp = deleteNode->Tleft;
BTree tempParent = deleteNode;
while(temp->Tright != NULL){
tempParent = temp;
temp = temp->Tright;
}
deleteNode->data = temp->data;
if(tempParent->Tleft == temp){
tempParent->Tleft = temp->Tleft;
}else{
tempParent->Tright = temp->Tleft;
}
printf("temp = %d\n", temp->data);
free(temp);
}
return root;
}
void InBTree(BTree root){
if(root != NULL){
InBTree(root->Tleft);
printf("%d ", root->data);
InBTree(root->Tright);
}
}
void PreBTree(BTree root){
if(root != NULL){
printf("%d ", root->data);
PreBTree(root->Tleft);
PreBTree(root->Tright);
}
}
void PostBTree(BTree root){
if(root != NULL){
PostBTree(root->Tleft);
PostBTree(root->Tright);
printf("%d ", root->data);
}
}
10. 二叉树怎样用C语言实现
以下代码可实现二叉树的递归创建与中序遍历，但在输入时需在输入完有效数据后再连续输入多个负数才可以。
#include <stdio.h>
#include <stdlib.h>
typedef struct BitNode
{
int data;
struct BitNode *lchile,*rchild;
}*BiTree;
BiTree CreateBiTree(BiTree &T)
{
int d;
scanf("%d",&d);
if (d<0)
return NULL;
else
{
if (!(T=(BiTree)malloc(sizeof(BiTree))))
{
exit(1);
}
T->data=d;//先根序创建二叉树
printf("%d ",T->data);
T->lchile=CreateBiTree(T->lchile);//创建左子树
T->rchild=CreateBiTree(T->rchild);//创建右子树
return T;
}
}
void InOrderView(BiTree &T)//中序遍历二叉树
{
if(T)
{
InOrderView(T->lchile);
printf("%d ",T->data);
InOrderView(T->rchild);
}
}
void main()
{
BiTree T;
T=CreateBiTree(T);//递归创建二叉树
InOrderView(T);
}