数据结构—无序树
程序员文章站
2022-10-03 12:35:22
基本术语: 节点的度:书中某一节点拥有的子节点数量。 数的度:该树中所有节点的度的最大值。 叶节点(终端节点):度为零的节点。 分支节点(非终端节点):度不为零的节点。 根节点(开始节点):树中的第一个节点。 内部节点:树中除了根节点之外的节点。 节点的层数:若根节点层数为1,根节点的第n代子节点的 ......
基本术语:
节点的度:书中某一节点拥有的子节点数量。
数的度:该树中所有节点的度的最大值。
叶节点(终端节点):度为零的节点。
分支节点(非终端节点):度不为零的节点。
根节点(开始节点):树中的第一个节点。
内部节点:树中除了根节点之外的节点。
节点的层数:若根节点层数为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; }
测试结果: