ae模板网站推荐,北京中国建设部网站首页,the ken wordpress,网页版梦幻西游能交易吗目录 3.编写后序遍历二叉树的非递归算法 4.试给出二叉树的自下而上、自右到左的层次遍历算法 #xff08;有图解代码详解#xff09;c语言代码实现
5.假设二叉树采用二叉链表存储结构#xff0c;设计一个非递归算法求二叉树的高度。
编辑 6.设一棵二叉树中各结点的值互不…目录 3.编写后序遍历二叉树的非递归算法 4.试给出二叉树的自下而上、自右到左的层次遍历算法 有图解代码详解c语言代码实现
5.假设二叉树采用二叉链表存储结构设计一个非递归算法求二叉树的高度。
编辑 6.设一棵二叉树中各结点的值互不相同其先序遍历序列和中序遍历序列分别存于两个一维数组A[l...n]和 B[l...n]中试编写算法建立该二叉树的二叉链表。 7.二叉树按二叉链表形式存储写一个判别给定二叉树是否是完全二叉树的算法 3.编写后序遍历二叉树的非递归算法 本题代码如下
void postorder(tree* t)
{struct treenode* stack[100];//初始化结构体数组int top -1;//让栈顶指向-1treenode* p *t;while (p || top ! -1)//p不为空并且栈不为空{if (p){top;//p不为空将p压入栈中stack[top] p;p p-lchild;//一直向左下遍历}else{p stack[top];//p等于栈顶元素if (p-rchild p-rchild-tag 0)//右孩子不为空且未被访问过p p-rchild;else//否则弹出结点并访问{p stack[top];top--;printf(%c, p-data);p-tag 1;//标记p被访问过p NULL;}}}
}
完整测试代码
#includestdio.h
#includestdlib.h
typedef struct treenode
{char data;struct treenode* lchild, * rchild;int tag;
}treenode,*tree;
void buildtree(tree *t)
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;(*t)-tag 0;(*t)-lchild NULL;(*t)-rchild NULL;buildtree((*t)-lchild);buildtree((*t)-rchild);}
}
void postorder(tree* t)
{struct treenode* stack[100];//初始化结构体数组int top -1;//让栈顶指向-1treenode* p *t;while (p || top ! -1)//p不为空并且栈不为空{if (p){top;//p不为空将p压入栈中stack[top] p;p p-lchild;//一直向左下遍历}else{p stack[top];//p等于栈顶元素if (p-rchild p-rchild-tag 0)//右孩子不为空且未被访问过p p-rchild;else//否则弹出结点并访问{p stack[top];top--;printf(%c, p-data);p-tag 1;//标记p被访问过p NULL;}}}
}
int main()
{tree t;buildtree(t);postorder(t);return 0;
}
用ABD##E##CF##G##
/* A B C D E F G */ 4.试给出二叉树的自下而上、自右到左的层次遍历算法 有图解代码详解c语言代码实现 本题我们采用让结点出队时将结点入栈同时访问该结点是否有左右孩子如果有的话就让左右孩子进队。最后所有结点都入栈了再从栈顶开始依次访问就可以得到结果
看下面的图解
A先入队然后出队就压入栈中 访问A结点有左右孩子左右孩子入队 B结点出队并入栈并访问B结点B结点有左右孩子左右孩子进队 C结点出队并入栈同时访问C结点C结点有左右孩子左右孩子进队 D结点出队并入栈同时访问D结点D结点没有左右孩子 EFG依次出队进栈与D的步骤相同
最后我们看一下栈中的元素 我们让栈中元素依次出栈就能得到我们想要的结果 下面我们来看一下代码该如何实现
void level(tree* t)
{treenode* q[10];treenode* s[10];int top -1;int f -1;int r -1;treenode* p;q[r] *t;//根结点进队while (f r){p q[f];//结点出队s[top] p;//结点进栈if (p-lchild)//出队结点是否有左孩子q[r] p-lchild;//有左孩子左孩子进栈if (p-rchild)//出队结点是否有右孩子q[r] p-rchild;//有右孩子右孩子进栈}while (top ! -1)//依次输出栈中元素{printf(%c , s[top--]-data);}
}
完整测试代码如下
#includestdio.h
#includestdlib.h
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
}treenode,*tree;
void buildtree(tree* t)
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;(*t)-lchild NULL;(*t)-rchild NULL;buildtree((*t)-lchild);buildtree((*t)-rchild);}
}
void level(tree* t)
{treenode* q[10];treenode* s[10];int top -1;int f -1;int r -1;treenode* p;q[r] *t;while (f r){p q[f];s[top] p;if (p-lchild)q[r] p-lchild;if (p-rchild)q[r] p-rchild;}while (top ! -1){printf(%c , s[top--]-data);}
}
int main()
{tree t;buildtree(t);level(t);return 0;
}
用ABD##E##CF##G##测试 5.假设二叉树采用二叉链表存储结构设计一个非递归算法求二叉树的高度。 采用层次遍历的算法设置变量 ans记录当前结点所在的层数设置变量 l 指向当前层的最右结点每次层次遍历出队时与 l指针比较若两者相等则层数加 1并让 l指向下一层的最右结点直到遍历完成。ans的值即为二又树的高度。
本题代码如下
int deep(tree* t)//求树的深度
{if ((*t) NULL)return 0; treenode* q[10];int f -1, r -1;//f头结点r尾结点int l 0, ans 0;//l每次指向每层的最后一个结点q[r] *t;treenode* p;while (f r){p q[f];//队列元素出队正在访问的结点if (p-lchild)q[r] p-lchild;//左孩子入队if (p-rchild)q[r] p-rchild;//右孩子入队if (f l)//处理该层的最右结点{ans;//层数1l r;//让l指向下一层}}return ans;
}
完整测试代码
#includestdio.h
#includestdlib.h
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
}treenode, * tree;
void buildtree(tree* t)//建树
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;(*t)-lchild NULL;(*t)-rchild NULL;buildtree((*t)-lchild);buildtree((*t)-rchild);}
}
int deep(tree* t)//求树的深度
{if ((*t) NULL)return 0; treenode* q[10];int f -1, r -1;//f头结点r尾结点int l 0, ans 0;//l每次指向每层的最后一个结点q[r] *t;treenode* p;while (f r){p q[f];//队列元素出队正在访问的结点if (p-lchild)q[r] p-lchild;//左孩子入队if (p-rchild)q[r] p-rchild;//右孩子入队if (f l)//处理该层的最右结点{ans;//层数1l r;//让l指向下一层}}return ans;
}
int main()
{tree t;buildtree(t);printf(树的高度为%d\n, deep(t)); return 0;
}
/* AB CD E F */
//ABD##E##CF### 6.设一棵二叉树中各结点的值互不相同其先序遍历序列和中序遍历序列分别存于两个一维数组A[l...n]和 B[l...n]中试编写算法建立该二叉树的二叉链表。 本题代码如下
tree build(char a[], char b[], int s, int e)
{if (s e){treenode* root (treenode*)malloc(sizeof(treenode));root-data a[pos];//将子树的根节点赋值给rootint i;for (i s; i e; i)//在b数组中找到根节点if (b[i] root-data)break;pos;root-lchild build(a, b, s, i - 1);//建立左子树root-rchild build(a, b, i 1, e);//建立右子树return root;}return NULL;
}
完整测试代码
#includestdio.h
typedef struct treenode {char data;struct treenode* lchild, * rchild;
}treenode,*tree;
int pos 0;//全局变量pos
tree build(char a[], char b[], int s, int e)
{if (s e){treenode* root (treenode*)malloc(sizeof(treenode));root-data a[pos];//将子树的根节点赋值给rootint i;for (i s; i e; i)//在b数组中找到根节点if (b[i] root-data)break;pos;root-lchild build(a, b, s, i - 1);//建立左子树root-rchild build(a, b, i 1, e);//建立右子树return root;}return NULL;
}
void disp(tree t)
{if (t){disp(t-lchild);disp(t-rchild);printf(%c, t-data);}
}
int main(){char a[] {A,B,D,E,C,F};//先序char b[] {D,B,E,A,F,C };//中序tree root build(a, b, 0, 5);printf(后序序列为:);disp(root);return 0;
} 7.二叉树按二叉链表形式存储写一个判别给定二叉树是否是完全二叉树的算法 采用层次遍历算法将所有结点加入队列(包括空结点)。
如果没有左孩子就看有没有右孩子如果有右孩子那么不为完全二叉树。
如果有左孩子且之前不存在缺孩子的结点左孩子进队如果有右孩子右孩子也进队否则就是缺孩子了。之前存在缺孩子的那么就不是完全二叉树。
有两种代码的写法
本题代码如下
int isok(tree* t)//判断完全二叉树
{squene q;q.f q.r q.tag 0;int flag false; // 标志是否遇到了空节点if (*t NULL)return true; // 空树也是完全二叉树enquene(q, *t);treenode* p;while (!isempty(q)){dequene(q, p);if (p-lchild){if (flag) // 如果之前遇到了空节点说明不是完全二叉树return false;enquene(q, p-lchild);}else{flag true;}if (p-rchild){if (flag) // 如果之前遇到了空节点说明不是完全二叉树return false;enquene(q, p-rchild);}else{flag true;}}return true;
}
完整测试代码
#include stdio.h
#include stdlib.h
#define Max 15
#define true 1
#define false 0
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
} treenode, * tree;
void buildtree(tree* t)
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;buildtree((*t)-lchild);buildtree((*t)-rchild);}
}
typedef struct squene
{struct treenode* data[Max];int f, r, tag;
} squene;
int isempty(squene* q)//判断队空
{if (q-f q-r q-tag 0)return true;return false;
}
int isfull(squene* q)//判断队满
{if (q-f q-r q-tag 1)return true;return false;
}
int enquene(squene* q, treenode* p)//进队操作
{if (isfull(q))return false;q-data[q-r] p;q-r (q-r 1) % Max;q-tag 1;return true;
}
int dequene(squene* q, treenode** p)//出队操作
{if (isempty(q))return false;*p q-data[q-f];q-f (q-f 1) % Max;q-tag 0;return true;
}
int isok(tree* t)//判断完全二叉树
{squene q;q.f q.r q.tag 0;int flag false; // 标志是否遇到了空节点if (*t NULL)return true; // 空树也是完全二叉树enquene(q, *t);treenode* p;while (!isempty(q)){dequene(q, p);if (p-lchild){if (flag) // 如果之前遇到了空节点说明不是完全二叉树return false;enquene(q, p-lchild);}else{flag true;}if (p-rchild){if (flag) // 如果之前遇到了空节点说明不是完全二叉树return false;enquene(q, p-rchild);}else{flag true;}}return true;
}
int main()
{treenode* t;buildtree(t);if (isok(t))printf(yes);elseprintf(no);return 0;
}
用ABD##E##CF##G##测试
/* A B C
D E F G
*/ 用ABD###CF##G##测试
/* A B C
D F G
*/ 还可以用另外一种写法
#include stdio.h
#include stdlib.h
#define Max 15
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
} treenode, * tree;
void buildtree(tree* t)
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;(*t)-lchild NULL;(*t)-rchild NULL;buildtree((*t)-lchild);buildtree((*t)-rchild);}
}int isok(tree* t)//判断完全二叉树
{treenode* q[Max];int f -1, r -1;int tag 1;//标记是否为完全二叉树q[r] *t;treenode* p;int flag 1;//标记缺孩子if (*t NULL) {tag 1;}if (!(*t)-lchild !(*t)-rchild)tag 1;while (f r) {p q[f];if (!p-lchild) //没有左孩子缺孩子{flag 0;if (p-rchild)tag 0;}else//有左孩子{if (flag)//之前不存在缺孩子的结点{q[r] p-lchild;if (p-rchild)q[r] p-rchild;elseflag 0;}else//之前存在缺孩子的结点tag 0;}}if (tag)return 1;return 0;
}
int main()
{treenode* t;buildtree(t);if (isok(t))printf(yes);elseprintf(no);return 0;
}
用ABD##E##CF##G##
/* A B C
D E F G
*/
测试结果为 用AB#E##CF###
/* A B C E F
*/
测试结果为
