节点的度：书中某一节点拥有的子节点数量。

数的度：该树中所有节点的度的最大值。

叶节点（终端节点）:度为零的节点。

分支节点（非终端节点）:度不为零的节点。

根节点（开始节点）：树中的第一个节点。

内部节点：树中除了根节点之外的节点。

节点的层数：若根节点层数为1，根节点的第n代子节点的层数为n。

树的高度：书中的节点的最大层数。

有序树和无序树：若树中某一节点的子节点无序，则该树为无序树，否则为有序树。

森林：去掉一棵树的根节点后得到的n棵树。

1.树是一种很基础很重要的非线性结构。

2.除表头（树根）和表尾（叶节点）外，任何一个节点只有一个直接前驱，但有多个直接后继。

3.树是数据的有限集，树分为空树和非空树。　

　　非空树：有且只有一个根节点。若根节点的子节点大于1，可以理解为这棵非空树有m棵相互独立的非空树组成。

4.树的递归特性（★★★）：一颗非空树有若干子树组成，每一棵子树又由更小的子组成。

 

C++实现：

[MyTree.h]：无序树类模板头文件

  1. #pragma once
  3. template<class T>
  4. class MyTree
  5. {
  6. private:
  7.     struct TreeNode  //定义私有，不让用户使用
  8.     {
  9.         T data;  //数据域，可以多个数据
  10.         //指针域
  11.         TreeNode *parent;   //节点的父指针
  12.         TreeNode *child;    //子指针
  13.         TreeNode *brother;    //兄弟指针  兄弟之间逐级管理
  14.     };
  15.     TreeNode *pRoot;   //根节点
  17. public:
  18.     MyTree();
  19.     ~MyTree();
  20.     void clear();
  21.     void insertNode(const T& parentData, const T& insertData, bool insertChild = true); //默认插入为子节点
  22.     //bool isFind(const T& findData);
  23.     void preOrderPrint(TreeNode *root /*= pRoot*/);  //前序（前根）遍历
  24.     void posOrderPrint(TreeNode *root /*= pRoot*/);  //前序（后根）遍历
  25.     void inOrderPrint(TreeNode *root  /*= pRoot*/);   //中序（中根）遍历    
  26.     TreeNode* getTreeRoot();
  27. private:
  28.     void _clear(TreeNode *root);        //用于clear（）函数的实现，不提供接口
  29.     TreeNode* _find(TreeNode *root, const T& findData);
  30. };
  32. template<class T>
  33. typename MyTree<T>::TreeNode* MyTree<T>::getTreeRoot()
  34. {
  35.     return pRoot;
  36. }
  38. template<class T>
  39. void MyTree<T>::inOrderPrint(TreeNode *root /*= pRoot*/)
  40. {
  41.     if (!root)
  42.         return;
  43.     inOrderPrint(root->child);
  44.     std::cout << root->data << " ";
  45.     inOrderPrint(root->brother);
  46. }
  48. template<class T>
  49. void MyTree<T>::posOrderPrint(TreeNode *root /*= pRoot*/)
  50. {
  51.     if (!root)
  52.         return;
  53.     posOrderPrint(root->child);
  54.     posOrderPrint(root->brother);
  55.     std::cout << root->data << " ";
  56. }
  58. template<class T>
  59. void MyTree<T>::preOrderPrint(TreeNode *root /*= pRoot*/)
  60. {
  61.     if (!root)
  62.         return;
  63.     std::cout << root->data << " ";
  64.     preOrderPrint(root->child);
  65.     preOrderPrint(root->brother);
  66. }
  68. template<class T>
  69. void MyTree<T>::insertNode(const T& parentData, const T& insertData, bool insertChild /*= true*/)
  70. {
  71.     TreeNode *tempInsertNode = new TreeNode;    //生成一个待插入的节点
  72.     tempInsertNode->data = insertData;
  73.     tempInsertNode->parent = NULL;
  74.     tempInsertNode->child = NULL;
  75.     tempInsertNode->brother = NULL;
  77.     if (pRoot)  //判断树是否为空
  78.     {
  79.         TreeNode *findNode = _find(pRoot, parentData);    //找到插入位置
  80.         if (findNode)
  81.         {//找到了插入位置
  82.             if (insertChild)
  83.             {//在子节点插入
  84.                 TreeNode *temp = findNode->child;
  85.                 if (temp)
  86.                 {
  87.                     while (temp->brother)
  88.                         temp = temp->brother;
  89.                     temp->brother = tempInsertNode;
  90.                     tempInsertNode->parent = findNode;
  91.                 }
  92.                 else
  93.                 {
  94.                     findNode->child = tempInsertNode;
  95.                     tempInsertNode->parent = findNode;
  96.                 }
  97.             }
  98.             else
  99.             {//在兄弟节点插入
  100.                 if (findNode->brother)
  101.                 {
  102.                     TreeNode *tempNode = findNode->brother;
  103.                     while (tempNode->brother)
  104.                         tempNode = tempNode->brother;
  105.                     tempNode->brother = tempInsertNode;
  106.                     tempInsertNode->parent = tempNode->parent;
  107.                 }
  108.                 else
  109.                 {
  110.                     //没有兄弟节点
  111.                     findNode->brother = tempInsertNode;
  112.                     tempInsertNode->parent = findNode->parent;
  113.                 }
  114.             }
  115.         }
  116.         else
  117.         {//如果没有找到插入位置  设计为插入在末尾
  118.             std::cout << "can not find the parent,insert the data in the end" << std::endl;
  119.             TreeNode *temp = pRoot;
  120.             while (temp->child)
  121.                 temp = temp->child;
  122.             temp->child = tempInsertNode;
  123.             tempInsertNode->parent = temp;
  124.         }
  125.     }
  126.     else
  127.     {//树为空的情况
  128.         //         TreeNode *temp = new TreeNode;
  129.         //         temp->data = insertData;
  130.         //         temp->parent = NULL;
  131.         //         inNode->child = inNode->brother = NULL;
  132.         pRoot = tempInsertNode;
  133.     }
  134. }
  136. template<class T>
  137. typename MyTree<T>::TreeNode * MyTree<T>::_find(TreeNode *root, const T& findData)
  138. {
  139.     if (root)    /*递归结束条件  传入的的指针为空  例如判断叶节点是  将叶子节点的子节点传入递归函数，
  140.         不满足条件直接返回空*/
  141.     {
  142.         //先判断本节点 在判断子节点  最后判断兄弟节点 找到直接返回 不继续找
  143.         if (root->data == findData)        //判断当前节点是否为 需要找的节点
  144.             return root;
  145.         TreeNode * temp = _find(root->child, findData);
  146.         if (temp)
  147.             return temp;
  148.         if (temp = _find(root->brother, findData))
  149.             return temp;
  150.     }
  151.     return NULL;    //若没有找到  返回为空
  152. }
  154. template<class T>
  155. void MyTree<T>::_clear(TreeNode *root)
  156. {
  157.     //用递归删除所有节点   树的递归特性
  158.     if (root)
  159.     {
  160.         _clear(root->child);
  161.         _clear(root->brother);  //先删除兄弟和先删除儿子一样
  162.         delete[]root;        //必须先删除兄弟和儿子后才能删除自己
  163.         root = nullptr;        //所有内存被释放后 指针置空
  164.     }
  165. }
  167. template<class T>
  168. void MyTree<T>::clear()
  169. {
  170.     _clear(pRoot);  //不需要再进行判空 ，_clear()中会判断
  171. }
  173. template<class T>
  174. MyTree<T>::~MyTree()
  175. {
  176.     clear();
  177. }
  179. template<class T>
  180. MyTree<T>::MyTree()
  181. {
  182.     pRoot = nullptr;
  183. }

代码测试：

 

  1. // 无序树.cpp : 定义控制台应用程序的入口点。
  2. //
  3. #include "stdafx.h"
  4. #include "MyTree.h"
  5. #include<iostream>
  6. using namespace std;
  8. int _tmain(int argc, _TCHAR* argv[])
  9. {
  10.     MyTree<int> tree;
  11.     std::cout << "tree:" << endl;;
  13.     tree.insertNode(1, 1);
  14.     cout << 1 << '\n' << '|' << endl;;
  16.      tree.insertNode(1, 2, 1);
  17.     tree.insertNode(2, 5, 0);
  18.      tree.insertNode(2, 9, 0);
  19.     cout << 2 << "—" << 5<<"— —"<<9<<endl;
  20.     cout << '|' << "  " << "|" <<"     "<<"|"<< endl;
  22.     tree.insertNode(2, 3, 1);
  23.      tree.insertNode(5, 6, 1);
  24.      tree.insertNode(6, 7, 0);
  25.      tree.insertNode(9, 10, 1);
  26.     cout << 3 << "  " << 6 << "—" << 7 <<" "<< 10 << endl;
  27.     cout << "|" << "     " << "|" << endl;
  29.      tree.insertNode(3, 4, 1);
  30.     tree.insertNode(7, 8, 1);
  31.     cout << 4 << "     " << 8 << "\n\n"<<endl;
  33.     
  35.     std::cout << "前序遍历：";
  36.     tree.preOrderPrint(tree.getTreeRoot());
  37.     std::cout << std::endl;
  39.     std::cout << "后序遍历：";
  40.     tree.posOrderPrint(tree.getTreeRoot());
  41.     std::cout << std::endl;
  43.     std::cout << "中序遍历：";
  44.     tree.inOrderPrint(tree.getTreeRoot());
  45.     std::cout << std::endl;
  47.     std::cin.get();
  48.     return 0;
  49. }

 

测试结果：

 

 

 

版权声明：本文为daniumeng原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/daniumeng/p/8597862.html