1樓：商葉楓
二叉樹（binary tree）是樹形結構的乙個重要型別。是指樹中節點的度不大於2的有序樹，它是一種最簡單且最重要的樹。
二叉樹的遞迴定義為：二叉樹是一棵空樹，或者是一棵由乙個根節點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹。
1. 許多實際問題抽象出來的資料結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的儲存結構及其演算法都較為簡單，因此二叉樹顯得特別重要。
2. 二叉樹特點是每個結點最多只能有兩棵子樹，且有左右之分。
3. 二叉樹是n個有限元素的集合，該集合或者為空、或者由乙個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。
在二叉樹中，乙個元素也稱作乙個結點。
2樓：都市的凌晨
在電腦科學中，樹是一種重要的非線性資料結構，直觀的看，它是資料元素按分支關係組織起來的結構。二叉樹是每個節點最多有兩個子樹的有序樹，通常子樹的根被稱作「左子樹」和「右子樹」。
什麼是二叉樹？二叉樹拿來幹什麼？
3樓：匿名使用者
1、二叉樹在圖論中是這樣定義的：二叉樹是乙個連通的無環圖，並且每乙個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。
有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的資訊來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。
2、二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查詢樹和二叉堆。
二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹t，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。
一棵深度為k，且有2^k-1個節點稱之為滿二叉樹；深度為k，有n個節點的二叉樹，當且僅當其每乙個節點都與深度為k的滿二叉樹中，序號為1至n的節點對應時，稱之為完全二叉樹。
4樓：匿名使用者
在電腦科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常
子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查詢樹和二叉堆。二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。
二叉樹的第i層至多有2的（i-1）次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹t，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹和二叉樹的2個主要差別：
1. 樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；
2. 樹的結點無左、右之分，而二叉樹的結點有左、右之分。……
樹是一種重要的非線性資料結構，直觀地看，它是資料元素（在樹中稱為結點）按分支關係組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程式時，可用樹表示源程式的語法結構。
又如在資料庫系統中，樹型結構也是資訊的重要組織形式之一。一切具有層次關係的問題都可用樹來描述。
樹的概述
樹結構的特點是：它的每乙個結點都可以有不止乙個直接後繼，除根結點外的所有結點都有且只有乙個直接前趨。以下具體地給出樹的定義及樹的資料結構表示。
樹的定義
樹是由乙個或多個結點組成的有限集合，其中：
⒈必有乙個特定的稱為根(root)的結點；
⒉剩下的結點被分成n>=0個互不相交的集合t1、t2、......tn，而且， 這些集合的每乙個又都是樹。樹t1、t2、......tn被稱作根的子樹(subtree)。
樹的遞迴定義如下：（1）至少有乙個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結點稱為葉結點或終端結點。
樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次，如上圖，其深度為3；
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點a，其原來的二棵子樹t1、t2、t3的集合就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
樹的表示
樹的表示方法有許多，常用的方法是用括號：先將根結點放入一對圓括號中，然後把它的子樹由左至右的順序放入括號中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最後用閉括號括起來。如上圖可寫成如下形式：
(a(b(e(k,l),f),c(g),d(h(m),i,j)))
二叉樹1.二叉樹的基本形態
二叉樹也是遞迴定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：
(1)空二叉樹——(a)；
(2)只有乙個根結點的二叉樹——(b)；
(3)只有左子樹——(c)；
(4)只有右子樹——(d)；
(5)完全二叉樹——(e)
注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
2.兩個重要的概念
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的節點都連續集中在最左邊，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每乙個結點都有左右子葉且葉結點都處在最底層的二叉樹,。
3.二叉樹的性質
(1) 在二叉樹中，第i層的結點總數不超過2^(i-1)；
(2) 深度為h的二叉樹最多有2^(h)-1個結點(h>=1)，最少有h個結點；
(3) 對於任意一棵二叉樹，如果其葉結點數為n0，而度數為2的結點總數為n2，
則n0=n2+1；
(4) 具有n個結點的完全二叉樹的深度為int（log2n）+1
(5)有n個結點的完全二叉樹各結點如果用順序方式儲存，則結點之間有如下關係：
若i為結點編號則 如果i<>1，則其父結點的編號為i/2；
如果2*i<=n，則其左兒子（即左子樹的根結點）的編號為2*i；若2*i>n，則無左兒子；
如果2*i+1<=n，則其右兒子的結點編號為2*i+1；若2*i+1>n，則無右兒子。
(6)給定n個節點，能構成h(n)種不同的二叉樹。
h(n)為卡特蘭數的第n項。h(n)=c(n,2*n)/(n+1)。
4.二叉樹的儲存結構
(1）順序儲存方式
type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;
(2)鍊錶儲存方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
5.普通樹轉換成二叉樹
二叉樹很象一株倒懸著的樹，從樹根到大分枝、小分枝、直到葉子把資料聯絡起來，這種資料結構就叫做樹結構，簡稱樹。樹中每個分叉點稱為結點，起始結點稱為樹根，任意兩個結點間的連線關係稱為樹枝，結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的"雙親"，結點的後趨結點稱為該結點的"子女"或"孩子"，同一結點的"子女"之間互稱"兄弟"。
普通樹轉二叉樹，一般採用左「子女」右「兄弟」的方式來轉化。
完全二叉樹
對滿二叉樹，從第一層的結點(即根)開始，由下而上，由左及右，按順序結點編號，便得到滿二叉樹的乙個順序表示。據此編號，完全二叉樹定義如下：一棵具有n個結點，深度為k的二叉樹，當且僅當所有結點對應於深度為k的滿二叉樹中編號由1至n的那些結點時，該二叉樹便是完全二叉樹。
圖4是一棵完全二叉樹。
二叉樹遍歷
遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每乙個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為乙個線性序列來表示。
設l、d、r分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：dlr（稱為先根次序遍歷），ldr（稱為中根次序遍歷），lrd （稱為後根次序遍歷）。
(1)前序遍歷
訪問根；按前序遍歷左子樹；按前序遍歷右子樹
(2)中序遍歷
按中序遍歷左子樹；訪問根；按中序遍歷右子樹
(3)後序遍歷
按後序遍歷左子樹；按後序遍歷右子樹；訪問根
（4）層次遍歷
即按照層次訪問，通常用佇列來做。訪問根，訪問子女，再訪問子女的子女（越往後的層次越低）（兩個子女的級別相同）
特殊的二叉樹
1. 完全二叉樹
complete binary tree
若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若干結點，這就是完全二叉樹。
2. 滿二叉樹
full binary tree：
乙個高度為h的二叉樹包含正是2-1元素稱為滿二叉樹。
5樓：匿名使用者
二叉樹是一種二次有序樹，但與二次有序樹有區別。嚴格區別左右孩子的樹。主要運用計算機領域
二叉樹中的度是什麼
6樓：王后
結點所擁有的子樹的個數稱為該結點的度(degree); 樹中各結點度的最大值稱為該樹的度； 稱度為m的樹為m叉樹。
在電腦科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查詢樹和二叉堆。
二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。
二叉樹不是樹的一種特殊情形，儘管其與樹有許多相似之處，但樹和二叉樹有兩個主要差別：
1. 樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；
2. 樹的結點無左、右之分，而二叉樹的結點有左、右之分。
以二叉樹鍊錶作為二叉樹的儲存結構，編寫演算法計算返回二叉樹的高
樓主看樣子是才學資料結構吧.我以前學過，忘很多了，看這麼高的分，我就順便複習一下吧 首先理解一下什麼是高度 高度其實也叫深度，我通俗點說就是 比如根節點 是第一層，根節點的左右孩子為第二層，然後根節點的左右孩子各自的孩子為第三層.那麼二叉樹的高度就是這棵樹最大的層數。這麼說不知道樓主明白了沒有，舉例...
遞迴做二叉樹的寬度，編寫計算二叉樹最大寬度的演算法
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 編寫計算二叉樹最大寬度的演算法 分析 二叉樹是遞迴定義的，其計算二叉樹的高度可以採取遞迴方式 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 二叉樹的根...