首页 > 其他 > 详细

二叉树及先序,中序,后序遍历

时间:2016-03-27 01:23:36      阅读:417      评论:0      收藏:0      [点我收藏+]

一、什么是二叉树

每个结点至多只有两棵子树,并且,二叉树有左右之分不能随便颠倒位置。

二、二叉树的存储形式

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!