当前位置：首页 -> 基础 -> c++编程基础

c/c++常用算法(5) -- 数据结构(树)

2014-11-24 07:10:56 · 作者: · 浏览: 0
标签: c/c 常用 算法 数据结构

一、树的定义和基本术语


1.树的定义

树(Tree)是n(n 0)个结点的有限集合T，若n=0时称为空树，否则：

⑴ 有且只有一个特殊的称为树的根(Root)结点；

⑵ 若n>1时，其余的结点被分为m(m>0)个互不相交的子集T1, T2, T3…Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。

这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成，如图6-1(a)所示。


2树的基本术语

⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。

⑵ 结点的度(degree)、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。


\


如图6-1(b)中结点A的度是3，结点B的度是2，结点M的度是0，树的度是3 。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPiAgICAgIKLHINK219MobGVmdCm94bXjoaK3x9K219O94bXjo7rK99bQtsjOqjC1xL3hteOzxs6q0rbX073hteMou/LW1bbLveG14ymho8/gttTTprXYo6y2yLK7zqowtcS94bXjs8bOqrfH0rbX073hteMou/K3x9bVtsu94bXju/K31tanveG14ymho7P9uPm94bXjzeKjrLfW1qe94bXj09azxs6qxNqyv73hteOhozwvcD4KPHA+ICAgIMjnzbw2LTEoYinW0L3hteNIoaJJoaJKoaJLoaJMoaJNoaJOysfSttfTveG146OstvjL+dPQxuTL/L3hteO2vMrHt9bWp73hteOhozwvcD4KPHA+PGJyPgo8L3A+CjxwPiAgICAgIKLIILqi19O94bXjoaLLq8fXveG146Gi0Na13L3hteM8L3A+CjxwPiAgICDSu7j2veG147XE19PK97XEuPmzxs6quMO94bXjtcS6otfTveG14yhjaGlsZCm78tfTveG146O7z+DTprXYo6y4w73htePKx8bkuqLX073hteO1xMurx9e94bXjKHBhcmVudCm78ri4veG146GjPC9wPgo8cD4gICAgICAgICDI5828Ni0xKGIp1tC94bXjQqGiQ6GiRMrHveG140G1xNfTveG146Ostvi94bXjQcrHveG140KhokOhokS1xLi4veG146O7wOAmIzIwMjg0O7XYveG140WhokbKx73hteNCtcTX073hteOjrL3hteNCyse94bXjRaGiRrXEuLi94bXjoaM8L3A+CjxwPs2s0rvLq8fXveG147XEy/nT0NfTveG147uls8bOqtDWtdy94bXjoaM8L3A+CjxwPiAgICAgICAgyOfNvDYtMShiKdbQveG140IgoaJDoaJEysfQ1rXcveG146O7veG140WhokbKx9DWtdy94bXjoaM8L3A+CjxwPjxicj4KPC9wPgo8cD4gICAgICCiySCy47TOoaLMw9DWtdy94bXjPC9wPgo8cD4gICAgICAgILnmtqjK99bQuPm94bXjtcSy47TOzqoxo6zG5NPgveG147XEsuO0zrXI09rG5Murx9e94bXjtcSy47TOvNMxoaM8L3A+CjxwPiAgICAgICAgyPTEs73htePU2rXabChsqFIxKbLjo6zU8sbk19O94bXj1Nq12mwmIzQzOzGy46GjPC9wPgo8cD4gICAgICAgIMurx9e94bXj1NrNrNK7suPJz7XEy/nT0L3hteO7pbPGzqrMw9DWtdy94bXjoaPI5828Ni0xKGIp1tC94bXjRaGiRqGiR6GiSKGiSaGiSqGjPC9wPgo8cD48YnI+CjwvcD4KPHA+ICAgICAgosogveG147XEsuO0zsK3vrahotfmz8ihotfTy+88L3A+CjxwPiAgICAgICAgtNO4+b3hteO/qsq8o6y1vbTvxLO94bXjcMv5vq25/bXEy/nT0L3hteOzyc6qveG143C1xLLjtM7Ct762KNPQx9LWu9PQ0rvM9SmhozwvcD4KPHA+ICAgICAgICC94bXjcLXEsuO0zsK3vrbJz7XEy/nT0L3hteOjqHCz/c3io6mzxs6qcLXE1+bPyChhbmNlc3RlcimhozwvcD4KPHA+ICAgICAgICDS1MSz0ru94bXjzqq4+bXE19PK99bQtcTIztLiveG147PGzqq4w73hteO1xNfTy++94bXjKGRlc2NlbnQpoaM8L3A+CjxwPjxicj4KPC9wPgo8cD4gICAgICCiy8r3tcTJ7rbIKGRlcHRoKaO6yvfW0L3hteO1xNfutPOy47TOJiMyMDU0MDujrNPWs8bOqsr3tcS437bIo6zI5828Ni0xKGIp1tDK97XEuN+2yM6qNKGjPC9wPgo8cD4gICAgICCizCDT0NDyyve6zc7e0PLK96O6ttTT2tK7v8PK96OsyPTG5NbQw7/Su7j2veG147XE19PK96OoyPTT0KOpvt/T0NK7tqi1xLTO0PKjrNTyuMPK97PGzqrT0NDyyvejrLfx1PKzxs6qzt7Q8sr3oaM8L3A+CjxwPiAgICAgIKLNya3B1ihmb3Jlc3Qpo7rKx20obahSMCm/w7ulsrvP4L27tcTK97XEvK+6z6Gjz9TIu6OsyPS9q9K7v8PK97XEuPm94bXjyb6z/aOsyqPT4LXE19PK977NubmzycHLya3B1qGjPC9wPgo8YnI+CjxwPjMgIMr3tcSx7cq+0M7KvTwvcD4KPHA+ICAgICAgosUgtbnQ/Mr3oaPKx9fus6PTw7XEse3KvtDOyr2jrMjnzbw2LTEoYimhozwvcD4KPHA+ICAgICAgosYgx7bM17yvus+ho8rH0rvQqbyvus+1xLyvzOWjrLbU09rIzrrOwb249ryvus+jrLvy1d+yu8/gvbujrLvy1d/Su7j2vK+6z7D8uqzB7dK7uPa8r7rPoaPNvDYtMihhKcrHzbw2LTEoYinK97XEx7bM17yvus/Qzsq9oaM8L3A+CjxwPiAgICAgIKLHILnj0uWx7dDOyr2ho828Ni0yKGIpysfK97XEuePS5bHt0M7KvaGjPC9wPgo8cD4gICAgICCiyCCwvMjrt6ix7cq+0M7KvaGjPC9wPgo8cD48YnI+CjwvcD4KPHA+ICAgyve1xLHtyr63vbeotcS24NH5u6/LtcP3wcvK973hubm1xNbY0qrQ1KGjPC9wPgo8YnI+CjxwPjxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/49/1_subnc__.jpg" alt="\">


二、树的抽象数据类型定义


ADT Tree{
    数据对象D：D是具有相同数据类型的数据元素的集合。
    数据关系R：若D为空集，则称为空树；
    ……
    基本操作：
    ……
} ADT Tree

三、二叉树


1 二叉树的定义

二叉树(Binarytree)是n(n≥0)个结点的有限集合。若n=0时称为空树，否则：

⑴有且只有一个特殊的称为树的根(Root)结点；

⑵若n>1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。

由此可知，二叉树的定义是递归的。


二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树结构。上节中引入的有关树的术语也都适用于二叉树。


2.二叉树的基本形态


二叉树有5种基本形态，如图6-3所示


\


满二叉树的特点：

◆ 基本特点是每一层上的结点数总是最大结点数。

◆ 满二叉树的所有的支结点都有左、右子树。

◆ 可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。


完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。

其中 2k-1 n 2k-1 。

完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。


完全二叉树的特点：

若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。


四、实现代码


Tree.h

#pragma once
#include 
  
   
#include 
   
     #include "stdio.h" #include 
    
      using namespace std; #define MANLEN 20 typedef char DATA; typedef struct CBT //定义二叉树的数据结构 { DATA data; struct CBT *left; struct CBT *right; }CBTType; class Tree { public: CBTType *InitTree(); //初始化 void AddTreeNode(CBTType *treeNode); //添加结点 CBTType *TreeFindNode(CBTType *treeNode,DATA data); //查找结点 CBTType *TreeLeftNode(CBTType *treeNode); //获得左子树 CBTType *TreeRightNode(CBTType *treeNode); //获得右子树 int TreeIsEmpty(CBTType *treeNode); //判断是否为空树 int TreeDepth(CBTType *treeNode); //计算二叉树深度 void ClearTree(CBTType *treeNode); //清空二叉树 void TreeNodeData(CBTType *p); //显示结点数据 void LevelTree(CBTType *treeNode,void (*TreeNodeData)(CBTType *p));//按层遍历 void DLRTree(CBTType *treeNode,void (*TreeNodeData)(CBTType *p)); //先序遍历 void LDRTree(CBTType *treeNode,void (*TreeNodeData)(CBTType *p)); //中序遍历 void LRDTree(CBTType *treeNode,void (*TreeNodeData)(CBTType *p)); //后序遍历 };
Tree.cpp 

#include "queue.h"
#include 
  
   


CBTType *Tree::InitTree()
{
	CBTType *node;

	if (node = (CBTType*)malloc(sizeof(CBTType)))
	{
		std::cout<<"请先输入一个根结点数据:\n";
		scanf("%c",&node->data);
		node->left = NULL;
		node->right = NULL;
		if (node != NULL)
		{
			return node;
		}
		else
		{
			return NULL;
		}
	}
	return NULL;
}

void Tree::AddTreeNode(CBTType *treeNode)
{
	CBTType *pnode,*parent;
	char data;
	char menusel;

	if (pnode = (CBTType*)malloc(sizeof(CBTType)))
	{
		std::cout<<"输入二叉树结点数据:\n";
		fflush(stdin);
		scanf("%c",&pnode->data);
		pnode->left = NULL;
		pnode->right = NULL;

		std::cout<<"输入该结点的父结点数据:\n";
		fflush(stdin);
		scanf("%c",&data);

		parent = TreeFindNode(treeNode, data);

		if (!parent)
		{
			std::cout<<"未找到该父结点!\n";
			free(pnode);
			return;
		}
		std::cout<<"1.添加该结点到左子树\n2.添加该结点到右子树\n";

		do
		{
			//scanf("%s",&menusel);
			menusel = getch();
			menusel -='0';
			if (menusel == 1 || menusel == 2)
			{
				if (parent == NULL)
				{
					std::cout<<"不存在父结点,请先设置父结点!\n";
				}
				else
				{
					switch (menusel)
					{
					case 1:
						if (parent->left)
						{
							std::cout<<"左子树结点不为空!\n";
						}
						else
						{
							parent->left = pnode;
						}
						break;

					case 2:
						if (parent->right)
						{
							std::cout<<"右子树结点不为空!\n";
						}
						else
						{
							parent->right = pnode;
						}
						break;   
					default:
						std::cout<<"无效参数!\n";
					}
				}
			}
		} while (menusel != 1 && menusel != 2);
	}
}


CBTType *Tree::TreeFindNode(CBTType *treeNode, DATA data)
{
	CBTType *ptr;

	if (treeNode == NULL)
	{
		return NULL;
	}
	else
	{
		if (treeNode->data == data)
		{
			return  treeNode;
		}
		else
		{
			if (ptr = TreeFindNode(treeNode->left, data))
			{
				return ptr;
			}
			else if(ptr =TreeFindNode(treeNode->right, data))
			{
				return ptr;
			}
			else
			{
				return NULL;
			}   
		}
	}
}


CBTType *Tree::TreeLeftNode(CBTType *treeNode)
{
	if (treeNode)
	{
		return treeNode->left;
	}
	else
	{
		return NULL;
	}
}

CBTType *Tree::TreeRightNode(CBTType *treeNode)
{
	if (treeNode)
	{
		return treeNode->right;
	}
	else
	{
		return NULL;
	}
}

int Tree::TreeIsEmpty(CBTType *treeNode)
{
	if (treeNode)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int Tree::TreeDepth(CBTType *treeNode)
{
	int depleft,depright;

	if (treeNode == NULL)
	{
		return 0;
	}
	else
	{
		depleft = TreeDepth(treeNode->left);
		depright = TreeDepth(treeNode->right);
		if (depleft > depright)
		{
			return depleft + 1;
		}
		else
		{
			return depright + 1;
		}
	}
}

void Tree::ClearTree(CBTType *treeNode)
{
	if (treeNode)
	{
		ClearTree(treeNode->left);
		ClearTree(treeNode->right);
		free(treeNode);
		treeNode = NULL;
	}
}

void Tree::TreeNodeData(CBTType *p)
{
	std::cout<
   
    data<<" "; } void Tree::LevelTree(CBTType *treeNode, void (*TreeNodeData)(CBTType *)) { CBTType *p; CBTType *q[MANLEN]; int head = 0,tail = 0; if (treeNode) { tail = (tail + 1) % MANLEN; q[tail] = treeNode; } while (head != tail) { head = (head + 1) % MANLEN; p = q[head]; TreeNodeData(p); if (p->left != NULL) { tail = (tail + 1) % MANLEN; q[tail] = p->left; } if (p->right != NULL) { tail = (tail + 1) % MANLEN; q[tail] = p->right; } } } void Tree::DLRTree(CBTType *treeNode, void (*TreeNodeData)(CBTType *p)) { if (treeNode) { TreeNodeData(treeNode); DLRTree(treeNode->left, TreeNodeData); DLRTree(treeNode->right,TreeNodeData); } } void Tree::LDRTree(CBTType *treeNode, void (*TreeNodeData)(CBTType *)) { if (treeNode) { LDRTree(treeNode->left, TreeNodeData); TreeNodeData(treeNode); LDRTree(treeNode->right, TreeNodeData); } } void Tree::LRDTree(CBTType *treeNode, void (*TreeNodeData)(CBTType *)) { if (treeNode) { LRDTree(treeNode->left, TreeNodeData); LRDTree(treeNode->right, TreeNodeData); TreeNodeData(treeNode); } }

main.cpp 

#include 
  
   
using namespace std;
#include "Tree.h"
#include 
   
     #include 
    
      using namespace std; void TreeNodeData2(CBTType *p) { printf("%c",p->data); } int main() { CBTType *root = NULL; char menusel; Tree *myTree = new Tree(); void(*TreeNodeData1)(CBTType *p); TreeNodeData1 =TreeNodeData2; //设置根结点 root = myTree->InitTree(); do { std::cout<<"请输入添加二叉树的结点\n"; std::cout<<"输入0退出\n"; std::cout<<"1.添加二叉树的结点\n"; menusel = getch(); switch (menusel) { case '1': myTree->AddTreeNode(root); break; case '0': break; default: break; } } while (menusel != '0'); //遍历 do { std::cout<<"请选择遍历二叉树，输入0退出\n"; std::cout<<"1.先序遍历 DLR \t"<<"2.中序遍历 LDR\n"; std::cout<<"3.后序遍历 LRD \t"<<"4.按层遍历 LDR\n"; scanf("%c",&menusel); switch (menusel) { case '0': break; case '1': std::cout<<"1.先序遍历 DLR的结果:"; myTree->DLRTree(root, TreeNodeData1); std::cout<<"\n"; break; case '2': std::cout<<"2.中序遍历 LDR的结果:"; myTree->LDRTree(root, TreeNodeData1); std::cout<<"\n"; break; case '3': std::cout<<"3.后序遍历 LRD的结果:"; myTree->LRDTree(root, TreeNodeData1); std::cout<<"\n"; break; case '4': std::cout<<"4.后序遍历 LRD的结果:"; myTree->LevelTree(root, TreeNodeData1); std::cout<<"\n"; break; default: ; } } while (menusel != '0'); printf("\n二叉树深度为:%d\n",myTree->TreeDepth(root)); myTree->ClearTree(root); root = NULL; delete myTree; cout << "helloWorld!"; system("pause"); return 0; }

演示效果图:





参考书籍:《C/C++常用算法手册》 《数据结构-清华大学严蔚敏》