23629人阅读
准备笔试（9）
面试准备（5）
二叉树的常见问题有如下几个，如果解决好了，就跟链表一样轻松：唯一不一样的是，二叉树是非线性结构。常见的问题如下：
二叉树的问题
1.二叉树三种周游（traversal）方式：
二叉树的问题
1.二叉树三种周游（traversal）方式：
2.怎样从顶部开始逐层打印二叉树结点数据
3.如何判断一棵二叉树是否是平衡二叉树
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得
5.如何不用递归实现二叉树的前序/后序/中序遍历？
6.在二叉树中找出和为某一值的所有路径
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
8.判断整数序列是不是二叉搜索树的后序遍历结果
9.求二叉树的镜像
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距
离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
11.把二叉搜索树转变成排序的双向链表
12.打印二叉树中的所有路径（与题目5很相似）
3.如何判断一棵二叉树是否是平衡二叉树
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。
5.如何不用递归实现二叉树的前序/后序/中序遍历？
6.在二叉树中找出和为某一值的所有路径（注意是到叶子节点）
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
8.判断整数序列是不是二叉搜索树的后序遍历结果
9.求二叉树的镜像
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
11.把二叉搜索树转变成排序的双向链表
12.打印二叉树中的所有路径（与题目6很相似）
解决思路：
1.二叉树三种周游（traversal）方式：任何一本数据结构的书都有描述，略过；
2.怎样从顶部开始逐层打印二叉树结点数据？
设置一个队列，然后只要队列不为空，将对首元素的左右孩子加入队列（如果左右孩子不为空），然后将队列的首元素出对即可，如下图所示：
二叉树如下图所示：
那么，整个过程如下：
自然，就输出了a,b,c,d,e,f
3.如何判断一个二叉树是否是平衡的？
太简单了，利用递归就可以了：判断根节点的左右子树深度之差是否小于等于1(这里需要用到求深度的方法)，如果是，根节点就是平衡的；然后，在判断根节点的左孩子和右孩子是否是平衡的。如此继续下去，直到遇见叶子节点。一旦不是，立刻返回
计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分
首先找到这两个点key1和key2，并且记录下找到这两个点的路径Path1和Path2。然后，找到第一个点k满足，key1&k&key2就可以了。
假设key1 = 5，key2 = 7，那么显然，Path1{8,6,5}, Path2{8,6,7}。满足第一个key1&k&key2的k为6。故k = 6。
至于怎么求出Path1和Path2，可以看问题12。
5.如何不用递归实现二叉树的前序/后序/中序遍历？（网易面试就问到了，悲剧了，当时一下子卡住了）
看看书，基本任何一本数据结构的书都有，主要利用栈。
6.在二叉树中找出和为某一值的所有路径？
还是先解决12题目，访问二叉树到叶子节点的任意路径。这个问题解决了，自然求和看是否满足条件就可以了。
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
递归，还是利用递归：
设有int array[begin,end]，首先将array[(begin + end)/2]加入二叉树，然后递归去做array[begin,(begin + end)/2 - 1]和array[(begin + end)/2 + 1, end]。注意写好函数的形式就可以了。一切都很自然。
8.判断整数序列是不是二叉搜索树的后序遍历结果？
看看吧，后续遍历是这样做的：左右根，所以访问的最有一个节点实际上就是整棵二叉树的根节点root：然后，找到第一个大于该节点值的根节点b，b就是root右子树最左边的节点（大于根节点的最小节点）。那么b前面的就是root的左子树。既然是二叉搜索树的遍历结果，那么在b和root之间的遍历结果，都应该大于b。去拿这个作为判断的条件。
9.求二叉树的镜像？
还是利用递归：只要节点不为空，交换左右子树的指针，然后在分别求左子树的镜像，再求右子树的镜像，直到节点为NULL。
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
首先，在BST中，最小值就是最左边的节点，最大值就是最右边的节点。
在分别求出min和max后，求出f。然后利用查找，找出一个大于f的节点就可以了。
复杂度为logN。
11.把二叉搜索树转变成排序的双向链表
12..打印二叉树中的所有路径
路径的定义就是从根节点到叶子节点的点的集合。
还是利用递归：用一个list来保存经过的节点，如果已经是叶子节点了，那么打印list的所有内容；如果不是，那么将节点加入list，然后继续递归调用该函数，只不过，入口的参数变成了该节点的左子树和右子树。
程序如下：
解答1：自己看书了
//问题2：怎样从顶部开始逐层打印二叉树结点数据
void PrintAtLevel(BiTNode* root){
vector&BiTNode*&
vector.push_back(root);
while(!vector.empty()){
BiTNode* tmp = vector.front();
if(tmp-&lchild != NULL)
vector.push_back(tmp-&lchild);
if (tmp-&rchild != NULL)
vector.push_back(tmp-&rchild);
cout && tmp-&data &&
vector.pop_back();
//问题3：如何判断一棵二叉树是否是平衡二叉树
int isBalencedTree(treeNode* root){
if (root == NULL)
int depth1 = getDepth(root-&lchild);
int depth2 = getDepth(root-&rchild);
if (depth1 == depth2 || depth1 == depth2 + 1 || depth1 == depth2 - 1)
int flag1 = isBalencedTree(root-&lchild);
int flag2 = isBalencedTree(root-&rchild);
if (flag1 && flag2)
//问题4：设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)
则不得分。
int getPublicAncestors(treeNode* root,int key1,int key2){
treeNode* ptr =
int path1[1000];
int pathLen1 = 0;
while (ptr != NULL){
if (key1 == ptr-&data){
path1[pathLen1] = ptr-&
pathLen1 ++;
printArray(path1,pathLen1);
if (ptr-&data & key1){
path1[pathLen1] = ptr-&
pathLen1 ++;
ptr = ptr-&
if (ptr-&data & key1){
path1[pathLen1] = ptr-&
pathLen1 ++;
ptr = ptr-&
int path2[1000];
int pathLen2 = 0;
while (ptr != NULL){
if (key2 == ptr-&data){
path2[pathLen2] = ptr-&
pathLen2 ++;
printArray(path2,pathLen2);
if (ptr-&data & key2){
path2[pathLen2] = ptr-&
pathLen2 ++;
ptr = ptr-&
if (ptr-&data & key2){
path2[pathLen2] = ptr-&
pathLen2 ++;
ptr = ptr-&
int i = pathLen1 - 1;
//key1和key2有序，
if (key2 & key1){
key2 = key2^key1;
key1 = key2^key1;
key2 = key2^key1;
for (; i & 0; i --){
if (key1 & path1[i] && path1[i]& key2){
int result = path1[i];
//问题6：在二叉树中找出和为某一值的所有路径
void FindPath(treeNode* root, int path[],int pathLen,int expectedSum, int
currentSum){
if (root == NULL)
currentSum += root-&
path[pathLen] = root-&
pathLen ++;
if (currentSum == expectedSum && root-&lchild == NULL && root-&rchild ==
printArray(path,pathLen);
if (root-&lchild != NULL){
FindPath(root-&lchild,path,pathLen,expectedSum,currentSum);
if (root-&rchild != NULL){
FindPath(root-
&rchild,path,pathLen,expectedSum,currentSum);
currentSum -= root-&
//问题7：怎样编写一个程序，把一个有序整数数组放到二叉树中？
void createTreeFromArray(int a[], int begin, int end, treeNode** root){
if (begin & end)
*root = (treeNode*) malloc(sizeof(treeNode));
int mid = (begin + end) / 2;
(*root)-&data = a[mid];
(*root)-&rchild = NULL;
(*root)-&lchild = NULL;
createTreeFromArray(a, begin ,mid - 1, &(*root)-&lchild);
createTreeFromArray(a, mid + 1 ,end, &(*root)-&rchild);
//问题8：判断整数序列是不是二叉搜索树的后//序遍历结果
int isPostTraverse(int a[], int begin ,int end){
if(begin &= end)
int root = a[end];
int location =
for (i = i & i ++){
if(a[i] & root){
location =
lroot = a[i];
for (i = location + 1; i & i++){
if (a[i] & lroot){
int flag1 = isPostTraverse(a,begin,location -1);
int flag2 = isPostTraverse(a,location,end - 1);
if (flag1 && flag2)
//问题9：求二叉树的镜像
void changeMirror(treeNode** root){
if ( *root == NULL)
treeNode* temp = (*root)-&
(*root)-&lchild = (*root)-&
(*root)-&rchild =
changeMirror(&(*root)-&lchild);
changeMirror(&(*root)-&rchild);
//问题10：10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算
//法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
int findNearMid(treeNode** root){
treeNode* ptr = *
while (ptr != NULL){
min = ptr-&
ptr = ptr-&
printf(&the min is %d\n&,min);
while (ptr != NULL){
max = ptr-&
ptr = ptr-&
printf(&the max is %d\n&,max);
int half = (min + max) && 1;
printf(&half is %d\n&,half);
while (1){
if (ptr-&data & half){
ptr = ptr-&
if (ptr-&data & half){
int result = ptr-&
return (ptr-&rchild)-&
//问题12：打印二叉树中的所有路径（与题目5很相似）
void printPathsRecur(treeNode* node, int path[], int pathLen) {
if (node == NULL)
// append this node to the path array
path[pathLen] = node-&
pathLen++;
// it's a leaf, so print the path that led to here
if (node-&lchild == NULL && node-&rchild == NULL) {
printArray(path, pathLen);
// otherwise try both subtrees
printPathsRecur(node-&lchild, path, pathLen);
printPathsRecur(node-&rchild, path, pathLen);
void printPaths(treeNode* node) {
int path[1000];
printPathsRecur(node, path, 0);
//用到的辅助函数：
* 求二叉树的深度
int getDepth(tNode root) {
if (root == NULL)
return getDepth(root-&lchild) & getLeaf(root-&rchild) ? 1 +
root-&lchild) : 1 + getDepth(root-&rchild);
int depthLchild = 1 + getDepth(root-&lchild);
int depthRchild = 1 + getDepth(root-&rchild);
return depthLchild & depthRchild ? depthLchild:
* 打印数组
void printArray(int ints[], int len) {
for (i = 0; i & i++) {
printf(&%d &, ints[i]);
printf(&\n&);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：972994次
积分：7953
积分：7953
排名：第2535名
原创：125篇
转载：48篇
评论：350条
(1)(3)(4)(2)(3)(4)(1)(3)(1)(2)(6)(3)(18)(1)(2)(12)(26)(24)(8)(2)(23)(24)扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
高度为5的二叉树至多有结点数多少个可是答案却是64，是不是这个答案错了？谁知道正确答案啊
字母wan1901
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
1+2+4+8+16=2^5-1=31
为您推荐：
其他类似问题
2的N+1次幂。书上有公式2的六次幂就是64喽
扫描下载二维码求大神指导 关于汇编语言写二叉树_汇编吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：33,233贴子：
求大神指导 关于汇编语言写二叉树收藏
最近老师留作业是用汇编语言写二叉树这些是需要的变量ARGV_NVAL = 6
| The number of nodes in the final tree (see &list&)NODE_VALUE
| Offset to ADD to the addr of a node to access its valueNODE_LEFT
| Offset to ADD to the addr of a node to access its left child addressNODE_RIGHT
| Offset to ADD to the addr of a node to access its right child addressNODE_OFFSET = -12
| Offset to ADD to next_mem when a node was createdCMOVE(stack_start, SP)
| Initialize stack segment: it begins just after the code segmentBR(main)
| Set program entry pointnext_mem:
| A global variable containing the next address available to allocate a
ALLOCATE(1)
| node. Should be incremented by NODE_OFFSET once the space was allocated
| to a new node, so that another node can be added in memory.tree_loc:
| A global variable containing the address of the tree root node.
LONG(0x0003FFFC)
| This variable should NEVER be modified, else you could loose
| access to your tree.list:
| The list of values to insert in the tree. Its length should be equal
| to ARGV_NVAL. This list and its element can NEVER be modified.
LONG(0x)我刚刚知道基本结构是啥＝（ 但是表示放不进去呀！！.include beta.uasm.include config.uasmCMOVE(stack_start, SP)
BR(main)main:
| Your main code goes here (you may erase this comment)
| Marks the end of the program execution. This should be the last executed instruction.| Additional code of yours might come here (you may erase this comment)| !! NO MODIFICATION WILL BE ACCEPTED BELOW THIS COMMENT !!.include stack_segment.uasm求大神指导！！！！
2楼的世界我不懂------回复于:日23时40分24秒
求大神指点！！！
登录百度帐号推荐应用汇编实现简单二叉树
我的图书馆
汇编实现简单二叉树
TITLE Binary
INCLUDE Irvine32.inc.data&array BYTE 50 dup('0')&strAskRoot BYTE 0dh,0ah,"Root:" ,0&strAskLeft BYTE 0dh,0ah,"left:" ,0&strAskRight BYTE 0dh,0ah,"Right:" ,0&strOrder BYTE 0dh,0ah,"Order:" ,0.codemain proc&&;mov ax,@data&;mov ds,ax&&mov& edx,offset strAskRoot&call WriteString&&mov& ebx,1&call CreateBT ;递归建树&&mov& edx,offset strOrder &call WriteString&&mov& ebx,1&call O前序遍历树&&exit
CreateBT proc uses eax ebx&&& &&mov eax,0&&call ReadChar&cmp al,0dh&je Exit&mov array[ebx],al&call WriteChar&call LeftChild&call RightChild&Exit:&&ret
CreateBT endp
LeftChild proc uses eax edx ebx
&mov edx,offset strAskLeft&call WriteString&&push ebx&shl ebx,1&call CreateBT &pop ebx&&ret
LeftChild endp
RightChild proc uses eax edx ebx
&mov edx,offset strAskRight&call WriteString&&push ebx&shl ebx,1&inc ebx&call CreateBT &pop ebx&&ret
RightChild endp
Order pr该过程为前序遍历，中序遍历、后序遍历与前序遍历大致相同&&cmp array[ebx],'0'&je return1&mov al,array[ebx]&call WriteChar&&call PrintLeft&&call PrintRight&return1:&ret
Order endp
PrintLeft proc uses ebx&&push ebx&shl ebx,1&call Order&pop ebx&&ret
PrintLeft endp
PrintRight proc uses ebx&&push ebx&shl ebx,1&inc ebx&call Order&pop ebx&&ret
PrintRight endpend main
TA的最新馆藏
喜欢该文的人也喜欢}