1. 二叉树利用栈的非递归先序遍历
【题目】试利用栈及其基本操作写出二叉树T的非递归的先序遍历算法。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef BiTree SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
//遍历根，并返回最左下根
BiTNode *GoFarGen(BiTree T,Stack &s,void (*visit)(TElemType)){
if(NULL == T) return NULL;
while(T->lchild !=NULL ){
visit(T->data);
Push(s,T);
T=T->lchild;
}
visit(T->data);
return T;
}
void PreOrder(BiTree T, void (*visit)(TElemType))
/* 使用栈，非递归先序遍历二叉树T， */
/* 对每个结点的元素域data调用函数visit */
{
Stack s; InitStack(s);
BiTree p;
p= GoFarGen(T,s,visit);
while(p!=NULL){
if(p->rchild!=NULL)
p= GoFarGen(p->rchild,s,visit);
else if(StackEmpty(s)!=TRUE) Pop(s,p);
else p=NULL;
}
}
2. 二叉树利用栈的非递归后序遍历
【题目】试利用栈及其基本操作写出二叉树T的非递归的后序遍历算法(提示：为分辨后序遍历时两次进栈的不同返回点，
需在指针进栈时同时将一个标志进栈）。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef struct {
struct BiTNode *ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
void PostOrder(BiTree T, void (*visit)(TElemType))
/* 使用栈，非递归后序遍历二叉树T， */
/* 对每个结点的元素域data调用函数visit */
{
if(T == NULL) return;
Stack s; InitStack(s);
int fistIn=0,left=1,right=2;
SElemType now;
now.ptr=T;
now.tag=fistIn;
Push(s,now);
while(!StackEmpty(s)){
Pop(s,now);
if(now.tag==fistIn){
//如果当前是第一次进栈,先置为从左栈返回.
now.tag=left;
Push(s,now);
if(now.ptr->lchild){
now.ptr=now.ptr->lchild;
now.tag=fistIn;
Push(s,now);
}
}else if(now.tag==left){
//如果当前是从左栈返回的,先置为从右栈返回.
now.tag=right;
Push(s,now);
if(now.ptr->rchild){
now.ptr=now.ptr->rchild;
now.tag=fistIn;
Push(s,now);
}
}else{
//如果当前是从右栈返回的,则打印当前节点
visit(now.ptr->data);
}
}
}
3. 找二叉树最近的共同祖先
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
bool FindParents(BiTNode *root, TElemType p, BiTNode **stack, int &length)
{
if(root)
{
if(root->data == p)
{
return true;
}
else
{
if(FindParents(root->lchild, p, stack, length))
{
stack[length++] = root;
return true;
}
else if(FindParents(root->rchild, p, stack, length))
{
stack[length++] = root;
return true;
}
else
return false;
}
}
return false;
}
BiTree CommAncestor(BiTree T, TElemType a, TElemType b)
/* 求二叉树T中结点a和b的最近共同祖先 */
{
if(T->data == a || T->data == b || a == b)
return NULL;
#define MaxSize 20
BiTNode *sa[MaxSize], *sb[MaxSize];
int lengthA, lengthB;
lengthA = lengthB = 0;
if(!FindParents(T, a, sa, lengthA))
return NULL;
sa[lengthA++] = NULL;
if(!FindParents(T, b, sb, lengthB))
return NULL;
sb[lengthB++] = NULL;
int longer, shorter;
BiTNode **longerSt, **shorterSt;
if(lengthA >= lengthB)
{
longer = lengthA;
shorter = lengthB;
longerSt = sa;
shorterSt = sb;
}
else
{
longer = lengthB;
shorter = lengthA;
longerSt = sb;
shorterSt = sa;
}
int diff = longer - shorter;
int index;
for(index = shorter - 1; index >= 0; --index)
if(longerSt[index + diff] != shorterSt[index])
break;
++index;
return shorterSt[index];
}
找二叉排序树最近的共同祖先
/* 求二叉排序树T中结点a和b的最近共同祖先 */
BiTree CommAncestor(BiTree T, TElemType a, TElemType b)
{
if(T==NULL) return NULL;
if((T->data>=a && T->data<b)||(T->data>=b && T->data<a)) return T;
if(T->data>a && T->data>b) return CommAncestor(T->lchild,a,b);
if(T->data<a && T->data<b) return CommAncestor(T->rchild,a,b);
}
4. 判断二叉树是否是完全二叉树
满二叉树就是一颗深度为k且有2^k-1个结点的二叉树(就是除了根结点和叶子结点之外,其他的结点均有左右孩子)
深度为k且含n个结点的二叉树,如果其每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应,则称为完全二叉树
【题目】编写算法判别给定二叉树是否为完全二叉树。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);
Status CompleteBiTree(BiTree T)
/* 判别二叉树T是否为完全二叉树 */
{
if(T==NULL) return TRUE;
Queue q;
BiTree h;//head dequeue
InitQueue(q);
EnQueue(q,T);
Status isC=TRUE;//isCompleteBiTree
bool isL=false;//isLast
while(!QueueEmpty(q)){
DeQueue(q,h);
if(!isL){
if(h->lchild&&h->rchild){ //h->lchild!=NULL && h->rchild=NULL
EnQueue(q,h->lchild);
EnQueue(q,h->rchild);
}else if(h->lchild){
isL=true;
EnQueue(q,h->lchild);
}else if(h->rchild){
isL=true;
isC=FALSE;
break;
}else{
isL=true;
}
}else{
if(h->lchild||h->rchild){
isC=FALSE;
break;
}
}
}
return isC;
}
网友评论