[数据结构与算法]王道【2022年数据结构考研复习指导】书P197思维拓展

#include <iostream>
#include <stack>
#include <map>
#include <string.h>
#include <queue>

using namespace std;

#define MaxSize 255
#define InTree -1
typedef int ElemType;
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void BTreeInit(BiTree &root){
    root=(BiTree)malloc(sizeof(BiTNode));
    root->lchild=NULL;
    root->rchild=NULL;
}

void BiTNodeInit(BiTree &bn,int x){
    bn=(BiTNode*)malloc(sizeof(BiTNode));
    bn->lchild=NULL;
    bn->rchild=NULL;
    bn->data=x;
}

void BTreeInput(BiTree &root){
    int *arr=new int[255];
    int i;
    for(i=1;;i++){
        cin>>arr[i];
        if(arr[i]==9999){
            i--;
            break;
        }
    }

    BTreeInit(root);
    root->data=arr[1];

    map<int,BiTNode*> index;
    int vis[255];
    int j=1;
    memset(vis,0,sizeof(vis));


    BiTNode *node=root;
    index[1]=root;
    BiTNode *tmp;

    for(j=1;j<=i;j++){
        node=index[j];

        int l=j*2,r=l+1;
        if(l<=i && vis[l]==0){
            BiTNodeInit(tmp,arr[l]);
            node->lchild=tmp;
            //cout<<"lchild="<<tmp->data<<" ";
            vis[l]=1;
            index[l]=tmp;
        }
        if(r<=i && vis[r]==0){
            BiTNodeInit(tmp,arr[r]);
            node->rchild=tmp;
            //cout<<"rchild="<<tmp->data<<" ";
            vis[r]=1;
            index[r]=tmp;
        }
    }
    delete arr;
}

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild); 
        cout<<T->data<<" ";
        InOrder(T->rchild);
    }
}

int S[100];
int top=-1;

void path(BiTree T,int &sum,int k){
    if(T){
        S[++top]=T->data;
        sum+=T->data;
        if(sum==k){
            for(int i=0;i<=top;i++){
                cout<<S[i];
                if(i<top)
                    cout<<"-";
            }
            cout<<endl;
        }

        path(T->lchild,sum,k);
        path(T->rchild,sum,k);
        sum-=T->data;
        top--;
    }
}

void printPathK(BiTree T,int k){
    int sum=0;
    path(T,sum,k);
}

int main()
{
    BiTree root;
    BTreeInput(root);

    cout<<"InOrder:"<<endl;
    InOrder(root);

    
    int k;
    cin>>k;
    cout<<"Print path:"<<endl;
    printPathK(root,k);

    cout<<"Hello world!"<<endl;

    system("pause");
    return 0;
}

path() 函数实现打印路径的功能。