二叉树的存储方式

1）树的顺序存储

#include <stdio.h>
#define MaxSize 100
struct TreeNode{
    int value;
    bool isEmpty;
};

void InitTreeNode(TreeNode t[MaxSize])
{
    for(int i=0;i<MaxSize;i++){
        t[i].isEmpty=true;
    }
}
void main(){
    TreeNode t[MaxSize];
    InitTreeNode(t);
}

2）树的链式存储

typedef struct BiTreeNode{
    int value;
    BiTreeNode * rchild,* lchild;
}BiTreeNode,* BiTree;

//插入根节点
    BiTree root=(BiTree)malloc(sizeof(BiTreeNode));
    root->value=1;
    root->lchild=NULL;
    root->rchild=NULL;
    return true;

//插入新节点
    BiTreeNode * p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    p->value=2;
    p->lchild=NULL;
    p->rchild=NULL;
    root->lchild=p;
    return true;

//先序遍历
void PreOrder(BiTree T)
{
    if(T!=NULL)
    {
        Visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//求树的深度：后序的应用
int TreeDepth(BiTree T)
{
    if(T==NULL) return 0;
    int l=TreeDepth(T->lchild);
    int r=TreeDepth(T->rchild);
    return l>r?l+1:r+1;
}

//中序遍历（非递归实现）
bool InOrderTraverse(BiTree T)
{
    BiTreeNode * p=T; InitStack(S); //初始化一个栈
    while(p||!ISEmpty(S))
    {
        if(p){push(S,p);p=p->lchild;}
        else
        {
            pop(S,q);
            printf("%d,",q->data);
            p=q->rchild;
        }
    }
    return true;
}