一、二叉树
二叉树是一棵树，其中每个节点都不能有多余两个儿子。
二叉树的一个性质是平均二叉树的深度要比N小的多，分析表明，这个平均深度为O(),对于特殊类型的二叉树，即二叉查找树，其深度的平均值O（logN）
二、二叉查找树
对于树中的每个节点X，它的左子树中所有的关键字值小于X的关键字，而它的右子树中所有的关键字值大于X的关键字值。
三、二叉树的遍历
前序遍历（DLR）
前序遍历也叫做先根遍历，可记做根左右。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。
中序遍历（LDR）
中序遍历也叫做中根遍历，可记做左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
后序遍历（LRD）
后序遍历也叫做后根遍历，可记做左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根结点。
注意的是：遍历左右子树时仍然采用后序遍历方法。
层次遍历
按照从上至下，从左至右的顺序遍历二叉树。
#include<stdio.h> #include<stdlib.h> #define N 9 int a[]={3,2,5,8,4,7,6,9,10}; //二叉树的结点类型； typedef struct tree { int data; struct tree *lchild; struct tree *rchild; }BitTree; //在二叉排序树中插入查找关键字可以； void Inserter(BitTree *bt,int key) { BitTree *parent; //表示双亲结点； BitTree *head = bt; BitTree *p=(BitTree *)malloc(sizeof(BitTree)); p->data=key; //保存结点数据； p->lchild=p->rchild=NULL; //左右子树置空； //查找需要添加的父结点，这个父结点是度为0的结点； while(head) { parent=head; if(key<head->data) //若关键字小于结点的数据； head=head->lchild; //在左子树上查找； else //若关键字大于结点的数据； head=head->rchild; //在右子树上查找； } //判断添加到左子树还是右子树； if(key<parent->data) //小于父结点； parent->lchild=p; //添加到左子树； else //大于父结点； parent->rchild=p; //添加到右子树； } //n个数据在数组data[]中； BitTree *Createer(BitTree *bt,int data[],int n) { int i=0; bt=(BitTree *)malloc(sizeof(BitTree)); bt->data=data[0]; bt->lchild=bt->rchild=NULL; for( i=1;i<n;i++) Inserter(bt,data[i]); return bt; } //前序遍历； void PreOrder(BitTree *bt) { if(bt) { printf("%d ",bt->data); PreOrder(bt->lchild); PreOrder(bt->rchild); } } //中序遍历； void InOrder(BitTree *bt) { if(bt) { InOrder(bt->lchild); printf("%d ",bt->data); InOrder(bt->rchild); } } void PostOrder(BitTree *bt){ //后序遍历 if(bt){ PostOrder(bt->lchild); PostOrder(bt->rchild); printf("%d ",bt->data); } } //删除结点； void Deleteer(BitTree *bt,int key) { BitTree *L,*LL; //在删除左右子树都有的结点时使用； BitTree *p=bt; BitTree *parent=bt; int child=0; //0表示左子树，1表示右子树； if(!bt) //如果排序树为空，则退出； return ; while(p) //二叉排序树有效； { if(p->data==key) { if(!p->lchild&&!p->rchild) //叶结点(左右子树都为空)； { if(p==bt) //被删除的结点只有根结点； free(p); else if(child==0) { parent->lchild=NULL; //设置父结点左子树为空； free(p); //释放结点空间； } else //父结点为右子树； { parent->rchild=NULL; //设置父结点右子树为空； free(p); //释放结点空间； } } else if(!p->lchild) //左子树为空，右子树不为空； { if(child==0) //是父结点的左子树； parent->lchild=p->rchild; else //是父结点的右子树； parent->rchild=p->rchild; free(p); //释放被删除的结点； } else if(!p->rchild) //右子树为空，左子树不为空； { if(child==0) //是父结点的左子树； parent->lchild=p->lchild; else //是父结点的右子树； parent->rchild=p->lchild; free(p); //释放被删除的结点； } else { LL=p; //保存左子树的结点； L=p->rchild; //从当前结点的右子树进行查找； if(L->lchild) //左子树不为空； { LL=L; L=L->lchild; //查找左子树； p->data=L->data; //将左子树的数据保存到被删除结点； LL->lchild=L->lchild; //设置父结点的左子树指针为空； for(;L->lchild;L=L->lchild); L->lchild=p->lchild; p->lchild=NULL; } else { p->data=L->data; LL->rchild=L->rchild; } } p=NULL; } else if(key<p->data) //需删除记录的关键字小于结点的数据； { //要删除的结点p是parent的左子树； child=0; //标记在当前结点左子树； parent=p;//保存当前结点作为父结点； p=p->lchild; //查找左子树； } else //需删除记录的关键字大于结点的数据； { //要删除的结点p是parent的右子树； child=1; //标记在当前结点右子树查找； parent=p; //保存当前结点作为父结点； p=p->rchild; //查找右子树； } } } int maxDepth(BitTree* root) { if (root == NULL) { return 0; } else { int maxLeft = maxDepth(root->lchild), maxRight = maxDepth(root->rchild); if (maxLeft > maxRight) { return 1 + maxLeft; } else { return 1 + maxRight; } } } int main(void) { BitTree *bt; //保存二叉排序树根结点； int i=0; int maxdepth=0; printf("数组数据为:\n"); for(i=0;i<N;i++) printf("%d ",a[i]); printf("\n\n"); bt=Createer(bt,a,N); printf("遍历后的二叉排序树为(前序遍历输出):\n"); PreOrder(bt); printf("\n\n"); printf("遍历后的二叉排序树为(中序遍历输出):\n"); InOrder(bt); printf("\n\n"); printf("遍历后的二叉排序树为(后序遍历输出):\n"); PostOrder(bt); printf("\n\n\n"); maxdepth=maxDepth(bt); printf("二叉树的深度 %d\n",maxdepth); printf(" **将数据8插入到二叉树中**\n\n"); printf("插入后的二叉树为(中序遍历输出):\n"); Inserter(bt,8); PreOrder(bt); printf("\n\n\n"); printf(" **将数据5从二叉树中删除**\n\n"); printf("删除后的二叉树为(中序遍历输出):\n"); Deleteer(bt,5); //删除拥有左右子树的结点有问题； PreOrder(bt); printf("\n"); return 0; }
