数据结构—无序树
2018-06-17 21:00:40来源：未知 阅读 ()
基本术语：
节点的度：书中某一节点拥有的子节点数量。
数的度：该树中所有节点的度的最大值。
叶节点（终端节点）:度为零的节点。
分支节点（非终端节点）:度不为零的节点。
根节点（开始节点）：树中的第一个节点。
内部节点：树中除了根节点之外的节点。
节点的层数：若根节点层数为1，根节点的第n代子节点的层数为n。
树的高度：书中的节点的最大层数。
有序树和无序树：若树中某一节点的子节点无序，则该树为无序树，否则为有序树。
森林：去掉一棵树的根节点后得到的n棵树。
树的特点：
1.树是一种很基础很重要的非线性结构。
2.除表头（树根）和表尾（叶节点）外，任何一个节点只有一个直接前驱，但有多个直接后继。
3.树是数据的有限集，树分为空树和非空树。
非空树：有且只有一个根节点。若根节点的子节点大于1，可以理解为这棵非空树有m棵相互独立的非空树组成。
4.树的递归特性（★★★）：一颗非空树有若干子树组成，每一棵子树又由更小的子组成。
C++实现：
[MyTree.h]：无序树类模板头文件
#pragma once
template<class T>
class MyTree
{
private:
struct TreeNode //定义私有，不让用户使用
{
T data; //数据域，可以多个数据
//指针域
TreeNode *parent; //节点的父指针
TreeNode *child; //子指针
TreeNode *brother; //兄弟指针 兄弟之间逐级管理
};
TreeNode *pRoot; //根节点
public:
MyTree();
~MyTree();
void clear();
void insertNode(const T& parentData, const T& insertData, bool insertChild = true); //默认插入为子节点
//bool isFind(const T& findData);
void preOrderPrint(TreeNode *root /*= pRoot*/); //前序（前根）遍历
void posOrderPrint(TreeNode *root /*= pRoot*/); //前序（后根）遍历
void inOrderPrint(TreeNode *root /*= pRoot*/); //中序（中根）遍历
TreeNode* getTreeRoot();
private:
void _clear(TreeNode *root); //用于clear（）函数的实现，不提供接口
TreeNode* _find(TreeNode *root, const T& findData);
};
template<class T>
typename MyTree<T>::TreeNode* MyTree<T>::getTreeRoot()
{
return pRoot;
}
template<class T>
void MyTree<T>::inOrderPrint(TreeNode *root /*= pRoot*/)
{
if (!root)
return;
inOrderPrint(root->child);
std::cout << root->data << " ";
inOrderPrint(root->brother);
}
template<class T>
void MyTree<T>::posOrderPrint(TreeNode *root /*= pRoot*/)
{
if (!root)
return;
posOrderPrint(root->child);
posOrderPrint(root->brother);
std::cout << root->data << " ";
}
template<class T>
void MyTree<T>::preOrderPrint(TreeNode *root /*= pRoot*/)
{
if (!root)
return;
std::cout << root->data << " ";
preOrderPrint(root->child);
preOrderPrint(root->brother);
}
template<class T>
void MyTree<T>::insertNode(const T& parentData, const T& insertData, bool insertChild /*= true*/)
{
TreeNode *tempInsertNode = new TreeNode; //生成一个待插入的节点
tempInsertNode->data = insertData;
tempInsertNode->parent = NULL;
tempInsertNode->child = NULL;
tempInsertNode->brother = NULL;
if (pRoot) //判断树是否为空
{
TreeNode *findNode = _find(pRoot, parentData); //找到插入位置
if (findNode)
{//找到了插入位置
if (insertChild)
{//在子节点插入
TreeNode *temp = findNode->child;
if (temp)
{
while (temp->brother)
temp = temp->brother;
temp->brother = tempInsertNode;
tempInsertNode->parent = findNode;
}
else
{
findNode->child = tempInsertNode;
tempInsertNode->parent = findNode;
}
}
else
{//在兄弟节点插入
if (findNode->brother)
{
TreeNode *tempNode = findNode->brother;
while (tempNode->brother)
tempNode = tempNode->brother;
tempNode->brother = tempInsertNode;
tempInsertNode->parent = tempNode->parent;
}
else
{
//没有兄弟节点
findNode->brother = tempInsertNode;
tempInsertNode->parent = findNode->parent;
}
}
}
else
{//如果没有找到插入位置 设计为插入在末尾
std::cout << "can not find the parent,insert the data in the end" << std::endl;
TreeNode *temp = pRoot;
while (temp->child)
temp = temp->child;
temp->child = tempInsertNode;
tempInsertNode->parent = temp;
}
}
else
{//树为空的情况
// TreeNode *temp = new TreeNode;
// temp->data = insertData;
// temp->parent = NULL;
// inNode->child = inNode->brother = NULL;
pRoot = tempInsertNode;
}
}
template<class T>
typename MyTree<T>::TreeNode * MyTree<T>::_find(TreeNode *root, const T& findData)
{
if (root) /*递归结束条件 传入的的指针为空 例如判断叶节点是 将叶子节点的子节点传入递归函数，
不满足条件直接返回空*/
{
//先判断本节点 在判断子节点 最后判断兄弟节点 找到直接返回 不继续找
if (root->data == findData) //判断当前节点是否为 需要找的节点
return root;
TreeNode * temp = _find(root->child, findData);
if (temp)
return temp;
if (temp = _find(root->brother, findData))
return temp;
}
return NULL; //若没有找到 返回为空
}
template<class T>
void MyTree<T>::_clear(TreeNode *root)
{
//用递归删除所有节点 树的递归特性
if (root)
{
_clear(root->child);
_clear(root->brother); //先删除兄弟和先删除儿子一样
delete[]root; //必须先删除兄弟和儿子后才能删除自己
root = nullptr; //所有内存被释放后 指针置空
}
}
template<class T>
void MyTree<T>::clear()
{
_clear(pRoot); //不需要再进行判空 ，_clear()中会判断
}
template<class T>
MyTree<T>::~MyTree()
{
clear();
}
template<class T>
MyTree<T>::MyTree()
{
pRoot = nullptr;
}
代码测试：
// 无序树.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "MyTree.h"
#include<iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
MyTree<int> tree;
std::cout << "tree:" << endl;;
tree.insertNode(1, 1);
cout << 1 << '\n' << '|' << endl;;
tree.insertNode(1, 2, 1);
tree.insertNode(2, 5, 0);
tree.insertNode(2, 9, 0);
cout << 2 << "—" << 5<<"— —"<<9<<endl;
cout << '|' << " " << "|" <<" "<<"|"<< endl;
tree.insertNode(2, 3, 1);
tree.insertNode(5, 6, 1);
tree.insertNode(6, 7, 0);
tree.insertNode(9, 10, 1);
cout << 3 << " " << 6 << "—" << 7 <<" "<< 10 << endl;
cout << "|" << " " << "|" << endl;
tree.insertNode(3, 4, 1);
tree.insertNode(7, 8, 1);
cout << 4 << " " << 8 << "\n\n"<<endl;
std::cout << "前序遍历：";
tree.preOrderPrint(tree.getTreeRoot());
std::cout << std::endl;
std::cout << "后序遍历：";
tree.posOrderPrint(tree.getTreeRoot());
std::cout << std::endl;
std::cout << "中序遍历：";
tree.inOrderPrint(tree.getTreeRoot());
std::cout << std::endl;
std::cin.get();
return 0;
}
测试结果：
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 数据结构之顺序表的实现 2020-04-06
- 第五章 继承与派生 2020-04-04
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
