??專欄【數(shù)據(jù)結(jié)構(gòu)】

??喜歡的詩句：更喜岷山千里雪 三軍過后盡開顏。

??音樂分享【勛章】

大一同學(xué)小吉，歡迎并且感謝大家指出我的問題??

目錄

?樹

??????定義

???????注意

??樹的基本術(shù)語

?二叉樹

??????定義

??二叉樹和樹的區(qū)別

??????二叉樹的性質(zhì)

?滿二叉樹

?完全二叉樹

??遍歷二叉樹

??先序遍歷二叉樹

??中序遍歷二叉樹

??后序遍歷二叉樹

??構(gòu)建二叉樹

??算法步驟

??代碼

??復(fù)制二叉樹

??算法步驟

??代碼

??計算二叉樹的深度

??算法步驟

??代碼

??統(tǒng)計二叉樹中結(jié)點的總數(shù)

??算法步驟

??代碼

??統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)

??算法步驟

??代碼

??完整代碼?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-451812.html

?

?樹

??????定義

樹是n（n>=0）個結(jié)點的有限集

n=0：稱為空樹

n>0：稱為非空樹

?對于非空樹，有下面兩個特點

(1)有且只有一個稱為根的結(jié)點

(2)除根節(jié)點之外的其余結(jié)點可以分為m(m>0)個互不相交的有限集，對于每一個有限集本身又是一棵樹，并且稱為根的子樹

樹可以有多種表示方法，如下圖所示?

???????注意

如下圖所示

?

??樹的基本術(shù)語

結(jié)點：樹的一個獨立單元（比如上圖的ABCD）

結(jié)點的度：結(jié)點擁有的子樹（比如上圖中，A的度為3，B的度為2）

樹的度：樹內(nèi)各結(jié)點度的最大值（比如上圖的樹的度為3）

葉子（終端結(jié)點）：度為0的結(jié)點

層次：結(jié)點的層次從根開始定義，根為第一層，根的孩子為第二層

樹的深度（高度）：樹中結(jié)點的最大層次

森林：m棵互不相交的樹的集合。對于樹的每個結(jié)點而言，其子樹的集合就是森林

?二叉樹

??????定義

樹是n（n>=0）個結(jié)點的有限集

n=0：稱為空樹

n>0：稱為非空樹

?對于非空樹，有下面兩個特點

(1)有且只有一個稱為根的結(jié)點

(2)除根節(jié)點之外的其余結(jié)點可以分為2個互不相交的子集，分別稱為T的左子樹T1和右子樹T2，且T1T2都是二叉樹

??二叉樹和樹的區(qū)別

??二叉樹中不存在度>2的結(jié)點??

二叉樹的左右子樹有左右之分，不能隨意顛倒

二叉樹也有多種表示方法，如下圖所示

?

??????二叉樹的性質(zhì)

??第i層上至多有2^(i-1)（i>=1）個結(jié)點

??深度為k的二叉樹至多有2^k-1（k>=1）個結(jié)點

??對于任何一顆二叉樹T，如果其終端結(jié)點樹為n0，度為2的結(jié)點樹為n2

那么n0=n2+1

?滿二叉樹

深度為k且有2^k-1個結(jié)點的二叉樹，每一層的結(jié)點數(shù)都是最大結(jié)點數(shù)

?完全二叉樹

?

深度為k，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)每一個結(jié)點都與深度為k的滿二叉樹?中編號從1到n的結(jié)點一一對應(yīng)時，為完全二叉樹

文末有完整代碼

?

??遍歷二叉樹

??定義

typedef struct BiNode{				
    char data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

??先序遍歷二叉樹

操作定義如下：若二叉樹為空，則操作為空；否則
(1)訪問根結(jié)點；
(2)先序遍歷左子樹；
(3)先序遍歷右子樹。

void preorder_traversal(BiTree root) {
    if (!root) {
        return;
    }

    cout << root->data << " "; // 訪問根節(jié)點
    preorder_traversal(root->lchild); // 遞歸訪問左子樹
    preorder_traversal(root->rchild); // 遞歸訪問右子樹
}

??中序遍歷二叉樹

操作定義如下：若二叉樹為空，則操作為空；否則
(1)中序遍歷左子樹；
(2)訪問根結(jié)點；
(3)中序遍歷右子樹。

void inorder_traversal(BiTree root) {
    if (!root) {
        return;
    }

    inorder_traversal(root->lchild); // 遞歸訪問左子樹
    cout << root->data << " "; // 訪問根節(jié)點
    inorder_traversal(root->rchild); // 遞歸訪問右子樹
}

??后序遍歷二叉樹

操作定義如下：若二叉樹為空，則操作為空；否則
(1)后序遍歷左子樹；
(2)后序遍歷右子樹；
(3)訪問根結(jié)點；

void postorder_traversal(BiTree root) {
    if (!root) {
        return;
    }

    postorder_traversal(root->lchild); // 遞歸訪問左子樹
    postorder_traversal(root->rchild); // 遞歸訪問右子樹
    cout << root->data << " "; // 訪問根節(jié)點
}

??構(gòu)建二叉樹

法一：

比如根據(jù)? ABC##DE#G##F###? 這一段來構(gòu)建

??算法步驟

1.讀取字符序列，讀入字符ch

2.如果ch是“#”，表明該二叉樹為空樹，即T為NULL，否則執(zhí)行下面的操作

（1）申請一個內(nèi)存空間T

（2）將ch賦給T->data

（3）遞歸創(chuàng)建T的左子樹

（4）遞歸創(chuàng)建T的右子樹

??代碼

void CreateBiTree(BiTree &T){	
	
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			
	else{							
		T=new BiTNode;
		T->data=ch;					//生成根結(jié)點
		CreateBiTree(T->lchild);	//遞歸創(chuàng)建左子樹
		CreateBiTree(T->rchild);	//遞歸創(chuàng)建右子樹
	}								
}					

法二：

 // 構(gòu)建二叉樹
    BiTree root = new BiNode{'A', nullptr, nullptr};
    root->lchild = new BiNode{'B', nullptr, nullptr};
    root->lchild->lchild = new BiNode{'C', nullptr, nullptr};
    root->lchild->rchild = new BiNode{'D', nullptr, nullptr};
    root->lchild->rchild->lchild = new BiNode{'E', nullptr, nullptr};
    root->lchild->rchild->lchild->rchild = new BiNode{'G', nullptr, nullptr};
    root->lchild->rchild->rchild = new BiNode{'F', nullptr, nullptr};

??復(fù)制二叉樹

??算法步驟

1.為空樹，遞歸結(jié)束

2.不為空樹，那么執(zhí)行下面的操作

（1）申請一個新結(jié)點空間，復(fù)制根節(jié)點

（2）遞歸復(fù)制左子樹

（3）遞歸復(fù)制右子樹

??代碼

void Copy(BiTree T,BiTree &NewT)
{
	if(T==NULL){
		NweT=NULL;
		return;
	}else{
		NewT=new BiTree;		//復(fù)制根節(jié)點
		NewT->data=T->data;
		Copy(T->lchild,NewT->lchild);
		Copy(T->rchild,NewT->rchild);
	}
}

??計算二叉樹的深度

??算法步驟

1.為空樹，遞歸結(jié)束

2.不為空樹，那么執(zhí)行下面的操作

（1）遞歸計算左子樹的深度為m

（2）遞歸計算右子樹的深度為n

（3）如果m>n，那么二叉樹深度為m+1，否則為n+1

??代碼

int Depth(BiTree T)
{ 
	int m,n;
	if(T == NULL ) return 0;        //如果是空樹，深度為0，遞歸結(jié)束
	else 
	{							
		m=Depth(T->lchild);			//遞歸計算左子樹的深度記為m
		n=Depth(T->rchild);			//遞歸計算右子樹的深度記為n
		if(m>n) return(m+1);		//二叉樹的深度為m 與n的較大者加1
		else return (n+1);
		//+1，所以可以計算出來
	}
}

??統(tǒng)計二叉樹中結(jié)點的總數(shù)

??算法步驟

如果是空樹，那么結(jié)點個數(shù)為0，遞歸結(jié)束

否則，結(jié)點個數(shù)=左子樹結(jié)點個數(shù)+右子樹結(jié)點個數(shù)+1

??代碼

int NodeCount(BiTree T)
{
     if(T==NULL) return 0;  			// 如果是空樹，則結(jié)點個數(shù)為0，遞歸結(jié)束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否則結(jié)點個數(shù)為左子樹的結(jié)點個數(shù)+右子樹的結(jié)點個數(shù)+1
     
     //+1，所以可以計算出來//
} 

??統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)

??算法步驟

如果是空樹，那么結(jié)點個數(shù)為0，遞歸結(jié)束

否則，遍歷到NULL，即葉子節(jié)點

??代碼

int LeafCount(BiTree T){
 	if(T==NULL) 	//如果是空樹返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是葉子結(jié)點返回1
		
		// 1，所以可以計算出來
		
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

??完整代碼?

#include<iostream>
using namespace std;
typedef struct BiNode{				
	char data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;


void CreateBiTree(BiTree &T){	
	
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			
	else{							
		T=new BiTNode;
		T->data=ch;					//生成根結(jié)點
		CreateBiTree(T->lchild);	//遞歸創(chuàng)建左子樹
		CreateBiTree(T->rchild);	//遞歸創(chuàng)建右子樹
	}								
}									


void PreOrderTraverse(BiTree T)
{  
   if (T) {
      cout<<T->data;            // 訪問結(jié)點
      PreOrderTraverse(T->lchild); // 遍歷左子樹
      PreOrderTraverse(T->rchild);// 遍歷右子樹  
   }
}



void InOrderTraverse(BiTree T){  
	
	if(T){
		InOrderTraverse(T->lchild);
		cout << T->data;
		InOrderTraverse(T->rchild);
	}
}


void PostOrderTraverse(BiTree T)
{ 
   if (T) {
      PostOrderTraverse(T->lchild); // 遍歷左子樹
      PostOrderTraverse(T->rchild);// 遍歷右子樹
      cout << T->data;           // 訪問結(jié)點
    }
}



int NodeCount(BiTree T)
{
     if(T==NULL) return 0;  			// 如果是空樹，則結(jié)點個數(shù)為0，遞歸結(jié)束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否則結(jié)點個數(shù)為左子樹的結(jié)點個數(shù)+右子樹的結(jié)點個數(shù)+1
     
     //+1，所以可以計算出來//
} 


//計算二叉樹中葉子結(jié)點的個數(shù)
int LeafCount(BiTree T){
 	if(T==NULL) 	//如果是空樹返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是葉子結(jié)點返回1
		
		// 1，所以可以計算出來
		
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}


//計算二叉樹的深度	
int Depth(BiTree T)
{ 
	int m,n;
	if(T == NULL ) return 0;        //如果是空樹，深度為0，遞歸結(jié)束
	else 
	{							
		m=Depth(T->lchild);			//遞歸計算左子樹的深度記為m
		n=Depth(T->rchild);			//遞歸計算右子樹的深度記為n
		if(m>n) return(m+1);		//二叉樹的深度為m 與n的較大者加1
		else return (n+1);
		//+1，所以可以計算出來
	}
}

int main(){
	BiTree tree;
	int nodecount=0,leafcount=0,depth=0;
	cout<<"請輸入建立二叉鏈表的序列：\n";
	CreateBiTree(tree);
	cout<<endl;
	cout<<"先序遍歷的結(jié)果為：\n";
	PreOrderTraverse(tree);
	cout<<endl;
	cout<<"中序遍歷的結(jié)果為：\n";
	InOrderTraverse(tree);
	cout<<endl;
	cout<<"后序遍歷的結(jié)果為：\n";
	PostOrderTraverse(tree);
	cout<<endl;
	cout<<"該二叉樹中結(jié)點總數(shù)為：";
	cout<<NodeCount(tree)<<endl;
	cout<<"該二叉樹中葉子結(jié)點總數(shù)為：";
	cout<<LeafCount(tree)<<endl;
	cout<<"該二叉樹的深度為：";
	cout<<Depth(tree)<<endl;
	return 0;
}

??如果大家有不明白的地方，或者文章有問題，歡迎大家在評論區(qū)討論，指正???

?

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】樹，二叉樹，滿二叉樹，完全二叉樹的定義和二叉樹的基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！