C++

「二叉树」二叉树详解

引入——动态链表

链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。

Singly-linked-list.svg
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址,在最后一个节点保存一个特殊的结束标记,另外在一个固定的位置保存指向第一个节点的指针,有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来,然后直接访问。当然如果只是访问数据就没必要了,不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个(需要储存反向的指针,见下面的双向链表)节点。

相对于下面的双向链表,这种普通的,每个节点只有一个指针的链表也叫单向链表,或者单链表,通常用在每次都只会按顺序遍历这个链表的时候(例如图的邻接表,通常都是按固定顺序访问的)。

写法:简单易懂 老少咸宜

第一次保留head指针指向链表的头,要么就丢了…

#include <iostream>
#include <cstdio>
using namespace std;
struct node{
    int data; node *next;
    node(int k){data=k;next=NULL;}
}*head,*p1,*p2;
int main(){
    int x;
    cin>>x;
    if(x!=0){
        p1=new node(x);
        head=p1;
    }
    else return 0;
    while(scanf("%d",&x) && x!=0){
        p2=new node(x);
        p1->next=p2;
        p1=p2;
    }
    p1=head;
    while(p1){
        printf("%d",p1->data);
        p1=p1->next;
    }
    return 0;
}

二叉树常用操作基本模版

存储结构:

struct node{
    char data;
    struct node *lch,*rch;
}node[N];

递归建树:

void create(node* &T){
    char ch;
    ch=cin.get();
    if(ch=='#') T=NULL;
    else{
        T=newnode();
        T->data=ch;
        create(T->lch);
        create(T->rch);
    }
}

二叉树的存储和遍历代码:

#include <iostream>
using namespace std;
#define N 1005

struct node{
    char data;
    struct node *lch,*rch;
}node[N];
node *root;

int cnt;

node* newnode(){
    node *u=&node[++cnt];
    u->lch=u->rch=NULL;
    return u;
}

void create(node* &T){
    char ch;
    ch=cin.get();
    if(ch=='#') T=NULL;
    else{
        T=newnode();
        T->data=ch;
        create(T->lch);
        create(T->rch);
    }
}

void pre(node* &T){
    if(T){
        cout<<T->data;
        pre(T->lch);
        pre(T->rch);
    }
}

void mid(node* &T){
    if(T){
        mid(T->lch);
        cout<<T->data;
        mid(T->rch);
    }
}

void pos(node* &T){
    if(T){
        pos(T->lch);
        pos(T->rch);
        cout<<T->data;
    }
}

int main(){
    create(T);
    pre(T);cout<<endl;//前序遍历
    mid(T);cout<<endl;//中序遍历
    pos(T);cout<<endl;//后序遍历
    return 0;
}
分享到