二叉树基本运算算法实现

核心代码

完整代码

示例

核心代码

//插入结点
node* insert(node *root,ElemType value){if(root==NULL){return createNode(value);//如果树为空，创建新节点}if(value<root->data){//比结点小的放在左子树，大的放在右子树root->lchild=insert(root->lchild,value);}else if(value>root->data){root->rchild=insert(root->rchild,value);}return root;
}//查找节点
node* search(node *root,ElemType x){node *p;if(root==NULL){return NULL;}else if(root->data==x){return root;}else{p=search(root->lchild,x);if(p!=NULL){return p;}else{return search(root->rchild,x);}}
}//找左孩子结点
node* Lchild(node *root){return root->lchild;
}//找右孩子结点
node* Rchild(node *root){return root->rchild;
}//求二叉树的高度
int High(node *root){int lchildh,rchildh;if(root==NULL){return(0);   //空树的高度为0}else{lchildh=High(root->lchild);   //求左子树的高度rchildh=High(root->rchild);   //求右子树的高度return (lchildh>rchildh)?(lchildh+1):(rchildh+1);}
}
//先序遍历
void PreOrder(node *root){if(root!=NULL){printf("%d ",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}
}//中序遍历
void InOrder(node *root){if(root!=NULL){InOrder(root->lchild);printf("%d ",root->data);InOrder(root->rchild);}
}//后序遍历
void PostOrder(node *root){if(root!=NULL){PostOrder(root->lchild);PostOrder(root->rchild);printf("%d ",root->data);}
}//销毁二叉树
void Destroy(node *root){if(root!=NULL){Destroy(root->lchild);Destroy(root->rchild);free(root);}
}

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;//定义二叉树结点
typedef struct node
{ElemType data;           //数据元素struct node *lchild;     //指向左孩子struct node *rchild;     //指向右孩子
}node;//创建新结点
node* createNode(ElemType value){node *newNode=(node *)malloc(sizeof(node));newNode->data=value;newNode->lchild=NULL;newNode->rchild=NULL;return newNode;
}//插入结点
node* insert(node *root,ElemType value){if(root==NULL){return createNode(value);//如果树为空，创建新节点}if(value<root->data){//比结点小的放在左子树，大的放在右子树root->lchild=insert(root->lchild,value);}else if(value>root->data){root->rchild=insert(root->rchild,value);}return root;
}//查找节点
node* search(node *root,ElemType x){node *p;if(root==NULL){return NULL;}else if(root->data==x){return root;}else{p=search(root->lchild,x);if(p!=NULL){return p;}else{return search(root->rchild,x);}}
}//找左孩子结点
node* Lchild(node *root){return root->lchild;
}//找右孩子结点
node* Rchild(node *root){return root->rchild;
}//求二叉树的高度
int High(node *root){int lchildh,rchildh;if(root==NULL){return(0);   //空树的高度为0}else{lchildh=High(root->lchild);   //求左子树的高度rchildh=High(root->rchild);   //求右子树的高度return (lchildh>rchildh)?(lchildh+1):(rchildh+1);}
}
//先序遍历
void PreOrder(node *root){if(root!=NULL){printf("%d ",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}
}//中序遍历
void InOrder(node *root){if(root!=NULL){InOrder(root->lchild);printf("%d ",root->data);InOrder(root->rchild);}
}//后序遍历
void PostOrder(node *root){if(root!=NULL){PostOrder(root->lchild);PostOrder(root->rchild);printf("%d ",root->data);}
}//销毁二叉树
void Destroy(node *root){if(root!=NULL){Destroy(root->lchild);Destroy(root->rchild);free(root);}
}
int main(){node *root=NULL;//插入结点root=insert(root,6);insert(root,3);insert(root,4);insert(root,5);insert(root,8);insert(root,7);//查找节点int value=4;node *foundnode=search(root,value);if(foundnode){printf("找到结点：%d\n",foundnode->data);}else{printf("未找到结点：%d\n",value);}//求二叉树的高度int height=High(root);printf("二叉树的高度：%d\n",height);//遍历二叉树//先序遍历printf("先序遍历：");PreOrder(root);printf("\n");//中序遍历printf("中序遍历：");InOrder(root);printf("\n");//后序遍历printf("后序遍历：");PostOrder(root);printf("\n");//销毁二叉树Destroy(root);return 0;}