数据结构第二次习题课

数据结构第二次习题课

二叉树按二叉链表形式存储

1. 建立完全二叉树的算法

typedef struct BTNode{
    int data;
    struct BTNode *lchild,*rchild;
}BTNode,*BiTree;
//采用先序遍历构建二叉树
BiTree CreateTree(){
    int x;
    BiTree *bt;
    scanf("%d",&x);
    if(x==0) bt=NULL;
    else{
        bt=(BiTree)malloc(sizeof(BTNode));
        bt->data=x;
        bt->lchild=CreateTree();
        bt->rchild=CreateTree();
    }
    return bt;
}

2. 写一个判断给定的二叉树是否是完全二叉树的算法

/*
思路：
完全二叉树的结点编号于满二叉树的结点编号一一对应。
采用层序遍历算法，将所有结点加入序列，遇到空结点时，
查看队列中是否还有非空结点，若有则不少二叉树。
*/
int CheckTree(BiTree T){
    if(T=NULL) return 1;
    BiTree q[Max_Size];
    int front=0,rear=0;
    BiTree p=T;
    q[++rear]=p;
    while(front<rear){
        p=q[++front];
        if(q!=NULL){//左右孩子入队
            q[++rear]=p->lchild;
            q[++rear]=p->rchild;
        }else{//空指针则出队，若知道队空都是空指针，就为完全二叉树。
            while(front<rear){
                p=q[++front];
                if(p)return 0;//空指针后又有结点指针，不是完全二叉树。
            }
        }
    }
    return 1;
}

已知先序和中序遍历序列存于两个一维数组，编写算法建立该二叉树的二叉链表

/*
给定二叉树结点的先序和中序序列，可以唯一确定该二叉树，
因为前序序列的第一个元素是根节点，该元素将二叉树的中序序列分成两部分，
左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；
右边（设r个元素）表示右子树，若右边无元素，则右子树为空。
根据前序遍历：“根左右”的顺序，则由第二元素开始的l个结点序列构造左子树，
由前序序列最好r个元素序列与中序序列根右边的r个元素序列构造右子树。
*/
typedef struct BTNode{
    int data;
    struct BTNode *lchild,*rchild;
}BTNode,*BiTree;
BiTree CreateTree(int pre[],int l1,int r1,int in[],int l2,int r2){
    BiTree root=(BiTree)malloc(sizeof(BTNode));
    root->data=pre[l1];
    int i;
    for(i=l2;i<=r2;i++){
        if(in[i]==pre[l1])break;
    }
    int llen=i-l2;//左子树长度;
    int rlen=r2-i;//右子树长度;
    //递归建立左子树
    if(llen==0){
        root->lchild=NULL;
    }else{
        root->lchild=CreateTree(pre,l1+1,l1+llen,in,l2,l2+llen-1);
    }
    //递归建立右子树
    if(rlen==0){
        root->rchild=NULL;
    }else{
        root->rchild=CreateTree(pre,r1-rlen+1,r1,in,r2-rlen+1,r2);
    }
    return root;//返回根节点
}

已知中序和后序遍历序列存于两个一维数组，编写算法建立该二叉树的二叉链表

/*
给定二叉树结点的后序序列和中序序列,可以唯一确定该二叉树。
因为后序序列的第最后一个元素是根结点，该元素将二叉树的中序序列分成两部分，
左边(设l个元素)表示左子树，若左边无元素,则说明左子树为空;右边(设r个元素)是右子树，
若右边无元素,则右子树为空。根据后序遍历中“左子树-右子树-根”的顺序，
则由从第1个元素开始的l个结点序列和中序序列根左边的1个结点序列构造左子树,
由后序序列倒数第二个元素开始的r个结点序列与中序序列根右边的r个元素序列构造右子树。
*/
typedef struct BTNode {
int data;
struct BTNode *lchild, *rchild;
} BTNode, *BiTree;
BiTree CreateTree(int post[],int l1,int r1,int in[],int l2,intr2){
    BiTree root=(BiTree)malloc(sizeof(BTNode));
	root->data=post[r1];
	int i;
    for(i=l2;i<=r2;i++){//在中序序列中查找根节点并将其分成左右子树
        if(in[i]==post[r1]) break;
	}
    int llen=i-l2;//左子树长度
    int rlen=r2-i;//右子树长度
    //递归建立左子树
    if(llen==0){
		root->lchild=NULL;
	}else{
	root->lchild=CreateTree(post,l1,l1+llen-1,in,l2,l2+llen-1);
    }
	//递归建立右子树
	if(rlen==0){
		root->rchild=NULL;
	}else{
	root->rchild=CreateTree(post,l1+llen,r1-1,in,r2-rlen+1,r2);
    }
	return root;//返回根节点
}

以二叉链表形式存储，求该树第k层的结点数

#define MAX_SIZE 105
typedef struct BTNode{
    int data;
    struct BTNode *lchild,*rchild;
}BTNode,*BiTree;
/*
T指当前为根的树
depth指当前结点的深度
count计数处理
*/
void Count_k_Leaf(BiTree T,int depth,int k,int &count){
    if(T==NULL)return 0;
    if(depth==k) count++;//当前结点在第k层
    Count_k_Leaf(T->lchild,depth+1,k,count);
    Count_k_Leaf(T->rchild,depth+1,k,count);
}
//非递归(层序遍历)
int Count_k_Leaf(BiTree T,int k){
    if(T==NULL) return 0;
    BiTree q[MAX_SIZE];
    int front=0,rear=0;
    int level=0,count;//分别表示层次值，第k层结点数
    BiTree p=T;
    q[++rear]=p;
    while(front<rear){
        level++;//深度+1
        if(level==k) cout=rear-front;
        int l=front+1,r=rear;
        for(int i=l;i<=r;i++){//对level层结点进行遍历
            if(q[i]->lchild!=NULL) q[++rear]=q[i]->lchild;
            if(q[i]->rchild!=NULL) q[++rear]=q[i]->rchild;
        }
        front=r;//更新队列的指针
    }
    return count;
}

假定一棵树以二叉链表进行存储，T指向该二叉树的根节点指针，p和q分别指向该二叉树中任意两个节点的指针，试编写算法找到p和q节点的最近公共祖先。

/*
后续遍历的非递归算法的特性：当访问一个结点p时，栈中结点恰好是p结点的所有祖先
*/
#define MAX_SIZE 105
typedef struct BTNode{
    int data;
    struct BTNode *lchild,*rchild;
}BTNode,*BiTree;
BiTree SearchAncestor(BiTree T,BiTree p,BiTree q){
    //s辅助栈s1存储p结点的祖先s2存储q结点的祖先
    BiTree s[MAX_SIZE],s1[MAX_SIZE],s2[MAX_SIZE];
    int top=0,top1=0,top2=0;
    BiTree t=T,r=NULL;//遍历指针 最近访问过的结点 
    while(t!=NULL || top > 0){
        while(t!=NULL){
            s[++top]=t;
            t=t->lchild;
        }
        //向右走
        t=s[top];//获取栈顶元素
        if(t->rchild && t->rchild != r){//若右子树存在且未被访问过
            t=t->rchild;//转向右子树
        }else{//否则，弹出结点并访问
            if(t==p){
                for(int i=top;i>0;i--) s1[++top1]=s[i];
            }
            if(t==q){
                for(int i=top;i>0;i--) s2[++top2]=s[i];
            }
            top--;//栈顶元素出栈
            r=t;//记录最近访问过的结点
            t=NULL;//结点访问完，重置t指针
        }
    }
    //自顶向下查找最后一个相同结点
    while(top1>0&&top2>0&&s1[top1]==s2[top2]){
        top1--;top2--;
    }
    return s1[top1-1];
}