PHP&C语言数据结构

2023/12/27 Basic 数据结构

字数统计: 5.1k字 | 阅读时长: 26分 | 总文章阅读量：次

前言

本人为了方便理解，于是用自己最熟悉的语言PHP来学习数据结构~~（PHP是世界上最好的语言）~~

不过考试可不考PHP，所以我这里再用C复现一遍~~（作为PHP的底层应该不难吧（心虚））~~

PHP部分的源码学习来源于：https://www.zhihu.com/column/zyblog

PHP实现的部分本人只完成了链表，栈，队列和树

链表

PHP实现

<?php
class Node{
    public $data;
    public $next;
    public function __construct($data,$next=null){
        $this->data = $data;
        $this->next = $next;
    }
}

$node1 = new node(10);
$node2 = new node(20);
$node3 = new node(30);

$node1->next = $node2;
$node2->next = $node3;

//var_dump($node1);

function creat_link_list_head($arr=[]){ // 头插法
    $head = new Node($arr[0]);
    for($i=1;$i<count($arr);$i++){
        $node = new Node($arr[$i]);
        $node->next = $head;    // 从链表头部插入
        $head = $node;
    }
    //var_dump($head);
    return $head;
}
$lk = creat_link_list_head([1,5,13,22,7]);

function PrintList($link_list){
    while($link_list){
        print($link_list->data.',');
        $link_list = $link_list->next;
    }
}

//PrintList($lk);
//echo "\n";

function create_link_list_tail($arr=[]){    // 尾插法
    $head = new node($arr[0]);
    $tail = $head;
    for($i=1;$i<count($arr);$i++){
        $node = new Node($arr[$i]);
        $tail->next = $node;    // 从链表尾部插入
        $tail = $node;
    }
    //var_dump($head);
    return $head;
}
$lk = create_link_list_tail([41,13,66,3,11]);
PrintList($lk);
echo "\n";

function locateElem($link_list,&$e){    // 返回链表中值为e数据元素的地址
    $p=$link_list->next;    // 找节点标准语句
    $j=1;
    while($p&&$j){
        if($e==$p->data){
            return "地址为".$j+1;
        }
        $p=$p->next;
        ++$j;
        if(!$p){
            return "none";
        }
    }
}
$e=3;
echo locateElem($lk,$e);
echo "\n";

function insert(&$link_list,$i,$e){
    $p=$link_list;
    $j=1;
    while($p&&$j){
        $p=$p->next;
        ++$j;
        if($i==$j){
            $e->next=$p->next;
            $p->next=$e;
        }
    }
}
$e=new Node(77);
insert($lk,2,$e);
PrintList($lk);
echo "\n";

function delete(&$link_list,$i){
    $p=$link_list;
    $j=1;
    while($p&&$j){
        $p=$p->next;
        ++$j;
        if($i==$j){
            $p->next=$p->next->next;
        }
    }
}
delete($lk,4);
PrintList($lk);
echo "\n";

我们现在来分组拆开用c实现

首先是数据对象——结点，在c语言中用typedef结构体实现，也就是对应php中的class

class Node{
    public $data;
    public $next;
    public function __construct($data,$next=null){
        $this->data = $data;
        $this->next = $next;
    }
}

typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;	// 指向结构体 Node 的指针
}Node,*LinkList;

可以看出来链表的结点只需要定义数据域data和指针域*next

打印

然后我们尝试定义并打印一个链表，php只要直接实例化类然后指定指针域指向即可

$node1 = new node(10);
$node2 = new node(20);
$node3 = new node(30);

$node1->next = $node2;
$node2->next = $node3;

var_dump($node1);

而c语言则需要用malloc函数自行分配内存空间

void print(LinkList head)
{
    Node *current = head;
    while (current != NULL)
    {
        printf("%d ", current->data);
        printf("当前地址：%p ", &current->data);
        printf("指针指向：%p ", current->next);
        current = current->next;
        printf("\n");
    }
}

int main()
{
    // 创建链表节点
    Node *node1 = (Node *)malloc(sizeof(Node));
    Node *node2 = (Node *)malloc(sizeof(Node));
    Node *node3 = (Node *)malloc(sizeof(Node));

    // 构建链表
    node1->data = 10;
    node2->data = 20;
    node3->data = 30;

    node1->next = node2;
    node2->next = node3;
    node3->next = NULL;

    // 打印链表
    print(node1);

    // 释放内存
    free(node1);
    free(node2);
    free(node3);

    return 0;
}

这就是c语言写链表的基本方法了，现在我们来实现一些基本操作

尾插法创建链表

首先是尾插法：

基本思路就是设置头尾结点，每次添加结点的时候都从链表的尾部插入

function create_link_list_tail($arr=[]){    // 尾插法
    $head = new node($arr[0]);
    $tail = $head;
    for($i=1;$i<count($arr);$i++){
        $node = new Node($arr[$i]);
        $tail->next = $node;    // 从链表尾部插入
        $tail = $node;
    }
    //var_dump($head);
    return $head;
}

c的话我们不仅需要传入数组，还需要把链表的长度传入来开辟内存空间，然后这边把释放内存的方法再封装成函数一下

LinkList creat(ElemType e[], int size)
{
    LinkList head = NULL;
    LinkList tail = NULL;

    for (int i = 0; i < size; i++)
    {
        LinkList newNode = (LinkList)malloc(sizeof(Node));
        newNode->data = e[i];
        newNode->next = NULL;

        if (head == NULL)
        {
            // 链表为空，新节点作为头节点和尾节点
            head = newNode;
            tail = newNode;
        }
        else
        {
            // 链表不为空，将新节点插入到尾节点之后
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

// 释放链表内存
void freeLinkedList(LinkList head)
{
    Node *current = head;
    while (current != NULL)
    {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
}
int main()
{
    int elements[] = {10, 20, 30, 40, 50};
    int size = sizeof(elements) / sizeof(elements[0]);
    LinkList myList = creat(elements, size);
    print(myList);
    freeLinkedList(myList);
    return 0;
}

获取元素

接下来实现一些功能，有了前面的基础，后面就好写了

首先是获取某个位置上的元素

Status GetElem(LinkList L, int i, ElemType *e)
{
    // L为带头结点的单链表的头指针
    Node *p = L->next;
    int j = 1; // 计数
    while (p && j < i)
    {
        p = p->next; // 查找，直到p指向第i个元素或p为空
        ++j;
    }
    if (!p || j > i)
    {
        return ERROR; // 第i个元素不存在
    }
    *e = p->data;
    return OK;
}

int main(){
    /*
    前面必要的定义代码
    */
    ElemType e1;
    int i1 = 3;
    Status result = GetElem(myList, i1, &e1);
    if (result == OK)
    {
        printf("第%d个元素为：%d\n", i1, e1);
    }
    else
    {
        printf("第%d个元素不存在\n", i1);
    }
    
    freeLinkedList(myList);
    return 0;
}

指定位置插入

修改前一个结点的指针域指向要插入的结点

让要插入的结点的指针域指向后一个结点

Status insert(LinkList L, int i, ElemType e)
{
    Node *p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j; // 寻找第i-1个结点
    }
    if (!p || j > i - 1)
    {
        return ERROR; // i小于1或者大于表长加1
    }
    LinkList s = (LinkList)malloc(sizeof(Node)); // 生成新结点
    // 插入L中
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
int main(){
    /*
    前面必要的定义代码
    */
    ElemType e2 = 523;
    int i2 = 2;
    insert(myList, i2, e2);
    print(myList);
    
    freeLinkedList(myList);
    return 0;
}

指定位置删除

修改前一个结点的指针域指向下一个结点即可

Status delete(LinkList L, int i)
{
    Node *p = L;
    int j = 0;
    while (p->next && j < i - 1)
    {
        p = p->next;
        ++j;    // 寻找第i个结点，并令p指向其前驱
    }
    if (!(p->next || j < i - 1))
    {
        return ERROR;   // 删除位置不合理
    }
    Node *q = p->next;
    p->next = q->next;
    free(q);    // 释放被删除的结点
    return OK;
}
int main(){
    /*
    前面必要的定义代码
    */
    int i3 = 4;
    delete (myList, i3);
    print(myList);
    
    freeLinkedList(myList);
    return 0;
}

将两表并为一表

void Merge(LinkList La, LinkList Lb, LinkList Lc)
{
    // 已知La，Lb的元素按值非递减排列
    Node *pa = La->next;
    Node *pb = Lb->next;
    Node *pc = Lc;
    while (pa && pb)
    {
        if (pa->data <= pb->data) // 比大小，然后就是插入操作
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb; // 插入剩余段
    free(Lb);                // 释放Lb的头结点
}

int main(){
    int l1[] = {13, 31, 231, 442, 2453};
    int size1 = sizeof(l1) / sizeof(l1[0]);
    LinkList L1 = creat(l1, size1);
    int l2[] = {3, 56, 231, 1234, 5555};
    int size2 = sizeof(l2) / sizeof(l2[0]);
    LinkList L2 = creat(l2, size2);
    LinkList L3 = (LinkList)malloc(sizeof(Node));
    L3 = L1;
    Merge(L1, L2, L3);
    print(L3);
    return 0;
}

C实现

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next; // 指向结构体 Node 的指针
} Node, *LinkList;

LinkList creat(ElemType e[], int size)
{
    LinkList head = NULL;
    LinkList tail = NULL;

    for (int i = 0; i < size; i++)
    {
        LinkList newNode = (LinkList)malloc(sizeof(Node));
        newNode->data = e[i];
        newNode->next = NULL;

        if (head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

// 释放链表内存
void freeLinkedList(LinkList head)
{
    Node *current = head;
    while (current != NULL)
    {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
}

void print(LinkList head)
{
    Node *current = head;
    while (current != NULL)
    {
        printf("%d ", current->data);
        printf("当前地址：%p ", &current->data);
        printf("指针指向：%p ", current->next);
        current = current->next;
        printf("\n");
    }
}

Status GetElem(LinkList L, int i, ElemType *e)
{
    // L为带头结点的单链表的头指针
    Node *p = L->next;
    int j = 1; // 计数
    while (p && j < i)
    {
        p = p->next; // 查找，直到p指向第i个元素或p为空
        ++j;
    }
    if (!p || j > i)
    {
        return ERROR; // 第i个元素不存在
    }
    *e = p->data;
    return OK;
}

Status insert(LinkList L, int i, ElemType e)
{
    Node *p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j; // 寻找第i-1个结点
    }
    if (!p || j > i - 1)
    {
        return ERROR; // i小于1或者大于表长加1
    }
    LinkList s = (LinkList)malloc(sizeof(Node)); // 生成新结点
    // 插入L中
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
Status delete(LinkList L, int i)
{
    Node *p = L;
    int j = 0;
    while (p->next && j < i - 1)
    {
        p = p->next;
        ++j; // 寻找第i个结点，并令p指向其前驱
    }
    if (!(p->next || j < i - 1))
    {
        return ERROR; // 删除位置不合理
    }
    Node *q = p->next;
    p->next = q->next;
    free(q); // 释放被删除的结点
    return OK;
}

void Merge(LinkList La, LinkList Lb, LinkList Lc)
{
    // 已知La，Lb的元素按值非递减排列
    Node *pa = La->next;
    Node *pb = Lb->next;
    Node *pc = Lc;
    while (pa && pb)
    {
        if (pa->data <= pb->data) // 比大小，然后就是插入操作
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb; // 插入剩余段
    free(Lb);                // 释放Lb的头结点
}

int main()
{
    int elements[] = {10, 20, 30, 40, 50};
    int size = sizeof(elements) / sizeof(elements[0]);
    LinkList myList = creat(elements, size);
    print(myList);

    ElemType e1;
    int i1 = 3;
    Status result = GetElem(myList, i1, &e1);
    if (result == OK)
    {
        printf("第%d个元素为：%d\n", i1, e1);
    }
    else
    {
        printf("第%d个元素不存在\n", i1);
    }

    ElemType e2 = 523;
    int i2 = 2;
    insert(myList, i2, e2);
    print(myList);

    int i3 = 4;
    delete (myList, i3);
    print(myList);

    freeLinkedList(myList);

    int l1[] = {13, 31, 231, 442, 2453};
    int size1 = sizeof(l1) / sizeof(l1[0]);
    LinkList L1 = creat(l1, size1);
    int l2[] = {3, 56, 231, 1234, 5555};
    int size2 = sizeof(l2) / sizeof(l2[0]);
    LinkList L2 = creat(l2, size2);
    LinkList L3 = (LinkList)malloc(sizeof(Node));
    L3 = L1;
    Merge(L1, L2, L3);
    print(L3);

    return 0;
}

栈

顺序栈

PHP实现

<?php
class Stack{
    public $data;
    public $top;
    public function __construct(){
        $this->data = array();
        $this->top = -1;
    }
}
function push(Stack &$stack,$e){
    $stack->top++;
    $stack->data[$stack->top] = $e;
}
function pop(Stack &$stack){
    if($stack->top == -1){
        return FALSE;
    }
    $s = $stack->data[$stack->top];
    $stack->top--;
    return $s;
}

$stack=new Stack();
push($stack,31);
push($stack,'a');
push($stack,77);
push($stack,'fff');
var_dump($stack);

pop($stack);
pop($stack);
var_dump($stack);

定义

typedef struct Stack
{
    ElemType *base;
    ElemType *top;
    int stacksize;
} Stack;

注意这里只定义了一个结构体名称Stack，因此下文要用到对应地址操作的均会是Stack *

初始化空栈

Status Init(Stack *S)
{
    S->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S->base)
    {
        exit(OVERFLOW);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

这个方法的作用大概类似于php中的new Stack

入栈出栈

Status Push(Stack *S, ElemType e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base = (ElemType *)realloc(S->base, (S->stacksize + STACK_INIT_SIZE) * sizeof(ElemType));
        if (!S->base)
        {
            exit(OVERFLOW);
        }
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top) = e;
    S->top++;
    return OK;
}
Status pop(Stack *S)
{
    if (S->top == S->base)
    {
        return ERROR; // 栈空，无法弹出元素
    }
    S->top--;
    return OK;
}

入栈就是先插入数据，然后栈顶指针top向上移动一位，出栈就只需要top向下移动一位

注意入栈时如果栈空间已满，需要再开辟新的内存空间，要用realloc函数

打印

void Print(Stack S)
{
    ElemType *p = S.top - 1; // 从栈顶元素开始遍历
    while (p >= S.base)
    {
        printf("%d ", *p);
        p--;
    }
    printf("\n");
}

从top指针开始向下遍历元素到栈底

最终实现

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;
typedef int ElemType;
typedef struct Stack
{
    ElemType *base;
    ElemType *top;
    int stacksize;
} Stack;

Status Init(Stack *S)
{
    S->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S->base)
    {
        exit(OVERFLOW);
    }
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

Status Push(Stack *S, ElemType e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base = (ElemType *)realloc(S->base, (S->stacksize + STACK_INIT_SIZE) * sizeof(ElemType));
        if (!S->base)
        {
            exit(OVERFLOW);
        }
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top) = e;
    S->top++;
    return OK;
}
Status pop(Stack *S)
{
    if (S->top == S->base)
    {
        return ERROR; // 栈空，无法弹出元素
    }
    S->top--;
    return OK;
}

void Print(Stack S)
{
    ElemType *p = S.top - 1; // 从栈顶元素开始遍历
    while (p >= S.base)
    {
        printf("%d ", *p);
        p--;
    }
    printf("\n");
}

int main()
{
    Stack myStack;

    Init(&myStack);
    Push(&myStack, 13);
    Push(&myStack, 25);
    Push(&myStack, 77);
    Push(&myStack, 128);
    Print(myStack);

    pop(&myStack);
    Print(myStack);
    return 0;
}

链栈

PHP实现

<?php
class LinkStack{
    public $data;
    public $next;
}
function init(){
    return null;    // 初始化一个空栈作为栈底，对应顺序栈里的-1
}
function push(&$stack,$e){
    $s = new LinkStack();
    $s->data = $e;
    $s->next = $stack;
    $stack = $s;
}
function pop(&$stack){
    if($stack == NULL){
        return FALSE;
    }
    $v = $stack->data;
    $stack = $stack->next;
    return $v;
}

$stack = init();
push($stack,12);
push($stack,'arc');
push($stack,444);
push($stack,'?');
var_dump($stack);

定义

typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;

typedef struct LinkStack
{
    Node *top;
} LinkStack;

C实现

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;

typedef struct LinkStack
{
    Node *top;
} LinkStack;

Status Init(LinkStack *S)
{
    S->top = NULL;
    return OK;
}

Status Push(LinkStack *S, ElemType e)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode)
    {
        exit(OVERFLOW);
    }
    newNode->data = e;
    newNode->next = S->top;
    S->top = newNode;
    return OK;
}

void Print(LinkStack S)
{
    Node *p = S.top;
    while (p != NULL)
    {
        printf("%d ", p->data);
        printf("当前地址：%p ", &p->data);
        printf("指针指向：%p ", p->next);
        p = p->next;
        printf("\n");
    }
}

int main()
{
    LinkStack S;
    ElemType e;

    // 初始化链栈
    Init(&S);

    // 入栈操作
    Push(&S, 11);
    Push(&S, 4);
    Push(&S, 514);

    // 打印链栈中的元素
    Print(S);
}

队列

顺序队列

PHP实现

<?php
class Quene{
    public $data;
    public $front;
    public $rear;
}
function init(){
    $quene = new Quene();
    $quene->data = [];
    $quene->front = 0;
    $quene->rear = 0;
    return $quene;
}
function en(&$quene,$e){
    $quene->data[$quene->rear] = $e;
    $quene->rear++;
}
function de(&$quene){
    if($quene->front == $quene->rear){
        return FALSE;
    }
    $e = $quene->data[$quene->front];
    $quene->front++;
    return $e;
}

$quene=new Quene();
en($quene,55);
en($quene,13);
en($quene,4);
en($quene,"a");
var_dump($quene);

de($quene);
de($quene);
de($quene);
var_dump($quene);

C实现

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
} QNode;
typedef struct Quene
{
    QNode *front;
    QNode *rear;
} Quene;

Status Init(Quene *Q)
{
    Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
    if (!Q->front)
    {
        exit(OVERFLOW);
    }
    Q->front->next = NULL;
    return OK;
}

Status En(Quene *Q, ElemType e)
{
    QNode *newNode = (QNode *)malloc(sizeof(QNode));
    if (!newNode)
    {
        exit(OVERFLOW);
    }
    newNode->data = e;
    newNode->next = NULL;
    Q->rear->next = newNode;
    Q->rear = newNode;
    return OK;
}

void Print(Quene Q)
{
    QNode *p = Q.front->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int main()
{
    Quene myQuene;
    ElemType e;

    Init(&myQuene);
    En(&myQuene, 11);
    En(&myQuene, 22);
    En(&myQuene, 33);

    Print(myQuene);
    return 0;
}

循环队列

<?php
define('MAX_QUENE_LENGTH',6);
class QueneLoop{
    public $data;
    public $front;
    public $rear;
}
function init(){
    $quene = new QueneLoop();
    $quene->data = [];
    $quene->front = 0;
    $quene->rear = 0;
    return $quene;
}
function en(QueneLoop &$quene,$e){
    if(($quene->rear+1) % MAX_QUENE_LENGTH == $quene->front){ // 判断队列是否满了
        return FALSE;
    }
    $quene->data[$quene->rear] = $e;
    $quene->rear = ($quene->rear+1) % MAX_QUENE_LENGTH; // 改成循环下标,即满了之后尾指针接下来指向头指针的位置
}

function de(QueneLoop &$quene){
    if($quene->front == $quene->rear){// 判断队列为空
        return FALSE;
    }
    $e = $quene->data[$quene->front];
    $quene->front = ($quene->front+1) % MAX_QUENE_LENGTH;
    return $e;
}

$q=init();
en($q,"bba");
en($q,"lunasama");
en($q,"404");
en($q,"A");
en($q,"123");
en($q,"q");
var_dump($q);

de($q);
de($q);
var_dump($q);

en($q,"new");
var_dump($q);

树

二叉树

PHP实现

<?php
class Btree
{
    public $data;
    public $lChild;
    public $rChild;
}
function creat($arr,$i){    // 使用一个数组来依次表示树的各个结点
    if(!isset($arr[$i])||!$arr[$i]){
        return null;
    }
    $t = new Btree();
    $t->data = $arr[$i];
    $t->lChild = creat($arr, $i*2); // 给左、右孩子赋值时进行了递归操作
    $t->rChild = creat($arr, $i*2+1);
    return $t;
    // 对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲的编号必为i/2
}

$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'];
$tree = creat($treeList,1);
print_r($tree);

function PreOrder($t){
    // 先序遍历:先读取结点的内容，然后再读取这个结点左右孩子结点的内容。通过递归，先按一个方向走到底，当这个结点没有子结点之后，通过递归栈的特性再向上弹出
    if($t){
        echo $t->data.',';
        PreOrder($t->lChild);
        PreOrder($t->rChild);
    }
}
PreOrder($tree);
echo "\n";

function InOrder($t){
    // 中序遍历:遍历完左孩子结点之后再输出当前这个结点的内容
    if ($t) {
        InOrder($t->lChild);
        echo $t->data.',';
        InOrder($t->rChild);
    }
}
InOrder($tree);
echo "\n";

function PostOrder($t){
    // 后序遍历:遍历完一个结点的左右孩子之后最后输出这个结点的内容
    if($t){
        PostOrder($t->lChild);
        PostOrder($t->rChild);
        echo $t->data.',';
    }
}
PostOrder($tree);
echo "\n";
/*
include("顺序队列.php");
$q=init();
function LevelOrder($t){
    // 层序遍历:按照树的层次，一层一层地输出相应的结点信息，用队列而不是栈。遇到一个结点，就把这个结点入队，然后判断它是否有子结点，然后相继把子结点入队。
    global $q;
    if (!$t) {
        return;
    }
    en($q,$t);  // 根结点入队
    $node=$q;
    while($node){
        $node=de($q);   // 每遍历一个结点，就把队首的结点出队
        if($node->lChild){
            en($q,$node->lChild);
        }
        if($node->rChild){
            en($q,$node->rChild);
        }
        echo $node->data.",";
    }
}
LevelOrder($tree);

定义

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lChild, *rChild;
} BiTNode, *BiTree;

定义数据元素，左子树和右子树的指针

注意这里的结构名我用了两种表示方式BiTNode，*BiTree，为了避免混用带来歧义，下文均用*BiTree

C实现

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lChild, *rChild;
} BiTNode, *BiTree;

Status Creat(BiTree *T)
{
    ElemType e;
    scanf("%d", &e);
    if (e == -1)
    { // -1表示空节点
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!(*T))
        {
            exit(OVERFLOW);
        }
        (*T)->data = e;
        Creat(&(*T)->lChild);
        Creat(&(*T)->rChild);
    }
    return OK;
}

void PreOrder(BiTree T)
{
    if (T != NULL)
    {
        printf("%d ", T->data);
        PreOrder(T->lChild);
        PreOrder(T->rChild);
    }
}
void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lChild);
        printf("%d ", T->data);
        InOrder(T->rChild);
    }
}
void PostOrder(BiTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lChild);
        PostOrder(T->rChild);
        printf("%d ", T->data);
    }
}

int main()
{
    BiTree myTree = NULL;

    printf("请输入二叉树的元素值，-1表示空节点：\n");
    Creat(&myTree);
    printf("二叉树创建成功！\n");
    PreOrder(myTree);
    printf("\n");
    InOrder(myTree);
    printf("\n");
    PostOrder(myTree);

    return 0;
}

线索二叉树

PHP实现

<?php
class TBTNode
{
    public $data;
    public $lTag = 0;
    public $rTag = 0;
    public $lChild;
    public $rChild;
}
function create($arr, $i)
{
    if (!isset($arr[$i]) || !$arr[$i]) {
        return null;
    }
    $t = new TBTNode();
    $t->data = $arr[$i];
    $t->lChild = create($arr, $i * 2);
    $t->rChild = create($arr, $i * 2 + 1);
    return $t;
}

$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'I', '', '', '', '', 'H', '', 'J', '', ''];

$tree = create($treeList, 1);
print_r($tree);

function InThread($p, &$pre)
{
    if ($p) {
        // 递归，左子树线索化
        InThread($p->lChild, $pre);

        if (!$p->lChild) {
            // 建立当前结点的前驱线索
            $p->lChild = $pre;
            $p->lTag = 1;
        }
        if ($pre && !$pre->rChild) {
            // 建立当前结点的后继线索
            $pre->rChild = $p;
            $pre->rTag = 1;
        }
        $pre = $p; // $pre 指向当前的 $p ，作为 $p 将要指向的下一个结点的前驱结点指示指针
        $p = $p->rChild; // $p 指向一个新结点，此时 $pre 和 $p 分别指向的结点形成了一个前驱后继对，为下一次线索化做准备

        // 递归，右子树线索化
        InThread($p, $pre);
    }
}

// 创建线索二叉树
function createInThread(TBTNode $root)
{
    $pre = null; // 前驱结点指针
    if($root){
        InThread($root, $pre);
        $pre->rChild = null; // 非空二叉树，线索化
        $pre->rTag = 1; // 后处理中序最后一个结点
    }
}

createInThread($tree);
print_r($tree);

C实现

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;
typedef enum PointerTag
{
    Link,
    Thread
} PointerTag; // Link==0;指针,Thread==1;线索
typedef struct Node
{
    ElemType data;
    struct Node *lChild, *rChild;
    PointerTag LTag, RTag;
} Node, *BiThrTree;

Status Creat(BiThrTree *T)
{
    ElemType e;
    scanf("%d", &e);
    if (e == 0)
    {
        *T = NULL;
    }
    else
    {
        *T = (BiThrTree)malloc(sizeof(Node));
        if (!*T)
        {
            exit(OVERFLOW);
        }
        (*T)->data = e;
        Creat(&((*T)->lChild));
        Creat(&((*T)->rChild));
    }
    return TRUE;
}

Status InOrderThreading(BiThrTree T, BiThrTree *pre)
{
    if (T)
    {
        // 递归线索化左子树
        InOrderThreading(T->lChild, pre);

        // 线索化当前节点
        if (!T->lChild)
        {
            T->LTag = Thread;
            T->lChild = *pre;
        }
        if (*pre && !(*pre)->rChild)
        {
            (*pre)->RTag = Thread;
            (*pre)->rChild = T;
        }
        *pre = T;

        // 递归线索化右子树
        InOrderThreading(T->rChild, pre);
    }
    return TRUE;
}

Status InOrderTraverse(BiThrTree T)
{
    BiThrTree p = T;
    while (p)
    {
        // 找到中序遍历的起始节点
        while (p->LTag == Link)
        {
            p = p->lChild;
        }

        // 输出当前节点的值
        printf("%d ", p->data);

        // 遍历下一个节点
        while (p->RTag == Thread && p->rChild)
        {
            p = p->rChild;
            printf("%d ", p->data);
        }
        p = p->rChild;
    }

    return TRUE;
}

int main()
{
    BiThrTree T = NULL;
    printf("请输入线索二叉树的节点值（先序次序输入，输入 0 表示空节点）：\n");
    Creat(&T);
    // 进行线索化
    BiThrTree pre = NULL; // 用于记录中序遍历的前驱节点
    InOrderThreading(T, &pre);

    // 进行中序遍历
    printf("中序遍历结果：");
    InOrderTraverse(T);
    printf("\n");
    return 0;
}

哈夫曼树

剩余部分

由于没有PHP实现了，请移步我的另几篇博客

目录

LOADING

PHP&C语言数据结构

前言

链表

PHP实现

打印

尾插法创建链表

获取元素

指定位置插入

指定位置删除

将两表并为一表

C实现

栈

顺序栈

PHP实现

定义

初始化空栈

入栈出栈

打印

最终实现

链栈

PHP实现

定义

C实现

队列

顺序队列

PHP实现

C实现

循环队列

树

二叉树

PHP实现

定义

C实现

线索二叉树

PHP实现

C实现

哈夫曼树

剩余部分