一、结点结构
在二叉树的链接存储中,通常采用的方法是:每个结点中设置三个域,即值域、左指针域和右指针域,其结点结构如下:
图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;
}
}
}
}
阅读(665) | 评论(0) | 转发(0) |