完全二叉树 顺序储存 实现对其的先序遍历
则该二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，后序遍历序列为DEBFCA。
先序遍历二叉树规则：根-左-右
1、访问根结点；
2、先序遍历左子树；
3、先序遍历右子树。
中序遍历二叉树规则：左-根-右
1、先中序遍历左子树；
2、再访问根节点；
3、最后访问中序遍历右子树。
后序遍历二叉树规则：左-右-根
1、后序遍历左子树；
2、后序遍历右子树；
3、访问根结点。
扩展资料
完全二叉树的特点
叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
判断一棵树是否是完全二叉树的思路
1>如果树为空，则直接返回错；
2>如果树不为空：层序遍历二叉树；
2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
#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); //栈顶前移 取出栈顶元素给e
return 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()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='
') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='
') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{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;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('
');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('
');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('
');
}
else printf("空二叉树
");
}
这是先序递归和非递归建立二叉树 和 先、中、后 的遍历输出
假设完全二叉树的顺序储存序列是10,15,20,25,30,50,定义数组:
int BTree[]={10,15,20,25,30,50};
完全二叉树的树形如下:
10
/ \
15 20
/ \ /
25 30 50
相应的顺序号(也就是数组的下标)是:
[0]
/ \
[1] [2]
/ \ /
[3] [4] [5]
[0]=10,[1]=15,[2]=20,[3]=25,[4]=30,[5]=50
根节点10的下标是n=0,其左节点下标是2*n+1=2*0+1=1,左节点就是[1]=15,
右节点下标是2*n+2=2*0+2=2,右节点就是[2]=20
节点15的下标是n=1,其左节点下标是2*n+1=2*1+1=3,左节点就是[3]=25,
右节点下标是2*n+2=2*1+2=4,右节点就是[4]=30
节点20的下标是n=2,其左节点下标是2*n+1=2*2+1=5,左节点就是[5]=50,
没有右节点.
先序遍历就是遍历数组的下标.
注:如果将根节点10的下标定为1,也就是[1]=10,那么,其它节点的下标也相应加1.
根节点10的下标是n=1,其左节点下标是2*n=2*1=2,左节点就是[2]=15,
右节点下标是2*n+1=2*1+1=3,右节点就是[3]=20
// 测试结果:
// 输入完全二叉树的总节点数: 6
// 输入6个节点的数值: 10 15 20 25 30 50
// 先序遍历序列(递归法): 10 15 25 30 20 50
// 先序遍历序列(非递归): 10 15 25 30 20 50
#include <stdio.h>
#define MAXSIZE 100
void preOrderByStack(int BT[],int i,int n) //先序遍历(非递归)
{
int oneStack[MAXSIZE]; //栈
int top=0; //栈顶,从top=1开始存入数据
int left,right;
if(i>=n)
{
return;
}
top++;
oneStack[top]=i; //根节点的下标入栈
while(top!=0)
{
i=oneStack[top]; //出栈
top--;
printf("%d ",BT[i]);
left=i*2+1;
right=i*2+2;
if(right<n)
{
top++;
oneStack[top]=right; //右节点的下标入栈
}
if(left<n)
{
top++;
oneStack[top]=left; //左节点的下标入栈
}
}
}
void preOrder(int BT[],int i,int n) //先序遍历(递归法)
{
if(i<n)
{
printf("%d ",BT[i]);
preOrder(BT,2*i+1,n); //左节点
preOrder(BT,2*i+2,n); //右节点
}
}
int main()
{
int BTree[MAXSIZE];
int n;
int i;
printf("输入完全二叉树的总节点数: ");
scanf("%d",&n);
printf("输入%d个节点的数值: ",n);
for(i=0;i<n;i++)
{
scanf("%d",&BTree[i]);
}
printf("先序遍历序列(递归法): ");
preOrder(BTree,0,n);
printf("
");
printf("先序遍历序列(非递归): ");
preOrderByStack(BTree,0,n);
printf("
");
return 0;
}
陀泉氯化： 这棵树根节点是tree[1],顺序存储.最后一个叶子节点是tree[maxnode]; void mid(int treenode) { if (treenode > maxnode) return; mid(treenode * 2); visit(treenode) /*访问treenode节点*/ mid(treenode * 2 + 1); }
津南区15787071235： 已知一颗具有n个结点的完全二叉树以向量作为存储结构,设计一个非递归算法,实现对该树的先序遍历. - ？
陀泉氯化： #include#define array_max 12 int main() { int tree[array_max]; for(int i = 0;itree[i] = i+1; int flag = 0;//记录当前叶子的遍历位置,0 刚遍历到这个叶子,1 已经遍历完成该叶子的左儿子,2 已经遍历完成该叶子的右儿子 int count = 1;//假设tree不为...
津南区15787071235： 某完全二叉树采用顺序存储结构,结点数据的存放顺序依次为ABCDEFGH,该完全二叉树的后序遍历序列为? - ？
陀泉氯化： ABCDEFGH是前序排列还仅仅指的是存放顺序,前者的话后续排列是ECDBGHFA,后者的话HDEBFCGA. 如果是按顺序存储的话,那么直接根据后序排列的左右根判别. 主要要注意每一棵小子树都要采用这样的判别是递归的,就本题后序...
津南区15787071235： 一棵具有n个结点的完全二叉树以数组存储,试写一个非递归算法实现对该树的前序遍历 - ？
陀泉氯化： #include ＂stdafx.h＂#include <stack>#include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { //构建完全二叉树,层数是三,7个节点 int a[7] = {0,1,2,3,4,5,6}; //前序遍历,先访问左儿子,再访问自己,再访问右儿子 //左...
津南区15787071235： 一棵完全二叉树以顺序方式存储,设计一个递归算法,对该完全二叉树进行中序遍历. - ？
陀泉氯化： 展开全部 这棵树根节点是tree[1],顺序存储.最后一个叶子节点是tree[maxnode];void mid(int treenode) { if (treenode > maxnode) return;mid(treenode * 2);visit(treenode) /*访问treenode节点*/mid(treenode * 2 + 1); }
津南区15787071235： 有关数据结构的:设一棵完全二叉树采用顺序存储结构存储在B[1..n]中,设计一算法对完全二叉树进行 - ？
陀泉氯化： 可以这样存:B[1]存根节点 然后对于已存的点B[n],其左子结点的内容存在B[2*n],右子节点存在B[2*n+1] 对于完全二叉树,这种方法空间利用率还是很高的
津南区15787071235： c语言, 一棵具有n个结点的完全二叉树以数组存储,试写一个非递归 算法实现对 该树的前序遍历. - ？
陀泉氯化： 以向量为存储结构的完全二叉树,其存储在向量中的结点其实是按层次遍历的次序存放的,可以根据课本第74页的内容设计出算法: typedef char DataType;//设结点数据类型为char #define M 100//设结点数不超过100 typedef DataType BinTree[...
津南区15787071235： 已知a是一棵顺序存储的完全二叉树,如何求出a和a的最近的共同祖先 - ？
陀泉氯化： (a+1)(a+2)(a+3)(a+4)+M = [(a+1)(a+4)]*[(a+2)(a+3)]+M =(a²+5a+4)(a²+5a+6)+M =[(a²+5a+5)-1]*[(a²+5a+5)+1]+M =(a²+5a+5)²-1+M 且题目要求是完全平方式, 所以M-1=0 M=1
津南区15787071235： java编程把一个顺序存在一维数组中的完全二叉树按先序遍历访问 - ？
陀泉氯化： 根据数组存放二叉树的逻辑,写代码反过来取出来就是了.
津南区15787071235： 二叉树相关知识 - ？
陀泉氯化： 二叉树 (binary tree) 是另一种树型结构,它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 ),并且,二叉树的子树有左右之分,其次序不能任意颠倒 . 二叉树是一种数据结构 :Binary_tree=(D,R)其中: D是具有...
