2024年4月4日发(作者：)
树和二叉树
1 按先序遍历的扩展序列建立一棵二叉树的存储结构。
设计思想：先序遍历为：先访问根节点，先序遍历左子数，先序遍历右子数
完整代码见附件。
伪代码为：
bool BITREE::CreateBiTree(BiTree &T)
{ /*先序序列建立二叉树*/
char ch;
scanf("%c",&ch);
if (ch=='*')
T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
return ERROR;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
2 分别实现二叉树先序、中序、后序遍历的递归算法。
设计思想：先序遍历为：访问根节点，先序遍历左子数，先序遍历右子数
中序遍历为：中序遍历左子数，访问根节点，中序遍历右子数
后序遍历为：后序遍历左子数，后序遍历右子数，访问根节点
完整代码见附件。
伪代码为：
Status BITREE::PreOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{ /*先序遍历二叉树的递归算法*/
if (T){
if(Visit(T->data))
if(PreOrderTraverse(T->lchild, Visit))
if(PreOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}
Status BITREE::InOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{ /*中序遍历二叉树的递归算法*/
if(T){
if(InOrderTraverse(T->lchild, Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else return OK;
}
Status BITREE::PostOrderTraverse(BiTree T, Status(*Visit)(TElemType))
{ /*后序遍历二叉树的递归算法*/
if(T){
if(PostOrderTraverse(T->lchild, Visit))
if(PostOrderTraverse(T->rchild, Visit))
if(Visit(T->data))
return OK;
return ERROR;
}
else return OK;
}
3 实现二叉树中序遍历的非递归算法。
完整代码见附件。
伪代码为：
Status BITREE::InOrderTraverse2(BiTree T, Status (*Visit)(TElemType))
{ /*中序遍历二叉树的非递归算法*/
Stack S;
BiTree p;
InitStack(S);
Push(S, T);
while (!StackEmpty(S)){
while(GetTop(S, p) && p)
Push(S, p->lchild);
Pop(S, p);
if (!StackEmpty(S)){
Pop(S, p);
if (!Visit(p->data))
return ERROR;
Push(S, p->rchild);
}
}
return OK;
}
4 假设一颗二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树。
发布评论