二叉樹演算法題及答案

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);
}