#define nodeNum 50
typedef struct PNode{
　　int _data;　　      //树中结点的数据类型
　　int _parent;　　　　 //结点的父结点在数组中的位置下标
}PNode;
​
typedef struct 
{
　　PNode _node[nodeNum];　　//存放树中所有结点
　　int _r, _n;　　         //根的位置下标和结点数
}Tree;

#define nodeNum 50
//孩子表示法
typedef struct CNode{
　　int _child;　　//链表中每个结点存储的是数据在数组中存储的位置下标
　　struct CNode *_next;
}*Child;
typedef struct {
　　int _data;　　//结点的数据
　　Child _childptr;　　//孩子链表的头指针（指向其父节点）
}CBox;
typedef struct{
　　CBox nodes[nodeNum];　　//存储结点的数组
　　int n, r;　　//结点数量和根的位置
}CTree;

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};

#include <stdio.h>
#include<stdlib.h>
​
//拓展二叉树的先序建立
//仅由先序序列无法确定一棵二叉树，但是我们可以由拓展二叉树的先序序列可以唯一确定一棵二叉树。
//拓展二叉树：将原二叉树每个结点的空指针都引出一个“虚结点”，令其值为 ‘#’,表示为空结点，这样处理的二叉树称为原二叉树的拓展二叉树。
​
typedef struct Node{
    int data;
    struct Node *LChildren , *RChildren;
}Node,*LinkNode;
​
typedef struct Tree{
    LinkNode root;  //根节点 
    int n;          //节点数 
}Tree;
​
extern int index=0;     //已经取到的数组下标
​
//根据序列生成树 
void CreateTree(char nodes[],Node *node){
    char ch = nodes[index++];
    if(ch=='#') 
        node=NULL;
    else{
        if(node) {  
            node->data=ch-'0';
            Node *lch;
            lch=(Node*)malloc(sizeof(Node));
            node->LChildren = lch;
            CreateTree(nodes,lch);
            Node *rch;
            rch=(Node*)malloc(sizeof(Node));
            node->RChildren = rch;
            CreateTree(nodes,rch);
        }
    }
}
​
int main(){
    char nodes[] = {'1','2','4','#','#','#','3','#','5','#','#'};
    Node *root;     //根节点 
    root=(Node*)malloc(sizeof(Node));   
    Tree *tree;
    tree = (Tree*)malloc(sizeof(tree));
    tree->n=0;
    tree->root = root;
    CreateTree(nodes,root);
    printf("%d",tree->root->RChildren->RChildren->data);
}

/*--------------------------先序和中序构造二叉树--------------------------*/
/*  a是先序序列
    b是中序序列 
    i是先序序列首字符在a[]中的位置
    j是中序序列首字符在b[]中的位置
    len是子树的字符长度
*/
Node* FMCreatTree(char a[], char b[], int i,int j, int len)
{
    Node *root; //二叉树的根结点
    root = (Node*)malloc(sizeof(Node));
    if (len > 0){
        root->data = a[i];
        char *p = b;
        for (p = b; p != NULL; p++) //在b中找到a[i]
        {
            if (*p == a[i]) break;
        }
        int m = p - b;  //计算该结点在b中的下标
        root->LChildren = FMCreatTree(a, b, i + 1, j, m - j);   //左孩子
        root->RChildren = FMCreatTree(a, b, i + (m - j) + 1, m + 1, len - 1 - (m - j)); //右孩子
        return root;    //返回二叉树的根
    }
}

/*--------------------------后序和中序构造二叉树--------------------------*/
//b是中序 
//c是后续
Node*  EMCreateTree(char b[],char c[],int i,int j,int len){
    Node *root;     //根节点
    root = (Node*)malloc(sizeof(Node));
    if(len>0){
        root->data = c[j+len-1];
        char *p = b;
        for(;p!=NULL;p++){
            if(*p == c[j+len-1]){
                break;
            }
        }
        int m = p-b;    //获取根节点在b中的下标
        root->LChildren = EMCreateTree(b,c,i,j,m-i);
        root->RChildren = EMCreateTree(b,c,m+1,m+j-i,len-(m-i)-1);
        return root;
    } 
} 

/*--------------------------先序遍历二叉树--------------------------*/
//递归 
void Prerequisite(Node *root){
    if(root != NULL){
        printf("%c ",root->data);
        Prerequisite(root->LChildren);
        Prerequisite(root->RChildren);
    }
} 
//非递归
void N_Prerequisite(Node *root){
    Node* stack[10];        //节点指针数组 
    int top=0;
    stack[0] = root;
    while(top>-1){
        Node *temp = stack[top--];
        printf("%c ",temp->data);
        if(temp->RChildren != NULL){
            stack[++top] = temp->RChildren;
        }
        if(temp->LChildren != NULL){
            stack[++top] = temp->LChildren;
        }
    }
}

/*--------------------------中序遍历二叉树--------------------------*/
//递归 
void Mediumorder(Node *root){
    if(root != NULL){
        Mediumorder(root->LChildren);
        printf("%c ",root->data);
        Mediumorder(root->RChildren);
    }
} 
//非递归 
void N_Mediumorder(Node *root){ 
    Node* stack[10];
    int top=-1;
    Node *P = root;
    while(P||top>-1){
        while(P){
            stack[++top] = P;
            P = P->LChildren;
        }
        if(top>-1){
            P = stack[top--];
            printf("%c ",P->data);
            P = P->RChildren;
        }
    }
} 

/*--------------------------后序遍历二叉树--------------------------*/
//递归
void Postorder(Node *root){
    if(root != NULL){
        Postorder(root->LChildren);
        Postorder(root->RChildren);
        printf("%c ",root->data);
    }
} 
//非递归
void N_Postorder(Node *root){
    Node* stack[10];
    int top=-1;
    Node *P = root;
    Node *r;                // r 为辅助节点，用于判断当节点返回时，是从哪个方向返回到父节点的。
    
    while (P || top>-1) {
        // 先从左走到底
        if (P) {
            stack[++top] = P;
            P = P->LChildren;
        } else {
            P = stack[top--];
            // 若右孩子还未遍历，遍历右孩子
            if (P->RChildren && P->RChildren != r) {
                top++;          //如果该节点还有右孩子未访问，则其还未访问，所以暂不出栈，top加回来 
                P = P->RChildren;
            } else {
                printf("%c ",P->data);
                r = P;
                P = NULL;
            }
        }
    }
}

/*--------------------------层次遍历二叉树--------------------------*/
void level(Node *root){
    Node* queue[10];
    int head=-1, end=0;
    queue[0] = root;
    Node *P;
    while(end > head){
        P = queue[++head];
        printf("%c ",P->data);
        if(P->LChildren != NULL)
            queue[++end] = P->LChildren;
        if(P->RChildren != NULL)
            queue[++end] = P->RChildren;
    }
}