二叉排序樹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);
}