Chinaunix首页 | 论坛 | 博客
  • 博客访问: 883555
  • 博文数量: 376
  • 博客积分: 154
  • 博客等级: 入伍新兵
  • 技术积分: 1558
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-13 08:42
文章分类

全部博文(376)

文章存档

2014年(11)

2013年(88)

2012年(260)

2011年(17)

分类: 架构设计与优化

2013-04-25 18:40:10

原文地址:二叉树之前序遍历 作者:scq2099yt

一、结点结构
        在二叉树的链接存储中,通常采用的方法是:每个结点中设置三个域,即值域、左指针域和右指针域,其结点结构如下:

图1 二叉树结点结构
        其中,data表示值域,用于存储放入结点的数据元素,left和right分别表示左指针域和右指针域,用于分别存储左孩子和右孩子结点(即左右子树的根结点)的存储位置(即指针)。
        链接存储的指针类型和结点定义如下:
        typedef struct bnode
        {
            ElemType data;
            struct bnode *left, *right;
        }btree;
        其中,ElemType可以是任意数据类型如int、float或者char等,在算法中,规定其默认为int类型。

二、递归遍历
        前序遍历原理:按照先访问根节点,再访问左子树,最后访问右子树的次序访问二叉树中所有节点,且每个结点仅访问一次。其递归算法如下:
        void preorder(btree *p)
        {
            if (NULL != p)
            {
                printf("%d ", p->data)
                preorder(p->left);
                preorder(p->right);
            }
        }

三、非递归遍历
       void preorder(btree *b)
      {
            btree *stack[MAX_SIZE], *p;
            int top;
            if (NULL != b)
            {
                top = 1;                            // 根结点入栈
                stack[top] = b;                   
                while (top > 0)                   // 栈不为空时循环
                {
                    p = stack[top];                // 退栈并访问该节点
                    top--;
                    printf("%d ", p->data);
                    if (NULL != p->right)        // 右孩子入栈
                    {
                        top++;
                        stack[top] = p->right;
                    }
                    if (NULL != p->left)         // 左孩子入栈           
                    {
                        top++;
                        stack[top] = p->left;
                    }
                }
            }
      }


阅读(495) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~