顺序表

7-3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef struct book
{
    char name[50];
    char no[20];
    float price;
} book;
typedef struct lnode
{
    book *elem;
    int length;
} lnode;
int main()
{
    lnode L;
    L.elem = (book *)malloc(sizeof(struct book) * MAXSIZE);
    L.length = 0;
    char nname[50];
    char insb[20];
    float pprice;
    scanf("%s%s%f", insb, nname, &pprice);
    while (strcmp(insb,"0")!=0&&strcmp(nname,"0")!=0&&pprice!=0)
    {
        strcpy(L.elem[L.length].no, insb);
        strcpy(L.elem[L.length].name, nname);
        L.elem[L.length].price = pprice;
        L.length++;
        scanf("%s%s%f", insb, nname, &pprice);
    }
    printf("%d\n", L.length);
    for (int i = 0; i < L.length; i++)
    {
        printf("%s %s %.2f\n", L.elem[i].no, L.elem[i].name, L.elem[i].price);
    }
    return 0;
}

7-4

//c++
#include <iostream>
using namespace std;
struct list
{
    int *num;
    int *index;
    int length;
};
list intilist(int a)
{
    list la;
    if (a == 0)
    {
        la.length = 1;
        la.index = new int[1];
        la.num = new int[1];
        la.num[0] = 0;
        la.index[0] = 0;
    }
    else
    {
        la.length = a;
        la.index = new int[a];
        la.num = new int[a];
        for (int i = 0; i < a; i++)
        {
            cin >> la.num[i] >> la.index[i];
        }
    }
    return la;
}
list addlist(list la, list lb)
{
    list lc;
    lc.length = la.length + lb.length;
    lc.index = new int[lc.length];
    lc.num = new int[lc.length];
    int a = 0, b = 0, c = 0;
    while (a < la.length && b < lb.length)
    {
        if (la.index[a] < lb.index[b])
        {
            lc.num[c] = lb.num[b];
            lc.index[c] = lb.index[b];
            b++;
            c++;
        }
        else if (la.index[a] > lb.index[b])
        {
            lc.num[c] = la.num[a];
            lc.index[c] = la.index[a];
            a++;
            c++;
        }
        else
        {
            int sum = la.num[a] + lb.num[b];
            if (sum != 0)
            {
                lc.num[c] = la.num[a] + lb.num[b];
                lc.index[c] = la.index[a];
                c++;
            }
            a++;
            b++;
        }
    }
    while (a < la.length)
    {
        lc.num[c] = la.num[a];
        lc.index[c] = la.index[a];
        a++;
        c++;
    }
    while (b < lb.length)
    {
        lc.num[c] = lb.num[b];
        lc.index[c] = lb.index[b];
        b++;
        c++;
    }
    if(c==0)
        cout <<"0 0";
    lc.length = c;
    return lc;
}
int main()
{
    int a;
    cin >> a;
    list la = intilist(a);
    int b;
    cin >> b;
    list lb = intilist(b);
    list lc = addlist(la, lb);
    for (int i = 0; i < lc.length; i++)
    {

        if (i < lc.length - 1)
            cout << lc.num[i] << " " << lc.index[i] << " ";
        else
            cout << lc.num[i] << " " << lc.index[i];
    }
    
    return 0;
}

7-1

#include<stdio.h>
int main ()
{
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    for(int i=0;i<n;i++)
        i<n-1?printf("%d ",arr[i]):printf("%d",arr[i]);
    return 0;
}

7-2

//c++
#include <iostream>
using namespace std;
struct llist
{
    int *data;
    int length;
};
llist *creatlist(int length)
{
    llist *l = new llist;
    l->length = length;
    l->data = new int[length];
    for (int i = 0; i < length; i++)
    {
        cin >> l->data[i];
    }
    return l;
}
int main()
{
    int a;
    cin >> a;
    llist *la = creatlist(a);
    int b;
    cin >> b;
    llist *lb = creatlist(b);


    llist *lc = new llist;
    lc->data = new int[a + b];
    lc->length = a;
    for (int i = 0; i < a; i++)
    {
        lc->data[i] = la->data[i];
    }
    int flag;
    for (int i = 0; i < b; i++)
    {
        flag = 0;
        for (int j = 0; j < a; j++)
        {
            if (lb->data[i] == lc->data[j])
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            lc->length++;
            lc->data[lc->length - 1] = lb->data[i];
        }
    }
    for (int i = 0; i < lc->length; i++)
        cout << lc->data[i] << " ";
    return 0;
}

链表

7-1 单链表的创建，遍历与销毁

//c
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} node;

int main()
{
    int n;
    scanf("%d", &n);

    node *head = NULL;
    while(n!=-1)
    {
        node *newnode=(node*)malloc(sizeof(node));
        newnode->data=n;
        newnode->next=head;
        
        head=newnode;
        scanf("%d", &n);
    }

    node *endp=(node*)malloc(sizeof(node));
    endp->data=-1;
    endp->next=head;
    head=endp;
    
    node *ptr = head->next;
    while (ptr != NULL)
    {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }

    ptr = head;
    while (ptr != NULL)
    {
        node *next_node = ptr->next;
        free(ptr);
        ptr = next_node;
    }

    return 0;
}

7-2 在有序链表中插入数据

#include <iostream>
using namespace std;

struct Lnode
{
    int data;
    Lnode *next;
};

void insert(Lnode *head, int x)
{
    Lnode *newLnode = new Lnode;
    newLnode->data = x;
    newLnode->next = NULL;

    Lnode *cur = head;
    while (cur->next != NULL && cur->next->data < x)
    {
        cur = cur->next;
    }

    if (cur->next == NULL || cur->next->data != x)
    {
        newLnode->next = cur->next;
        cur->next = newLnode;
    }
}

void Print(Lnode *head)
{
    Lnode *cur = head->next;
    while (cur != NULL)
    {
        cout << cur->data;
        if (cur->next != NULL)
        {
            cout << " ";
        }
        cur = cur->next;
    }
}

int main()
{
    int n, x;
    cin >> n;

    Lnode *head = new Lnode;
    head->next = NULL;

    Lnode *cur = head;
    for (int i = 0; i < n; i++)
    {
        int data;
        cin >> data;

        Lnode *newLnode = new Lnode;
        newLnode->data = data;
        newLnode->next = NULL;

        cur->next = newLnode;
        cur = newLnode;
    }

    cin >> x;

    insert(head, x);
    Print(head);

    return 0;
}

7-3 学生信息输入输出

#include <iostream>
#include <string>
using namespace std;
struct Lnode
{
    int index;
    string name;
    int score;
    Lnode *next;
};
int main()
{
    Lnode *head = new Lnode;
    head->next = NULL;
    int n;
    cin >> n;
    Lnode *p = head;
    while (n != 0)
    {
        Lnode *newnode = new Lnode;
        cin >>newnode->name >> newnode->score;
        newnode->index = n;
        p->next = newnode;
        p = newnode;
        cin >> n;
    }
    p->next = NULL;
    Lnode *ptr = head->next;
    while (ptr != NULL)
    {
        cout << ptr->index << " " << ptr->name << " " << ptr->score << endl;
        ptr = ptr->next;
    }
    return 0;
}

7-4 求链式线性表的倒数第K项

#include<stdio.h>
#include<stdlib.h>
 
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;
 
int main()
{
    int temp;
    int k,cnt=0;
    LinkList L;
    L = (LinkList)malloc( sizeof ( struct LNode));
    LNode *s=L,*r=L,*p;
 
    scanf("%d",&k);
    int f=k;
    while(1){
        scanf("%d",&temp);
        if( temp<0 ){
            break;
        }
        else{
            p=(LNode *)malloc(sizeof(LNode));
            p->data = temp;
            r->next = p;
            r = p;
            k--;
            cnt++;
            if( k<1){
                s= s->next;
            }
        }
    }
    if( f>cnt){
        printf("NULL");
    }
    else printf("%d",s->data);
 
     return 0;
}

7-5 输出链表偶数结点

#include<iostream>
using namespace std;
struct Lnode
{
    int data;
    Lnode *next;
};
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin >> n;
        Lnode *head = new Lnode;
        Lnode *s;
        head->next = NULL;
        s = head;
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            Lnode *newnde=new Lnode;
            newnde->data=a;

            s->next=newnde;
            s=newnde;
        }
        s->next=NULL;

        Lnode *p=head->next;
        int count=0;
        while(p!=NULL)
        {
            count++;
            if(count%2==0)
            count<n-n%2?cout<<p->data<<" ":cout<<p->data;
            p=p->next;
        }
        cout<<endl;
    }
}

7-6 头插法创建单链表、遍历链表、删除链表

#include <iostream>
using namespace std;
struct Lnode
{
    int data;
    Lnode *next;
};
typedef Lnode *LinkList;
LinkList CreatNode()
{
    LinkList head = new Lnode;
    head->next = NULL;
    LinkList p = head->next;
    int n;
    cin >> n;
    while (n != -1)
    {
        Lnode *newnode = new Lnode;
        newnode->data = n;
        newnode->next = p;

        p = newnode;
        cin >> n;
    }
    head->next = p;
    return head;
}
void TravelNode(LinkList head)
{
    LinkList p=head->next;
    while (p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
void DelNode(LinkList head)
{
    LinkList p = head->next;
    LinkList q = p->next;
    delete (head);
    while (q != NULL)
    {
        delete (p);
        p = q;
        q = q->next;
    }
    delete (q);
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        Lnode *head = CreatNode();
        TravelNode(head);
       DelNode(head);
    }
    return 0;
}

7-7 单链表逆置

#include<iostream>
using namespace std;
struct Lnode
{
    int data;
    Lnode *next;
};
Lnode *cteate(int n)
{
    Lnode *head = new Lnode;
    head->next=NULL;
    Lnode *p = head;
    int a;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        Lnode  *newnode=new Lnode;
        newnode->data=a;
        newnode->next=NULL;

        p->next=newnode;
        p=newnode;
    }
    p->next=NULL;
    return head;
}
Lnode *oponode(Lnode *head)
{
    Lnode *pCur=head->next;
    Lnode *pPre=NULL;
    Lnode *pNext;
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    while (pCur)
    {
        pNext = pCur->next;
        pCur->next = pPre;
        pPre = pCur;
        pCur = pNext;
    }
    head->next = pPre;
    return head;
}
void print(Lnode *head)
{
    Lnode *p=head->next;
    while(p!=NULL)
    {
            cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    int n;
    cin>>n;
    Lnode *head=cteate(n);
    head = oponode(head);
    print(head);

    return 0;
}

7-8 两个有序链表序列的合并

#include <iostream>
using namespace std;

struct listnode
{
    int data;
    listnode *next;
};
listnode *CreatNode()
{
    listnode *head = new listnode;
    head->next = NULL;
    listnode *ptr = head;
    int n;
    cin >> n;
    while (n != -1)
    {
        listnode *newnode = new listnode;
        newnode->data = n;
        ptr->next = newnode;
        ptr = newnode;
        cin >> n;
    }
    return head;
}
listnode *AddNode(listnode *a, listnode *b)
{
    listnode *cHead= new listnode;
      a = a->next;
    b = b->next;
    cHead->next=NULL;
     if (a == NULL && b == NULL) {
        return cHead;
    }
    listnode *cPtr=cHead;
    while(a!=NULL&&b!=NULL)
    {
        listnode *newnode=new listnode;
        if(a->data<b->data)
        {
            newnode->data=a->data;
            a=a->next;

            cPtr->next=newnode;
            cPtr=newnode;
        }
        else 
        {
            newnode->data=b->data;
            b=b->next;

            cPtr->next=newnode;
            cPtr=newnode;
        }
        // else
        // {
        //     newnode->data=a->data;
        //     a=a->next;
        //     b=b->next;

        //     cPtr->next=newnode;
        //     cPtr=newnode;
        // }
        cPtr->next=NULL;
    }
    while(a!=NULL)
    {
        listnode *newnode=new listnode;
        newnode->data=a->data;
        a=a->next;
        cPtr->next=newnode;
        cPtr=newnode;
        cPtr->next=NULL;
    }
    while(b!=NULL)
    {
        listnode *newnode=new listnode;
        newnode->data=b->data;
        b=b->next;
        cPtr->next=newnode;
        cPtr=newnode;
        cPtr->next=NULL;
    }   
    return cHead;
}
void PrintNode(listnode *a)
{
    listnode *p=a->next;
    if(p==NULL)
        cout<<"NULL";
    while (p != NULL)
    {
        if (p->next == NULL)
            cout << p->data<<endl;
        else
            cout << p->data << " ";
        p = p->next;
    }
}
int main()
{
    listnode *a = CreatNode();
    listnode *b = CreatNode();
    listnode *c = AddNode(a, b);
    PrintNode(c);
    return 0;
}

栈

7-1 栈的实现及基本操作

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    stack<int> s1;
    int n,a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin >>a;
        if(a==1)
        {
            cin >> b;
            s1.push(b);
        }
        else
        {
            if(s1.empty())
                cout<<"invalid"<<endl;
            else
            {
               cout<<s1.top()<<endl;
                s1.pop();
            }
        }
    }
    return 0;
}

7-2 数据结构考题 十进制转换为二进制

#include <iostream>
using namespace std;
#define MAX 100
struct stack
{
    int *base;
    int *top;
};
void push(stack &s, int n)
{
    *s.top = n;
    s.top++;
}
void pop(stack &s)
{
    s.top--;
    cout << *s.top;
}
int main()
{
    int n;
    cin >> n;
    stack s;
    s.base = new int[MAX];
    s.top = s.base;
    while (n != 0)
    {
       int a = n % 2;
        push(s, a);
        n /= 2;
    }
    
    while (s.top != s.base)
    {
        pop(s);
    }
    cout << endl;
    return 0;
}

7-4 栈操作的合法性

这里我们提供两种方法

//方法一 novice
#include <iostream>
#include <stack>
#include <string>
using namespace std;
void justify(const string &str, int m)
{
    stack<char> s;
    int countS = 0;
    for (int i = 0; i < str.length(); i++)
    {
        char ch = str[i];
        if (ch == 'S')
        {
            if (countS >= m)
            {
                cout << "NO" << endl;
                return;
            }
            s.push(ch);
            countS++;
        }
        else if (ch == 'X')
        {
            if (s.empty())
            {
                cout << "NO" << endl;
                return;
            }
            s.pop();
        }
    }
    if (s.empty())
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        justify(str, m);
    }
    return 0;
}

//方法二 pro
#include <iostream>
#include <stack>
#include <string>
using namespace std;

void justify(const string &str, int m)
{
    stack<char> s;
    int countS = 0;
    for (auto ch : str)
    {
        if (ch == 'S')
        {
            if (countS >= m)
            {
                cout << "NO" << endl;
                return;
            }
            s.push(ch);
            countS++;
        }
        else if (ch == 'X')
        {
            if (s.empty())
            {
                cout << "NO" << endl;
                return;
            }
            s.pop();
        }
    }
    if (s.empty())
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        justify(str, m);
    }
    return 0;
}

7-5 括号匹配

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
    string str;
    stack<char> s;
    cin >> str;
    int left = 0, right = 0;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == '('&&i<str.length()-1)
        {
            s.push(str[i]);
            left++;
        }
        if (str[i] == ')')
        {
            if (s.empty())
            {
                s.push(str[i]);
                right++;
            }
            else if (s.top() == '(')
            {
                s.pop();
                left--;
            }
            else
            {
                s.push(str[i]);
                right++;
            }
        }
        if (str[i] == '['&&i<str.length()-1)
        {
            s.push(str[i]);
            left++;
        }
        if (str[i] == ']')
        {
            if (s.empty())
            {
                s.push(str[i]);
                right++;
            }
            else if (s.top() == '[')
            {
                s.pop();
                left--;
            }
            else
            {
                s.push(str[i]);
                right++;
            }
        }
        if (str[i] == '{'&&i<str.length()-1)
        {
            s.push(str[i]);
            left++;
        }
        if (str[i] == '}')
        {
            if (s.empty())
            {
                s.push(str[i]);
                right++;
            }
            else if (s.top() == '{')
            {
                s.pop();
                left--;
            }
            else
            {
                s.push(str[i]);
                right++;
            }
        }
    }
    if (s.empty())
        cout << "Brackets match" << endl;
    else if (left !=0 && right == 0)
        cout << "Extra left brackets" << endl;
    else if (left ==0 && right != 0)
        cout << "Extra right brackets" << endl;
    else
        cout << "Brackets not match" << endl;
    return 0;
}

7-5 中缀表达式转换为后缀表达式并求值

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 20

typedef struct
{
    int data[MAX_SIZE];
    int *base;
    int *top;
} Stack;

void push(Stack *stack, int num)
{
    *(++stack->top) = num;
}

int pop(Stack *stack)
{
    return *(stack->top--);
}

bool is_empty(Stack *stack)
{
    return stack->top == stack->base - 1;
}

int peek(Stack *stack)
{
    return *(stack->top);
}

bool is_operator(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int precedence(char op)
{
    if (op == '*' || op == '/')
        return 2;
    else if (op == '+' || op == '-')
        return 1;
    else
        return 0;
}

void infix_to_postfix(char *infix, char *postfix)
{
    Stack stack;
    stack.base = stack.data;
    stack.top = stack.base - 1;

    int i = 0, j = 0;
    while (infix[i] != '\0')
    {
        char c = infix[i];
        if (c >= '0' && c <= '9')
        {
            postfix[j++] = c;
        }
        else if (c == '(')
        {
            push(&stack, c);
        }
        else if (c == ')')
        {
            while (!is_empty(&stack) && peek(&stack) != '(')
            {
                postfix[j++] = pop(&stack);
            }
            pop(&stack); 
        }
        else if (is_operator(c))
        {
            while (!is_empty(&stack) && precedence(c) <= precedence(peek(&stack)))
            {
                postfix[j++] = pop(&stack);
            }
            push(&stack, c);
        }
        i++;
    }

    while (!is_empty(&stack))
    {
        postfix[j++] = pop(&stack);
    }
    postfix[j] = '\0';
}

int evaluate_postfix(char *postfix)
{
    Stack stack;
    stack.base = stack.data;
    stack.top = stack.base - 1;

    int i = 0;
    while (postfix[i] != '\0')
    {
        char c = postfix[i];
        if (c >= '0' && c <= '9')
        {
            push(&stack, c - '0');
        }
        else if (is_operator(c))
        {
            int b = pop(&stack);
            int a = pop(&stack);
            int result;
            switch (c)
            {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = a / b;
                break;
            }
            push(&stack, result);
        }
        i++;
    }

    return pop(&stack);
}

int main()
{
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
    {
        char infix[MAX_SIZE];
        scanf("%s", infix);

        char postfix[MAX_SIZE];
        infix_to_postfix(infix, postfix);

        printf("%s ", postfix);
        printf("%d\n", evaluate_postfix(postfix));
    }

    return 0;
}

队列

7-1 队列的实现及基本操作

#include<iostream>
#include<queue>
using namespace std;
int main ()
{
    int n;
    cin>>n;
    queue<int> q1;
    for(int i=0;i<n;i++)
    {
        int x, y;
        cin >> x;
        if(x==1)
        {
            cin >> y;
            q1.push(y);
        }
        else
        {
            if(q1.empty())
            {
                cout<<"invalid"<<endl;
            }
            else
            {
                cout<<q1.front()<<endl;
                q1.pop();
            }
        }
    }
    return 0;
}

7-3 队列模拟

#include <iostream>
using namespace std;
#define MAX_SIZE 11
struct queue
{
    int data[MAX_SIZE];
    int front;
    int rear;
    queue() : front(0), rear(0){};
};

bool isempty(queue q)
{
    return q.front == q.rear;
}
bool is_full(queue q)
{
    return (q.rear + 1) % MAX_SIZE == q.front;
}
void push(queue &q, int x)
{
    if (is_full(q))
    {
        cout << "Queue is full!" << endl;
        return;
    }
    q.rear++;
    q.data[q.rear % MAX_SIZE] = x;
}
void pop(queue &q)
{
    if (isempty(q))
    {
        cout << "wrong" << endl;
        return;
    }
    q.front++;
}
void print(queue q)
{
    cout << "The Queue is:";
    for (int i = q.front + 1; i <= q.rear; i++)
    {
        cout << q.data[i % MAX_SIZE] << " ";
    }
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    queue q;
    while (n != 0)
    {
        if (n > 0)
        {
            if (is_full(q))
            {
                push(q, n);
                break;
            }
            else
            {
                push(q, n);
            }
        }
        else
        {
            if (isempty(q))
            {
                pop(q);
                break;
            }
            else
            {
                pop(q);
            }
        }
        cin >> n;
    }
    if (!isempty(q))
        print(q);

    return 0;
}

树和图

7-1 哈夫曼编码

#include <iostream>
#include <vector>
#include <string>
#define INT_MAX 10000
using namespace std;

struct HuffmantreeNode
{
    int weight, left, right, parent;
    char name;
};

class hufmantree
{
private:
    vector<HuffmantreeNode> tree;

public:
    vector<HuffmantreeNode> createhuffmantree()
    {
        string line;
        while (getline(cin, line))
        {
            if (line.empty())
            {
                break; // 如果输入为空行，则结束循环
            }
            char b = line[0];
            int c;
            if (line.size() == 4)
                c = line[3] - '0' + (line[2] - '0') * 10;
            else
                c = line[2] - '0';
            tree.push_back({c, 0, 0, 0, b});
        }
        int length = tree.size() - 1; // 获取输入的节点数
        for (int i = 0; i < length; i++)
        {
            int s1, s2;
            seletmin(tree, s1, s2);        // 选择权值最小的两个节点
            tree[s1].parent = tree.size(); // 设置第一个节点的父节点为当节点数
            tree[s2].parent = tree.size(); // 设置第二个节点的父节点为当前节点数
            tree.push_back({tree[s1].weight + tree[s2].weight, s1, s2, 0, '\0'});
        }
        return tree;
    }
    void printtree(vector<HuffmantreeNode> tree) // 输出哈夫曼树
    {
        int l = tree.size();
        for (int i = 0; i < l; i++)
        {
            cout << tree[i].weight << " " << tree[i].left << " " << tree[i].right << " " << tree[i].parent << " " << tree[i].name << endl;
        }
    }
    void seletmin(vector<HuffmantreeNode> tree, int &s1, int &s2)
    {
        int min = INT_MAX, cmin = INT_MAX;
        int length = tree.size();
        for (int i = 0; i < length; i++)
        {
            if (tree[i].parent == 0)
            {
                if (tree[i].weight < min)
                {
                    min = tree[i].weight; // 找到权值最小的节点
                    s1 = i;               // 记录该节点的下标
                }
            }
        }
        for(int i=0;i<length;i++)
        {
            if (tree[i].weight < cmin && tree[i].weight > min) // 找到权值次小的节点
            {
                cmin = tree[i].weight; // 记录该节点的权值
                s2 = i;                // 记录该节点的下标
            }
        }
    }
    int treesize()
    {
        return (tree.size() + 1) / 2;
    }
    void printcode(vector<HuffmantreeNode> tree)
    {
        for (int i = 0; i < treesize(); i++)
        {
            vector<char> str;
            int f = tree[i].parent;
            int c = i;
            while (f != 0)
            {
                if (tree[f].left == c)
                    str.push_back('0'); // 左子树标记为0，右子树标记为1
                else if (tree[f].right == c)
                    str.push_back('1'); // 左子树标记为0，右子树标记为1
                c = f;                  // 向上移动到父节点
                f = tree[f].parent;     // 向上移动到父节点
            }
            cout << tree[i].name << ":";              // 输出字符
            for (int j = str.size() - 1; j >= 0; j--) // 输出编码，从后往前输出，因为是从根节点到叶子节点的路径
            {
                cout << str[j]; // 输出编码
            }
            cout << endl;
        }
    }
};
int main()
{
    hufmantree ht;
    vector<HuffmantreeNode> tree = ht.createhuffmantree();
    //ht.printtree(tree);
    ht.printcode(tree);
    return 0;
}

7-2 叶节点求和

#include <iostream>
using namespace std;

struct treenode
{
    int parent, data;
    treenode *left, *right;
};

treenode *searchtree(treenode *root, int data)
{
    if (root == NULL || root->data == data)
        return root;
    
    treenode *leftResult = searchtree(root->left, data);
    if (leftResult != NULL)
        return leftResult;

    treenode *rightResult = searchtree(root->right, data);
    if (rightResult != NULL)
        return rightResult;

    return NULL; // 当左子树和右子树都未找到目标数据时返回NULL
}

void maketree(treenode *&root, int n)
{
    root = new treenode;
    root->left = root->right = NULL;
    cin >> root->data;

    for (int i = 0; i < n-1; i++)
    {
        int parent, data, position;
        cin >> parent >> position >> data;
        treenode *newnode = new treenode;
        newnode->data = data;
        newnode->parent = parent;
        newnode->left = NULL;
        newnode->right = NULL;
        if(position == 0)
        {
            searchtree(root, parent)->left = newnode;
        }
        else
        {
            searchtree(root, parent)->right = newnode;
        }
    }
}

int addleaves(treenode *root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
    else
        return addleaves(root->left) + addleaves(root->right);
}

int main()
{
    treenode *root = NULL;
    int n;
    cin >> n;
    maketree(root, n);
    cout << addleaves(root) << endl;
    return 0;
}