一、什么是二叉树
每个结点至多只有两棵子树,并且,二叉树有左右之分不能随便颠倒位置。
二、二叉树的存储形式
1、顺序存储结构
用一组地址连续的存储单元以此自上而下、自左从右的存储二叉树的结点元素。这种结构便于遍历二叉树查找元素,但是会浪费大量内存空间。
2、链式存储结构
每个结点有指向左右子树的指针,本身的数据内容,还可以加上指向双亲的指针。这样相对于顺序存储结构能够节省内存空间。
三、二叉树结构体
typedef struct Node{ int data; Node *lchild; Node *rchild; }Node;
四、先序遍历
1、先访问根节点
2、先序遍历左子树
3、先序遍历右子树
代码(递归):
void BL(tree* T){
printf("%d",T->data); if(T->lchild!=NULL) BL(T->lchild); if(T->rchild!=NULL) BL(T->rchild); }
五、中序遍历
1、中序遍历左子树
2、访问根节点
3、中序遍历右子树
代码(递归):
void BL(tree* T) { if(T->lchild!=NULL) BL(T->lchild);
printf("%d",T->data); if(T->rchild!=NULL) BL(T->rchild); }
六、后序遍历
1、后序遍历左子树
2、后序遍历右子树
3、访问根节点
代码(递归):
void BL(tree* T) { if(T->lchild!=NULL) BL(T->lchild); if(T->rchild!=NULL) BL(T->rchild); printf("%d",T->data); }
七、例子
上图的先序:-+a*b-cd/ef
中序:a+b*c-d-e/f
后序:abcd-*+ef/-
原文:http://www.cnblogs.com/skblog/p/5324547.html