第四章树和二叉树

第四章树和二叉树

二叉树的存储结构

typedef int ElemType;
//顺序存储结构体定义描述
#define MAX_SIZE 100
typedef ElemType SqBitree[MAX_SIZE];
SqBiTree bt;

//链式存储结构
//二叉链表形式：
typedef struct BTNode {
    ElemType data;
    struct BTNode *lchild,*rchild;
}BTNode,*BiTree;

//三叉链表形式：
typedef struct BTNode{
    ElemType data;
    struct BTNode *lchild,*rchild,*parent;
}BTNode,*BiTree;

void visit(BiTree T){
    cout<<T->data<<" ";
}

二叉树的遍历递归写法

//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);   //访问根节点
        PreOrder(T->lchild);//递归遍历左子树
        PreOrder(T->rchild);//递归遍历右子树
    }
}
//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);//递归遍历左子树
        visit(T);   //访问根节点
        InOrder(T->rchild);//递归遍历右子树
    }
}
//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);//递归遍历左子树
        PostOrder(T->rchild);//递归遍历右子树
        visit(T);   //访问根节点
    }
}

非递归遍历

//先序遍历
void PreOrder2(BiTree T){
    BiTree Stack[MAX_SIZE];//初始化栈和遍历指针
    int top=0;
    BiTree p=T;
    while(p!=NULL||top>0){//栈不为空或p不为空时循环
        while(p!=NULL){ 
            visit(p);//访问当前结点
            Stack[++top]=p;//当前结点入栈
            p=p->lchild;//左孩子不为空一直往左走
        }
        p=Stack[top--];//栈顶元素出栈
        p=p->rchild;//向右子树走即p赋值为当前结点的右子树
    }
}
//中序遍历
void InOrder2(BiTree T){
    BiTree Stack[MAX_SIZE];//初始化 栈 和 遍历指针
    int top=0;    
    BiTree p=T;
    while(p!=NULL||top>0){//栈不空或p不空时循环
        while(p!=NULL){//一直往左走
            Stack[++top]=p;//当前结点入栈
            p=p->lchild;//左孩子不为空一直往左走
        }
        p=Stack[top--];//栈顶元素出栈 并访问
        visit(p);
        p=p->rchild;////向右子树走即p赋值为当前结点的右子树
    }
}

//后续遍历LRN 逆序 NRL 先根遍历NLR 
void PostOrder2(BiTree T){
    BiTree Stack1[MAX_SIZE];
    BiTree Stack2[MAX_SIZE];
    int top1=0,top2=0;
    BiTree p=T;
    while(p!=NULL||top1>0){
        while(p!=NULL){
            Stack[++top1]=p;
            Stack[++top2]=p;//存储后序列
            p=p->rchild;
        }
        p=Stack1[top--];
        p=p->lchild;
    }
    //Stack2中的元素依次出栈就是后续遍历。
    while(top2>0){
        visit(Stack2[top2]);
        top2--;
    }
}
void PostOrder2(BiTree T) {
    BiTree Stack[MAX_SIZE];
    BiTree p = T, r = NULL;// 遍历指针 最近访问过指针
    int top = 0;
    while (p !=NULL || top > 0) {
        while (p != NULL) { //一直向左走
            Stack[++top] = p;
            p = p->lchild;
        }//向右走
        p = Stack[top]; //获取栈顶元素
        if (p->rchild && p->rchild != r) {//若右子树存在且未被访问过
            p = p->rchild; //转向右子树
            } else { //否则，弹出结点并访问
                p = Stack[top--];
                visit(p);//访问结点
                r = p; //记录最近访问过的结点
                p = NULL;//结点访问完，重置p指针
            }
        }
}
// 注意：每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，需将p置NULL

层次遍历

void LevelOrder(BiTree L){
    BiTree que[MAX_SIZE];
    BiTree q=T;         //工作指针
    int front=0,rear=0;//队列的指针
    if(q==NULL) return;//特判
    que[++rear]=q;      //根节点入队
    while(front<rear){//队列不空 则循环
        q=que[++front];      //队头出队
        visit(q);           //访问出队结点
        if(q->lchild!=NULL) que[++rear]=q->lchild;//左子树不空，入队
        if(q->rchild!=NULL) que[++rear]=q->rchild;//右子树不空，入队
    }
}

线索二叉树

typedef struct ThreadNode{
    ElemType data;                  //数据域
    struct TreadNode *lchild,*rchild;//左，右孩子指针
    int ltag,rtag;//左,右线索标志
}ThreadNode,*ThreadTree;
//线索二叉树中序遍历
void InThread(ThreadTree &p,ThreadTree &pre){
    if(p!=NULL){
        InThread(p->lchild,pre);//递归线索二叉树
        if(p->lchild=NULL){     //左子树为空建立前驱线索
            p->lchild=pre; 
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=p;      //建立前驱结点的后继线索
            pre->rtag=1;
        }
        pre=p;                  //标记当前结点为刚刚访问过的结点
        InThread(p->rchild,pre);
    }
}
void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){//非空二叉树线索化
        InThread(T,pre);//线索化二叉树
        pre->rchild=NULL;//处理最后一个结点
        pre->rtag=1;
    }
}

//求中序序列下第一个结点
ThreadNode *Firstnote(ThreadNode *p){
    while(p->ltag==0)p=p->lchild;
    return p;
}
//求结点p在中序序列下的后继
ThreadNode *Nextnode(ThreadNode *p){
    while(p->rtag==0) return Firstnote(p->lchild);
    return p->rchild;
}

//中序线索二叉树的中序遍历算法
void InOrder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
        visit(p);
    }
}

哈夫曼树

#define MAX_NODE 200
typedef struct{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode;
//创建一个叶子结点数为n的Huffman树
void Create_Huffman(unsigned n,HTNode HT[],unsigned m){
    unsigned int w;
    int k,j;
    for(k=1;k<m;k++){       //输入时，所有叶子结点都有权值
        if(k<=n){
            cout<<"输入w=";
            cin>>w;
            HT[k].weight=w;
        }else HT[k].weight=0; //非叶子结点没有权值
        HT[k].parent=HT[k].lchild=HT[k].rchild=0;
    }
    for(k=n+1;k<m;k++){
        unsigned w1=32767,w2=w1;//w1,w2分别保存权值最小的两个权值
        int p1=0,p2=0;          //p1,p2保存两个最小权值的下标
        for(j=1;j<=k-1;j++){
            if(HT[k].parent==0){    //尚未合并
                if(HT[j].weight<w1){
                    w2=w1;
                    p2=p1;
                    w1=HT[j].weight;
                    p1=j;
                }else if(HT[j].weight<w2){
                    w2=HT[j].weight;
                    p2=j;
                }
            }//找到权值最小的两个值及其下标
        }
        HT[k].lchild=p1;
        HT[k].rchild=p2;
        HT[k].weight=w1+w2;
        HT[p1].parent=k;
        HT[p2].parent=k;
    }
}
void Huff_coding(unsigned n,HTNode HT[],unsigned m){
    int k,sp,fp;
    char *cd,*HC[m];
    cd=(char *)malloc(m* sizeof(char));
    cd[n]='\0';
    for(k=1;k<n+1;k++){
        sp=n;
        int p=k;
        fp=HT[k].parent;
        for(;fp!=0;p=fp,fp=HP[p].parent);//从叶子结点到根你想求编码
            if(HT[fp].lchild==p)cd[--p]='0';
            else cd[--sp]='1';
            HC[k]=(char *)malloc((n-sp)*sizeof(char));//为第k个字符分配保存编码的空间
            strcpy(HC[k],&cd[sp]);
    }
    free(cd);
}

课后作业

//给定权值集合={3,5,7,9,11,12},请构造关于w的一棵Huffman树，并求其加权路径长度WPL
/*

1. 集合中找到根节点权值最小的两棵树
2. 合并两棵树生成一棵新的树加入到集合中，删除原来的树
3. 重复1,2步骤知道只剩下最后一棵树

3,5,7,9,11,12
7,8,9,11,12
9,11,12,15
12,15,20
20,27
47
*/

求二叉树所有的叶子结点数

int ans=0;
int count(BTNode *p){
    if(p==NULL) return;
    else{
        if(p->lchild==NULL&&p->rchild==NULL)
            ans++;
        count(p->lchild);
        count(p->rchild);
    }
}

求二叉树中值为x的结点层号

int leno(BTNode *p,char x,int lev){
    if(p==NULL)
        return 0;
    else{
        if(p->data==x)
            cout<<lev<<endl;
        leno(p->lchild,x,lev+1);
        leno(p->rchild,x,lev+1);
    }
}

int ans=0;
int leno(BTNode *p,char x){
    if(p!=NULL){
        if(p->data==x)
            cout<<ans<<endl;
        ++ans;
        leno(p->lchild,x);
        leno(p->rchild,x);
        --ans;
    }
}

树顺序存储求i和j结点的最近公共祖先结点的值

int forefather(ptree &p,int i,int j){
    if(i<1||j<1)
        return 0;
    else{
        for(;i!=0;i/=2){
            for(;j!=0;j/=2){
                if(i==j){
                    return p.HI[i].data;
                }
            }
        }
    }
    return 0;
}

满二叉树已知先序pre，求后序post

void change(char pre[],int L1,int R1,char post[],int L2,int R2){
    if(L1<=R1){
        post[R2]=pre[L1];//将pre[]中的第一个元素放在post[]的末尾
        change(pre,L1+1,(L1+1+R1)/2,post,L2,(L2+R2-1)/2);//递归处理pre[]中的前一半序列，将其存在post[]数组对应的前一半位置
        change(pre,(L1+1+R1)/2+1,R1,post,(L2+R2-1)/2+1,R2-1);//递归处理pre[]中的后一半序列，将其存在post[]数组对应的后一半位置
    }
}