二叉树的顺序存储与链式存储（C++）

//二叉树顺序存储方式：静态数组。 #define MAXSIZE 100 struct TreeNode { //ElemType value; int value; bool isEmpty;//表示结点是否为空 }; //定义树 TreeNode t[MAXSIZE]; //初始化 void InitTreeNode(TreeNode T[]) { for(int i=0;i<MAXSIZE;i++)//TreeNode T[MAXSIZE];i<T.length; { T[i].isEmpty=true; } } /* i的左孩子：t[2i] i的右孩子：2i+1 i的父结点：i/2（向左取整，int） i所在的层次：log（n+1）（2为底，向上取整）或logn+1（向上取整） i有左孩子？2i≤n？ i有右孩子？2i+1≤n？ i是否是叶子/分支结点？i>n/2？（n/2向下取整，int） */ //链式存储 //数据元素 struct ELemType { int value; }; typedef struct BTNode { ELemType data; struct BTNode *lchild,*rcild; //struct BTNode *parent;父结点指针，三叉链表 //因为要寻找父结点时需要地毯式搜索，添加父结点指针更容易找父结点 }BTNode,*BTree; //定义一颗空树,即一个BTNode类型的空指针 BTree root=NULL; //插入根结点 root=(BTree)malloc(sizeof(BTNode)); root->data={1}; root->lchild=NULL; root->rchild=NULL; //插入新结点 BTNode *p=(BTree)malloc(sizeof(BTNode)); p->data={2}; p->lchild=NULL; p->rchild=NULL; root->lchild=p;//作为左孩子 //n个结点的二叉链表共有2n个指针，n-1结点有指针，n+1个空链域