二叉树算法题及答案

1. 题目3． 平衡二叉树算法查找树中某节点的时间复杂度是多少

平均查找的时间复杂度为O(log n)。

平衡树的查找过程和排序树的相同。在查找过程中和给定值进行比较关键字个数不超过树的深度。

如果二叉树的元素个数为n，那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。

是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。

(1)二叉树算法题及答案扩展阅读：

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：

(1)空二叉树——(a)

(2)只有一个根结点的二叉树——(b);

(3)右子树为空的二叉树——(c);

(4)左子树为空的二叉树——(d);

(5)完全二叉树——(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

2. 一个有关二叉树的问题

在完全二叉树中，第m个结点的父结点为m/2取下整。
第k个结点的左孩子是2k，右孩子是2k+1,因此可以用一个队列来保存结点m的左右孩子，然后依次对队列中的每个结点进行以下操作，直到结点编号超过n：
队列头结点出队列，对该结点得到其两个孩子，将两个孩子进队列。

3. 已知二叉树以二叉链表做为存储结构，阅读算法并回答下列问题：（1）该算法的功能是什么（2）算法中的n的作

该算法的功能是前序遍历二叉树，统计二叉树中含有左右两个孩子的结点的个数。n的作用是统计二叉树中含有左右两个孩子的结点的个数。

4. 对于二叉树的遍历算法,下面描述正确的是

ABD的叙述都是正确的.C中,树的前趋结点只有唯一一个,这样才是树结构.

5. 求数据结构（JAVA版）实验树和二叉树题目答案

/**
* @param args
之前在大学的时候写的一个二叉树算法，运行应该没有问题，就看适不适合你的项目了 */
public static void main(String[] args) {

BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("递归前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非递归前序遍历二叉树结果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("递归中序遍历二叉树的结果为:");
tree.inOrder(tree);
System.out.println();
System.out.println("非递归中序遍历二叉树的结果为:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("递归后序遍历二叉树的结果为:");
tree.postOrder(tree);
System.out.println();
System.out.println("非递归后序遍历二叉树的结果为:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree));
System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree));

System.out.println("二叉树中,每个节点所在的层数为:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的层为:" + tree.level(p));
System.out.println("二叉树的高度为:" + height(tree));
System.out.println("二叉树中节点总数为:" + nodes(tree));
System.out.println("二叉树中叶子节点总数为:" + leaf(tree));
System.out.println("二叉树中父节点总数为:" + fatherNodes(tree));
System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree));
System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree));
System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree));
System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree));
System.out.println("--------------------------------------");
tree.exChange();
System.out.println("交换每个节点的左右孩子节点后......");
System.out.println("递归前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非递归前序遍历二叉树结果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("递归中序遍历二叉树的结果为:");
tree.inOrder(tree);
System.out.println();
System.out.println("非递归中序遍历二叉树的结果为:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("递归后序遍历二叉树的结果为:");
tree.postOrder(tree);
System.out.println();
System.out.println("非递归后序遍历二叉树的结果为:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();

System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree));
System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree));

System.out.println("二叉树中,每个节点所在的层数为:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的层为:" + tree.level(p));
System.out.println("二叉树的高度为:" + height(tree));
System.out.println("二叉树中节点总数为:" + nodes(tree));
System.out.println("二叉树中叶子节点总数为:" + leaf(tree));
System.out.println("二叉树中父节点总数为:" + fatherNodes(tree));
System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree));
System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree));
System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree));
System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree));
}
}

6. 以二叉链表为存储结构,写出求二叉树高度和宽度的算法

树的高度：对非空二叉树，其深度等于左子树的最大深度加1。

Int Depth(BinTree *T){int dep1,dep2;

if(T==Null) return(0);

else{dep1=Depth(T->lchild);

dep2=Depth(T->rchild);

if(dep1>dep2) return(dep1+1);

else return(dep2+1);}

树的宽度：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。

int Width(BinTree *T){intfront=-1,rear=-1;

/*队列初始化*／int flag=0,count=0,p;

/* pint CountNode (BTNode *t)

//节点总数{int num;if (t == NULL)num = 0;

elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);

return (num);}void CountLeaf (BTNode *t)

//叶子节点总数{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;

// 全局变量CountLeaf (t->lch);CountLeaf (t->rch);}}。

(6)二叉树算法题及答案扩展阅读

方法：

求二叉树的高度的算法基于对二叉树的三种遍历，可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度，当找到一个比已知高度还要高的叶子，刷新最高高度。

最后遍历下来就是树的高度，至于后序遍历的算法，是一本数据结构或者算法的书中都有介绍和参考代码

7. 关于二叉树的问题，高分求答案！急！

#include "stdio.h"
#include "malloc.h"
#define MAXNODE 100
int k=0;//定义一全局变量，用于统计树中叶子结点的个数
typedef struct node
{char data;
struct node *lchild,*rchild;
}tnode ,*btree;

//------------------------------------------------------------------
void creat(btree *t)//先序创建二叉树
{ char ch;
scanf("%2c",&ch);
if(ch=='0')
*t= NULL;
else
{*t=(btree)malloc(sizeof(tnode));
(*t)->data=ch;
creat(&(*t)->lchild);
creat(&(*t)->rchild);
}

}
//------------------------------------------------------------------
/*btree creat( )
{ btree t;
char ch;
scanf("%2c",&ch);
if(ch=='0')
t= NULL;
else
{t=(btree)malloc(sizeof(tnode));
t->data=ch;
t->lchild=creat();
t->rchild=creat();
}
return t;
}*/
//------------------------------------------------------------------
void middle(btree t)//中序遍历二叉树
{if(t==NULL) return;
middle(t->lchild);
printf("%2c",t->data);
middle(t->rchild);
}
//------------------------------------------------------------------
void first(btree t)//先序遍历二叉树
{if(t==NULL)return ;
printf("%2c",t->data);
first(t->lchild);
first(t->rchild);
}
//------------------------------------------------------------------
void last(btree t)//后序遍历二叉树
{if(t==NULL)return ;
last(t->lchild);
last(t->rchild);
printf("%2c",t->data);
}
//------------------------------------------------------------------
void level(btree t)//层次遍历二叉树
{btree q[MAXNODE];
int front,rear;
front=rear=-1;
if(t==NULL) return;
rear++;
q[rear]=t;//根结点入队列
while(front!=rear)//当队列不为空,则将对头元素出队列，并把其左右孩子入队列
{
front++;
printf("%2c",q[front]->data);
if(q[front]->lchild!=NULL)
{
rear++;
q[rear]=q[front]->lchild;
}
if(q[front]->rchild!=NULL)
{
rear++;
q[rear]=q[front]->rchild;
}
}

}
//------------------------------------------------------------------

btree search(btree t,char x)//在二叉树中查找数据x
{btree p,q;
p=t;
if(p->data==x)return p;
if(p->lchild!=NULL &&(q=search(t->lchild,x))) return q;
/*
if(p->lchild!=NULL)
q=search(t->lchild,x);
if(q!=NULL)
return q;
*/

if(p->rchild!=NULL &&(q=search(t->rchild,x))) return q;
return NULL;
}

//------------------------------------------------------------------
void num_leaf(btree t)//利用中序递归遍历算法求二叉树中叶子结点的个数
{
if(t!=NULL)
{num_leaf(t->lchild);
if(t->lchild==NULL && t->rchild==NULL) k++;
num_leaf(t->rchild);
}
}

//------------------------------------------------------------------
int num_node(btree t)//求二叉树中结点的个数
{
int num1,num2;
if(t==NULL)
return 0;
else if(t->lchild==NULL&&t->rchild==NULL)
return 1;
else
{
num1=num_node(t->lchild);
num2=num_node(t->rchild);
return(num1+num2+1); //返回左右子树结点数加1
}
}
//------------------------------------------------------------------
int high_t(btree t)//利用递归算法求二叉树的深度
{ int l,r,h;
if(t==NULL) h=0;
else
{l=high_t(t->lchild);
r=high_t(t->rchild);
h=(l>r?l:r)+1;
/*
if(l>r)
h=l+1;
else
h=r+1;
*/
}
return h;
}
//------------------------------------------------------------------
void main()
{btree t,p;
char x;
t=(btree)malloc(sizeof(tnode));
printf("\n请按先序的顺序依次输入二叉树中结点的数据域\n");
//t=creat();
creat(&t);
printf("\n先序遍历的结果为：");
first(t);
printf("\n中序遍历的结果为：");
middle(t);
printf("\n后序遍历的结果为：");
last(t);
printf("\n层次遍历的结果为：");
level(t);
num_leaf(t);
printf("\n该二叉树中叶子结点的数目为：%d\n",k);
printf("\n该二叉树的深度为：%d\n",high_t(t));
printf("\n该二叉树的结点的数目为：%d\n",num_node(t));
do
{printf("\n请输入要查找的数据：");
scanf("%2c",&x);
p=search(t,x);
if(p)
printf("\nYES!该二叉树中存在所要查找的数据!");
else
printf("\nNO!该二叉树中不存在所要查找的数据!");
printf("\n继续查找吗?(Y/N)");
scanf("%2c",&x);
}while (x=='y'||x=='Y');
}

8. 关于二叉树结点算法的问题

满二叉树是没有度为1的结点。

完全二叉树定义：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。

完全二叉树叶子结点的算法：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2 ，就可根据完全二叉树的结点总数计算出叶子结点数。

因此叶子结点数是(839+1)/2=420

9. 二叉树试题

答案是A？？？
应该是B
看算法与数据结构就OK啦

10. 以二叉链表为存储结构,写出求二叉树高度和宽度的算法

原题:
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案:
①求树的高度
思想:对非空二叉树，其深度等于左子树的最大深度加1。
Int
Depth(BinTree
*T)
{
int
dep1,dep2;
if(T==Null)
return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2)
return(dep1+1);
else
return(dep2+1);
}
②求树的宽度
思想:按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int
Width(BinTree
*T)
{
int
front=-1,rear=-1;/*
队列初始化*/
int
flag=0,count=0,p;
/*
p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*/if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/*
当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear;
/*
p指向下一层最右边的结点*/
}
}
/*
endwhile*/
return(flag);
}