資料結構樹和二叉樹轉換時樹有分左右子樹嗎

2021-03-03 23:12:31 字數 4877 閱讀 2364

1樓:烏石

樹中乙個結點只有乙個孩子,這個孩子不分左右,是第一棵子樹

資料結構樹轉換為二叉樹時,樹有分左右子樹嗎???

2樓:匿名使用者

樹也分,左邊的是第乙個孩子,其他的各個孩子順次接在結點的右子樹

資料結構與演算法 二叉樹交換左右子樹演算法

3樓:匿名使用者

傳入樹的根結點即可:

exchangelr(&root); //root為樹的根節點

void exchangelr(treenode *root)

4樓:id雞蛋炒韭菜

原來節點結構體抄:

typedef struct

node;

現在從新定義bai乙個結構

typedef struct

newnode;

然後用新du

樹的根指zhi向原樹的根

node* poldtree; 老樹

newnode* pnewtree = (newnode*)poldtree;

這樣省的交換了dao,省事吧 -_,-

資料結構的樹和二叉樹之間怎麼轉換?

5樓:果凍沐沐

將樹轉換成二叉樹:

① 加線:在兄弟之間加一連線

② 抹線:對每個結點,除了其左孩子外,去除其與其餘孩子之間的關係③ 旋**以樹的根結點為軸心,將整樹順時針轉45°將二叉樹轉換成樹:

① 加線:若p結點是雙親結點的左孩子,則將p的右孩子,右孩子的右孩子……沿分支找到的所有右孩子,都與p的雙親用線連起來

② 抹線:抹掉原二叉樹中雙親與右孩子之間的連線③ 調整:將結點按層次排列,形成樹結構

6樓:匿名使用者

二叉樹是樹的乙個子類,轉換要看具體的需求

資料結構,二叉樹左右子樹交換,遞迴演算法

7樓:gta小雞

root不為null並不能保證root的child不為null,如果為null那麼試圖訪問child的x成員時就會崩潰。

資料結構c++版,請問順序儲存的二叉樹怎樣實現所有左右子樹交換呢? 10

8樓:辛想事不成

交換子樹只需要交換指標即可,但為了確保精確查詢,最好重建新樹

二叉樹所有結點左右子樹互相交換為什麼不能用中序遍歷?

9樓:q他

給你一段**。c++寫的,你可以自己稍微修改一下:

#include

using namespace std;

#define ok 1

#define error 0

#define overflow -1

typedef int status ;

typedef char telemtype;

typedef struct treenodetreenode,*treep;

使用先序遍歷優勢建立

return t;

}void treetreaversef(treep t) //二叉樹先序遍歷

}void treetreaverses(treep t) //中序遍歷二叉樹

}void treetreaverset(treep t)

}int main()

求資料結構樹與二叉樹轉換c語言**

10樓:匿名使用者

那個叫二叉樹啊

樹是一種重要的非線性資料結構,直觀地看,它是資料元素(在樹中稱為結點)按分支關係組織起來的結構,很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在,如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用,如在編譯源程式如下時,可用樹表示源源程式如下的語法結構。

又如在資料庫系統中,樹型結構也是資訊的重要組織形式之一。一切具有層次關係的問題都可用樹來描述。

一、樹的概述

樹結構的特點是:它的每乙個結點都可以有不止乙個直接後繼,除根結點外的所有結點都有且只有乙個直接前趨。以下具體地給出樹的定義及樹的資料結構表示。

(一)樹的定義

樹是由乙個或多個結點組成的有限集合,其中:

⒈必有乙個特定的稱為根(root)的結點;

⒉剩下的結點被分成n>=0個互不相交的集合t1、t2、......tn,而且, 這些集合的每乙個又都是樹。樹t1、t2、......tn被稱作根的子樹(subtree)。

樹的遞迴定義如下:(1)至少有乙個結點(稱為根)(2)其它是互不相交的子樹

1.樹的度——也即是寬度,簡單地說,就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度,如上圖的樹,其度為3;樹中度為零的結點稱為葉結點或終端結點。

樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。

2.樹的深度——組成該樹各結點的最大層次,如上圖,其深度為4;

3.森林——指若干棵互不相交的樹的集合,如上圖,去掉根結點a,其原來的二棵子樹t1、t2、t3的集合就為森林;

4.有序樹——指樹中同層結點從左到右有次序排列,它們之間的次序不能互換,這樣的樹稱為有序樹,否則稱為無序樹。

5.樹的表示

樹的表示方法有許多,常用的方法是用括號:先將根結點放入一對圓括號中,然後把它的子樹由左至右的順序放入括號中,而對子樹也採用同樣的方法處理;同層子樹與它的根結點用圓括號括起來,同層子樹之間用逗號隔開,最後用閉括號括起來。如上圖可寫成如下形式:

(a(b(e(k,l),f),c(g),d(h(m),i,j)))

5. 2 二叉樹

1.二叉樹的基本形態:

二叉樹也是遞迴定義的,其結點有左右子樹之分,邏輯上二叉樹有五種基本形態:

(1)空二叉樹——(a);

(2)只有乙個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

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

注意:儘管二叉樹與樹有許多相似之處,但二叉樹不是樹的特殊情形。

2.兩個重要的概念:

(1)完全二叉樹——只有最下面的兩層結點度小於2,並且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹;

(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,則無右兒子。

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.普通樹轉換成二叉樹:凡是兄弟就用線連起來,然後去掉父親到兒子的連線,只留下父母到其第乙個子女的連線。

二叉樹很象一株倒懸著的樹,從樹根到大分枝、小分枝、直到葉子把資料聯絡起來,這種資料結構就叫做樹結構,簡稱樹。樹中每個分叉點稱為結點,起始結點稱為樹根,任意兩個結點間的連線關係稱為樹枝,結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的"雙親",結點的後趨結點稱為該結點的"子女"或"孩子",同一結點的"子女"之間互稱"兄弟"。

二叉樹:二叉樹是一種十分重要的樹型結構。它的特點是,樹中的每個結點最多只有兩棵子樹,即樹中任何結點的度數不得大於2。

二叉樹的子樹有左右之分,而且,子樹的左右次序是重要的,即使在只有一棵子樹的情況下,也應分清是左子樹還是右子樹。定義:二叉樹是結點的有限集合,這個集合或是空的,或是由乙個根結點和兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。

(三)完全二叉樹

對滿二叉樹,從第一層的結點(即根)開始,由下而上,由左及右,按順序結點編號,便得到滿二叉樹的乙個順序表示。據此編號,完全二叉樹定義如下:一棵具有n個結點,深度為k的二叉樹,當且僅當所有結點對應於深度為k的滿二叉樹中編號由1至n的那些結點時,該二叉樹便是完全二叉樹。

圖4是一棵完全二叉樹。

三、二叉樹的遍歷

遍歷是對樹的一種最基本的運算,所謂遍歷二叉樹,就是按一定的規則和順序走遍二叉樹的所有結點,使每乙個結點都被訪問一次,而且只被訪問一次。由於二叉樹是非線性結構,因此,樹的遍歷實質上是將二叉樹的各個結點轉換成為乙個線性序列來表示。

設l、d、r分別表示遍歷左子樹、訪問根結點和遍歷右子樹, 則對一棵二叉樹的遍歷有三種情況:dlr(稱為先根次序遍歷),ldr(稱為中根次序遍歷),lrd (稱為後根次序遍歷)。

(1)先序遍歷

訪問根;按先序遍歷左子樹;按先序遍歷右子樹

(2)中序遍歷

按中序遍歷左子樹;訪問根;按中序遍歷右子樹

(3)後序遍歷

按後序遍歷左子樹;按後序遍歷右子樹;訪問根

資料結構二叉樹的遍歷,C語言資料結構 二叉樹的遍歷

前序 根,左兒子,右兒子 中序 左兒子,根,右兒子 後序 左兒子,右兒子,根 首先是要牢記一上幾句話 比如這棵樹的中許遍歷,a有左兒子,先不訪問a,以此類推,直到d沒有左兒子,訪問d,然後訪問d的根b,然後應該訪問b的右兒子,但是b沒有,所以訪問b的根a,訪問完a以後訪問a的右子樹。先看c,c有左兒...

資料結構中二叉樹如何轉化成深林

將一棵二叉樹還原為樹或森林,具體方法如下 1 若某結點是其雙親的左孩子,則把該結點的右孩子 右孩子的右孩子 都與該結點的雙親結點用線連起來。2 刪掉原二叉樹中所有雙親結點與右孩子結點的連線。3 整理由 1 2 兩步所得到的樹或森林,使之結構層次分明。v 需要規定一下,比如左子樹是兒子,右子樹是弟弟,...

中序遞迴遍歷二叉樹的演算法?(資料結構)

include include define maxsize 100 typedef char elemtype typedef struct node bitnode j ch str j bitnode find bitnode b,elemtype x bitnode lchild bitno...