1樓:匿名使用者
樓主看樣子是才學資料結構吧...我以前學過,忘很多了,看這麼高的分,我就順便複習一下吧;
首先理解一下什麼是高度:高度其實也叫深度,我通俗點說就是 比如根節點 是第一層,根節點的左右孩子為第二層,然後根節點的左右孩子各自的孩子為第三層.....那麼二叉樹的高度就是這棵樹最大的層數。
這麼說不知道樓主明白了沒有,舉例就是:如果只有乙個根節點,那麼高度就是1,如果有乙個根節點再加上根節點的兩個孩子,或者其中乙個孩子,那麼高度就是2;
那根據這樣 如果用遞迴的思想,我想演算法就比較好寫了,就是統計一下根節點的左右孩子的高對唄,看哪個的高度更大那二叉樹高度就是那個唄。下面我貼上出網上的兩個演算法(我沒去執行試過,錯了別怪我)順便解釋一下:
#include
#include//標頭檔案就不用說了吧
typedef struct nodenode,*tree; //二叉樹的定義也不用多說吧那個data的資料型別char可以任意換是吧
int max(int m, int n)
//這個我想能夠看明白 求兩個數最大值,為什麼要求最大值上面也說了
int treeheight(node *root)
//否則遞迴計算他的左右孩子的高度然後在加上根節點的層數1 對吧
int height(node *t) //第二個演算法(其實和第乙個一樣)
//吧,這就是個逗號表示式,判斷?a:b 判斷滿足就返回a不滿
} //足就返回b 那這句換還是一樣就是求m和n的最大值然後加1返 回
大概就這麼個意思,如果程式沒通過,樓主可以試著按這個想法稍微改改。
分能給我麼?
2樓:
int depth (bitree t )
return depthval;}
以二叉鍊錶作儲存結構,試編寫求二叉樹高度的演算法
3樓:匿名使用者
主方法呼叫rootfirst(&root,0);即可,g_nmax 即為最終的樹的高度。
int g_nmax = 0;
voild rootfirst(treenode *p,int nlevel) }
if(null != p->left )
if(null != p->right)}
以二叉鍊錶為儲存結構,寫出求二叉樹高度和寬度的演算法
4樓:兔老大公尺奇
樹的高度:對非空二叉樹,其深度等於左子樹的最大深度加1。
int depth(bintree *t)
樹的寬度:按層遍歷二叉樹,採用乙個佇列q,讓根結點入佇列,最後出佇列,若有左右子樹,則左右子樹根結點入佇列,如此反覆,直到隊列為空。
int width(bintree *t)void countleaf (btnode *t)
//葉子節點總數}。
擴充套件資料
方法:求二叉樹的高度的演算法基於對二叉樹的三種遍歷,可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度,當找到乙個比已知高度還要高的葉子,重新整理最高高度。
最後遍歷下來就是樹的高度,至於後序遍歷的演算法,是一本資料結構或者演算法的書中都有介紹和參考**
5樓:匿名使用者
原題:以二叉鍊錶為儲存結構,分別寫出求二叉樹高度及寬度的演算法。所謂寬度是指在二叉樹的各層上,具有結點數最多的那一層上的結點總數。
標準答案:
①求樹的高度
思想:對非空二叉樹,其深度等於左子樹的最大深度加1。
int depth(bintree *t)②求樹的寬度
思想:按層遍歷二叉樹,採用乙個佇列q,讓根結點入佇列,最後出佇列,若有左右子樹,則左右子樹根結點入佇列,如此反覆,直到隊列為空。
int width(bintree *t)while(frontlchild!=null)if(t->rchild!=null)
if(front==p)
/* 當前層已遍歷完畢*/
}/* endwhile*/
return(flag);}
6樓:匿名使用者
遞迴,用乙個一維陣列維護各層的節點數資訊。層序遍歷 類似bfs 借助乙個佇列。
以二叉樹鍊錶作為二叉樹的儲存結構,怎麼編寫演算法計算返回二叉樹的高度?
7樓:大大的
編寫方法如下:
高度其實也叫深度,我通俗點說就是 比如根節點 是第一層,根節點的左右孩子為第二層,然後根節點的左右孩子各自的孩子為第三層.....那麼二叉樹的高度就是這棵樹最大的層數。這麼說不知道樓主明白了沒有,舉例就是:
如果只有乙個根節點,那麼高度就是1,如果有乙個根節點再加上根節點的兩個孩子,或者其中乙個孩子,那麼高度就是2;
那根據這樣 如果用遞迴的思想,演算法就比較好寫了,就是統計一下根節點的左右孩子的高對唄,看哪個的高度更大那二叉樹高度就是哪個。
具體**如下:
#include
#include//標頭檔案就不用說了吧
typedef struct nodenode,*tree; //二叉樹的定義也不用多說吧那個data的資料型別char可以任意換是吧
int max(int m, int n)
if (m > n)
return m;
else
return n;
} //這個我想能夠看明白 求兩個數最大值,為什麼要求最大值上面也說了
int treeheight(node *root)
if (root == null)
return 0; //如果根節點都沒有 那高度肯定就是0了 是吧
else
return 1 + max(treeheight(root->lchild), treeheight(root->rchild));
} //否則遞迴計算他的左右孩子的高度然後在加上根節點的層數1 對吧
int height(node *t) //第二個演算法(其實和第乙個一樣)
if(t==null)
return 0;
else
int m=height(t->lchild);
int n=height(t->rchild); //遞迴計算該節點的左右孩子的高度
return(m>n)?m+1:n+1; //只不過這裡沒有用到上面求最大值的那個函式,樓主應該學過c
} //吧,這就是個逗號表示式,判斷?a:b 判斷滿足就返回a不滿
} //足就返回b 那這句換還是一樣就是求m和n的最大值然後加1返 回
假設以二叉鍊錶作為二叉樹的儲存結構,試編寫乙個求樹的高度的演算法
8樓:匿名使用者
int length(bitree t)
bitree find(bitree t,elemtype x) //該函式返回給定值的結點的指標
9樓:易xiao萱
#include
using namespace std;
template
struct binode
;template
class bitree
void preorder()
int deepth()
int empty();
private:
binode*root;
binode*creat(binode*bt);
int deepth(binode*bt);
};template
binode*bitree::creat(binode*bt)return bt;
}template
int bitree::empty()
template
int bitree::deepth(binode*bt)//求深度的演算法
}int main()
return 0;}
10樓:_青青子衿
int btnodedepth (btnode *t)}
以二叉鍊錶為儲存結構,分別寫出求二叉樹結點總數,葉子總數,二叉樹高度的演算法;輸出此樹中序遍歷的序列 50
11樓:匿名使用者
int countnode (btnode *t) //節點總數
void countleaf (btnode *t) //葉子節點總數 }
求二叉樹高度的原理、演算法是什麼,越詳細越好,c語言,謝謝
12樓:
首先分copy析二叉樹的深度(高度)和它的左、右子樹深度之間的關係。從二叉樹深度的定義可知,二叉樹的深度應為其左、右子樹深度的最大值加1。由此,需先分別求得左、右子樹的深度,演算法中「訪問結點」的操作為:
求得左、右子樹深度的最大值,然後加 1 。
int depth (bitree t )return depthval;}
13樓:匿名使用者
二叉樹高度的計算是通過遍歷來實現的,主要的遍歷方法有三種:前序遍歷、中序遍歷、後序遍歷,這幾種方法又有共同的實現方法:一般採用遞迴來實現。遞迴演算法在c語言中是個很重要的知識點。
希望回答對你有幫助。
什麼是二叉樹,什麼是二叉樹?二叉樹拿來幹什麼?
二叉樹 binary tree 是樹形結構的乙個重要型別。是指樹中節點的度不大於2的有序樹,它是一種最簡單且最重要的樹。二叉樹的遞迴定義為 二叉樹是一棵空樹,或者是一棵由乙個根節點和兩棵互不相交的,分別稱作根的左子樹和右子樹組成的非空樹 左子樹和右子樹又同樣都是二叉樹。1.許多實際問題抽象出來的資料...
遞迴做二叉樹的寬度,編寫計算二叉樹最大寬度的演算法
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 編寫計算二叉樹最大寬度的演算法 分析 二叉樹是遞迴定義的,其計算二叉樹的高度可以採取遞迴方式 int height btre bt 求二叉樹bt的深度 分析 求二叉樹的最大寬度可採用層次遍歷的方法,記下各層結點數,每層遍...
關於二叉樹的問題,下面關於二叉樹的說法正確的是()
先序遍歷序列可得 1為根節點 而且其左子樹的根節點為2 後序遍歷序列可得其右子樹根節點為3 由此可劃分出樹的大體 2 34 576 對於這道題4是2的左孩子還是右孩子是無法判斷的都是可以的 哪麼看右子樹的先序遍歷序列3576 以及右子樹的後序遍歷序列7563 可以得到 5 6哪麼可以得到以下兩個結果...
有道「完全二叉樹」的題不會做,急求人幫忙
根據二叉樹的性質 對於一棵非空的二叉樹,如果葉子節點數為n0,度為2的結點數為n2,則no n2 1.根據完全二叉樹的定義可得 在完全二叉樹中度為1的結點n1只能取兩種情況,要麼為0,要麼為1.所以 n0 n1 n2 700 n0 n2 1 2n0 701 n1 因為結點數為整數,所以n1 1,no...
20分求解關於二叉樹的先中後序遍歷結果出錯
二叉樹前序遍歷函式dpre order access 遞迴演算法 引數描述 btnode head 二叉樹的根節點指標 void dpre order access btnode head 二叉樹中序遍歷函式dmid order access 遞迴演算法 引數描述 btnode head 二叉樹的根...