本文目录
- 如何对二叉树进行顺序存储
- 二叉树的顺序存储结构数据A B C D E
- 二叉链表存储二叉树的先序遍历算法
- 建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，怎么做
- 二叉树_顺序存储
- 什么是二叉树的顺序存储
- 完全二叉树为什么最适合顺序存储结构
如何对二叉树进行顺序存储
二叉树按照层序遍历，依次编号，按照编号的顺序，存储在连续存储单元的方式就是二叉树的顺序存储。
如果二叉树不是满二叉树，则只存储有内容的节点，缺失的结点在存储的过程中，所对应的位置不存储任何东西，即是空的。
对于题中所给的存储结构，构造一个满二叉树，结点为空，再按照层序遍历，依次编号，在相应的结点填上数据，没有数据的则为空结点。
最后删除所有的空结点，即为所对应的二叉树
扩展资料：
二叉树除了按顺序存储的存储方式，还有另外一种——链式存储方式，即用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
其中，data存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表。如下图所示：
二叉树的顺序存储结构数据A B C D E
二叉树结构链式图： A / \ BC/\ DE前序遍历：（根，左，右）：A -》B -》 D -》 E -》 C中序遍历：（左，根，右）：D -》 B -》 E -》 A -》 C后序遍历：（左，右，根）： D -》 E -》 B -》 C -》 A前序中序后序遍历，主要是以根节点做为参考点，进行遍历。（根，左，右）遍历顺序中‘根’在第一个，所以叫前序遍历。（左，根，右） 遍历顺序中‘根’在第二个，所以叫中序遍历。（左，右，根） 遍历顺序中‘根’在第三个，所以叫后序遍历。
二叉链表存储二叉树的先序遍历算法
二叉链表存储二叉树的先序遍历算法，通常采用递归的算法实现。首先访问二叉树的根节点，然后递归遍历它的左子树，最后，递归遍历他的右子树。
建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，怎么做
建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，程序操作如下:
#include "stdio.h"#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{char data;struct bitree *lchild,*rchild;}bitree; //二叉树结点定义typedef struct {bitree **base;
bitree **top;int stacksize;}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈int initstack(sqstack *s)
{s-》base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间if(!s-》base) exit(1); //抛出异常s-》top=s-》base; //栈顶=栈尾 表示栈空
s-》stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小return 1;}//进栈int push(sqstack *s,bitree *e) {if(s-》top-s-》base》=s-》stacksize) //如果栈满 追加开辟空间
{s-》base=(bitree *)realloc (s-》base,(s-》stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s-》base) exit(1); //抛出异常s-》top=s-》base+s-》stacksize; //感觉这一句没用s-》stacksize+=STACKINCREMENT;}*(s-》top)=e;s-》top++; //进栈 栈顶后移
return 1;}//出栈int pop(sqstack *s,bitree **e)
{if(s-》top==s-》base) return 0; //栈空 返回0--s-》top;*e=*(s-》top); //栈顶前移 取出栈顶元素给ereturn 1;}
//取栈顶int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个{if(s-》top==s-》base) return 0; //所以 s-》top-1*e=*(s-》top-1);
return 1;}/*------------------------非递归-----先序建立二叉树----------------------------------*/bitree *createprebitree()
{sqstack m;initstack(&m);while(h||m.base!=m.top){if(h) {push(&m,h);printf("%c",h-》data);h=h-》lchild;}else{pop(&m,&h);
h=h-》rchild;}}}/*------------------------非递归-----中序输出二叉树----------------------------*/void inordertraverse(bitree *h){sqstack m;initstack(&m);while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h-》lchild;}else {pop(&m,&h);printf("%c",h-》data);h=h-》rchild;}}}/*---------------------非递归----后序遍历二叉树----------------------------------*/void postordertraverse(bitree *h){sqstack m;initstack(&m);while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h-》lchild;}else {bitree *r; //使用r结点表示访问了右子树 代替标志域gettop(&m,&h);if(h-》rchild&&h-》rchild!=r)
{h=h-》rchild;push(&m,h);h=h-》lchild;}else{pop(&m,&h);
printf("%c",h-》data);r=h;h=NULL;}}}
二叉树_顺序存储
满二叉树 (Full Binary Tree) 所有分支结点都有存在左子树和右子树，并且所有叶子结点都在同一层上。 完全二叉树 (Complete Binary Tree) 如果一棵具有n个结点的二叉树与满二叉树的前n个结点的结构相同，则称这棵二叉树为完全二叉树。
重要性质 ： 对于一棵有n个结点的 完全二叉树 的结点按照从上至下和从左至右的顺序对所有结点从零开始到 n-1 进行顺序编号，则对于序号为i的结点(0≤i≤n),有： (1)如果 i=0，则结点i是二叉树的根；如果i》0，则其 双亲 是结点 (i-1)/2 （整除）。 (2)如果2i+1≥n，则结点i无左孩子；否则，其 左孩子 是结点 2i+1 。 (3)如果2i＋2≥n，则结点i无右孩子；否则，其 右孩子 是结点 2i＋2 。
根据上面两点，得到二叉树顺序存储的实现：
定义：
获取双亲节点下标：
左子节点下标：
右子节点下标：
主函数测试：
总结： 1、对于完全二叉树或接近于完全的二叉树，用顺序存储可以省空间简化操作；否则，都不适宜用顺序存储。 2、顺序存储结构通病：必须预先给出数组的存储空间大小MaxSize。
什么是二叉树的顺序存储
二叉树的顺序存储结构，此结构是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于近似满二叉树。在一棵具有n个结点的近似满二叉树中，我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如图6所示。其中每个结点的编号就作为结点。楼主看看下面的图希望对你有所帮助哟，好的话记得采纳哟！
完全二叉树为什么最适合顺序存储结构
顺序存储充分利用满二叉树的特性，即每层的节点数分别为1、2、4、8等等2i+1，一个深度为i的二叉树最多只能包含2i-1个节点，因此只要定义一个长度为2i-1的数组即可存储这颗二叉树。
对于普通的不是满二叉树的，那些空出来的节点对应的数组元素留空即可，因此顺序存储会造成一定的空间浪费。如果是完全二叉树，就不会有空间浪费的情况；若是只有右子树，那么会造成相当大的浪费。
二叉树算法思路：
1、如果树为空，则直接返回错。
2、如果树不为空：层序遍历二叉树。
3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。
4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。
5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
