一、二叉树定义
1.树的术语：
树的结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树
无序树：不考虑子树的顺序
2.由树引出二叉树
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^(i-1)个结点；深度为k的二叉树至多有2^k-1个结点。
二叉树有五种基本形态：
(1)空二叉树；
(2)只有一个根结点的二叉树；
(3)只有左子树；
(4)只有右子树；
(5)完全二叉树
尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。（当有序树只有一个节点时没有左右之分，而二叉树不是）
3.二叉树的遍历
对一棵二叉树的遍历有三种情况：
先(根)序遍历：首先访问根，再先序遍历左子树，最后先序遍历右子树
中(根)序遍历：首先中序遍历左子树，再访问根，最后中序遍历右子树
后(根)序遍历：首先后序遍历左子树，再后序遍历右子树，最后访问根
附上代码：
#include<stdio.h>
#include<stdlib.h>
typedef char TElemType;
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode* LChild,*RChild;
}BiTNode,*BiTree;
Status Visit(TElemType e){
if(e!=' ')
printf("%c ",e);
return OK;
}
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
if(T){
if(Visit(T->data)){
if(PreOrderTraverse(T->LChild,Visit)){
if(PreOrderTraverse(T->RChild,Visit)){
return OK;
}
}
}
return ERROR;
}else{
return OK;
}
}
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
if(T){
if(InOrderTraverse(T->LChild,Visit)){
if(Visit(T->data)){
if(InOrderTraverse(T->RChild,Visit)){
return OK;
}
}
}
return ERROR;
}else{
return OK;
}
}
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
if(T){
if(PostOrderTraverse(T->LChild,Visit)){
if(PostOrderTraverse(T->RChild,Visit)){
if(Visit(T->data)){
return OK;
}
}
}
return ERROR;
}else{
return OK;
}
}
Status CreatTree(BiTree& T){
TElemType ch;
T=(BiTree)malloc(sizeof(BiTNode));
scanf("%c",&ch);getchar();
T->data=ch;
if(ch==' '){
T->LChild=NULL;
T->RChild=NULL;
return OK;
}
printf("输入%c的左孩子:",ch);
CreatTree(T->LChild);
printf("输入%c的右孩子:",ch);
CreatTree(T->RChild);
}
int main(){
BiTree T=NULL;
printf("输入root:");
CreatTree(T);
printf("nPreOrderTraverse:");
PreOrderTraverse(T,Visit);
printf("nInOrderTraverse:");
InOrderTraverse(T,Visit);
printf("nPostOrderTraverse:");
PostOrderTraverse(T,Visit);
}
遍历的树：
运行截图：
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
