日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

C++關(guān)于樹的定義全面梳理_C 語言

作者：肩上風(fēng)騁 ? 更新時(shí)間： 2022-08-17 編程語言

概念

本文以一個(gè)簡(jiǎn)單的樹為例，如下圖，來記錄樹的一些概念。

樹

一種由n個(gè)節(jié)點(diǎn)組成的具有一定層次關(guān)系的有限數(shù)據(jù)集合。每個(gè)節(jié)點(diǎn)有0個(gè)或者n個(gè)子節(jié)點(diǎn)，有一個(gè)根節(jié)點(diǎn)（沒有前驅(qū)只有后繼），除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)，0個(gè)或多個(gè)后繼。

樹的葉子節(jié)點(diǎn)

只有一個(gè)前驅(qū)，沒有后繼的節(jié)點(diǎn)，為最外層的節(jié)點(diǎn)。葉子節(jié)點(diǎn)的度為0。

節(jié)點(diǎn)的度

節(jié)點(diǎn)擁有的子樹的數(shù)目。

分支結(jié)點(diǎn)

度不為0的結(jié)點(diǎn)。

樹的度

樹中結(jié)點(diǎn)的最大的度。

樹的高度

任意葉子節(jié)點(diǎn)距離根節(jié)點(diǎn)的最大深度。此文中樹的葉子節(jié)點(diǎn)為D、E、H，距離根節(jié)點(diǎn)的深度都為4，故高度為4。

樹的深度

即從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的行數(shù)。此文中樹的深度為4。

二叉樹

二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。

它有五種基本形態(tài)：

二叉樹可以是空集；

根可以有空的左子樹或右子樹；

或者左、右子樹皆為空。

二叉樹的特點(diǎn)

二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2i-1(i>=1)

深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k>=1）

包含n個(gè)結(jié)點(diǎn)的二叉樹的高度至少為(log2n)+1

滿二叉樹

高度為h，并且由2h-1個(gè)節(jié)點(diǎn)組成的二叉樹。

完全二叉樹

一棵二叉樹中，只有最下面兩層節(jié)點(diǎn)的度可以小于2，并且最下層的葉節(jié)點(diǎn)集中在靠左的若干位置上，這樣的二叉樹稱為完全二叉樹。

二叉查找樹

二叉查找樹又被稱為二叉搜索樹。設(shè)x為二叉查找樹中的一個(gè)結(jié)點(diǎn)，x結(jié)點(diǎn)包含關(guān)鍵字key，結(jié)點(diǎn)x的key值計(jì)為key[x]。如果y是x的左子樹中的一個(gè)結(jié)點(diǎn)，則key[y]<=key[x]；如果y是x的右子樹的一個(gè)結(jié)點(diǎn)，則key[y]>=key[x]。

特點(diǎn)：

1.若任意結(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。

2.任意結(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。

3.任意結(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

4.沒有鍵值相等的結(jié)點(diǎn)。

示例

下面直接上代碼，一個(gè)簡(jiǎn)單的樹的創(chuàng)建、遍歷輸出，葉子節(jié)點(diǎn)數(shù)，高度。

代碼實(shí)現(xiàn)

Tree.h

#pragma once
typedef struct MYTREE {
	char data;
	struct MYTREE* lChild;
	struct MYTREE* rChild;
}MyTree;
class Tree
{
public:
	Tree();
	~Tree();
	void CreateTree();
	void TraverseTree(MyTree *root);
	void GetLeafNode(MyTree *root,int &num);
	int GetTreeDepth(MyTree *root);
	void GetTreeNode(MyTree *root, int &num);
};

Tree.cpp

#include "Tree.h"
#include <iostream>
#include<algorithm>//max,min
using namespace std;
Tree::Tree()
{
}
Tree::~Tree()
{
}
void Tree::CreateTree()
{
	MyTree t1 = {'A',nullptr,nullptr};
	MyTree t2 = { 'B',nullptr,nullptr };
	MyTree t3 = { 'C',nullptr,nullptr };
	MyTree t4 = { 'D',nullptr,nullptr };
	MyTree t5 = { 'E',nullptr,nullptr };
	MyTree t6 = { 'F',nullptr,nullptr };
	MyTree t7 = { 'G',nullptr,nullptr };
	MyTree t8 = { 'H',nullptr,nullptr };
	t1.lChild = &t2;
	t1.rChild = &t6;
	t2.rChild = &t3;
	t3.lChild = &t4;
	t3.rChild = &t5;
	t6.rChild = &t7;
	t7.lChild = &t8;
	TraverseTree(&t1);
	cout << endl;
	int leafNum = 0;
	GetLeafNode(&t1,leafNum);
	cout << "leaf num: " << leafNum << endl;
	int treeDepth = GetTreeDepth(&t1);
	cout << "depth:" << treeDepth << endl;
	int nodeNum = 0;
	GetTreeNode(&t1,nodeNum);
	cout << "node num; " << nodeNum << endl;
}
void Tree::TraverseTree(MyTree *root)
{
	if (root == nullptr)
	{
		return;
	}
	TraverseTree(root->lChild);
	cout << root->data;
	TraverseTree(root->rChild);
}
void Tree::GetLeafNode(MyTree *root,int &num)
{
	if (root == nullptr)
	{
		return ;
	}
	if (root->lChild == nullptr && root->rChild == nullptr)
	{
		num++;
	}
	GetLeafNode(root->lChild,num);
	GetLeafNode(root->rChild,num);
}
int Tree::GetTreeDepth(MyTree * root)
{
	int num = 0;
	if (root == nullptr)
	{
		return num;
	}
	int lNum = GetTreeDepth(root->lChild);
	int rNum = GetTreeDepth(root->rChild);
	return max(lNum,rNum)+1;
}
void Tree::GetTreeNode(MyTree * root, int & num)
{
	if (root == nullptr)
	{
		return;
	}
	++num;
	GetTreeNode(root->lChild,num);
	GetTreeNode(root->rChild,num);
}

main.cpp

#include <iostream>
#include "Tree.h"
using namespace std;
void test() {
	Tree t;
	t.CreateTree();
}
int main()
{
	test();
	return 0;
}

開發(fā)環(huán)境

vs2017控制臺(tái)輸出程序。

運(yùn)行結(jié)果

原文鏈接：https://blog.csdn.net/blqzj214817/article/details/125403432

欄目分類
最近更新