树

树是一种数据结构，它是n(n>=0)个节点的有限集。n=0时称为空树。n>0时，有限集的元素构成一个具有层次感的数据结构。

根

有且仅有一个结点的非空树，那个结点就是根。

A就是上面树的根节点

子树

在一棵非空树中，除根外，其余所有结点可以分为m（m≥0）个互不相交的集合。每个集合本身又是一棵树，称为根的子树。

结点

包含一个数据元素及若干指向子树的分支

孩子结点和双亲结点

结点的子树的根称为该结点的孩子。B结点是A结点的孩子，则A结点是B结点的双亲

兄弟结点和堂兄结点

同一双亲的孩子结点称为兄弟结点，同一层上结点称为堂兄结点

祖先结点

从根到该结点的所经分支上的所有结点

子孙结点

以某结点为根的子树中任一结点都称为该结点的子孙结点层

叶子结点

终端结点，是度为 0 （没有子树）的结点

分支结点

除了叶子节点之外的节点，也即是度不为0的节点

内部结点

除了根节点之外的分支节点

度

结点拥有的子树的数量为结点的度，树的所有结点中度的最大值为树的度

层次和深度

根节点为第一层，它的孩子为第二层，依此类推。树中结点最大层次的值为树的深度

森林

0或多棵互不相交的树的集合

树的有序性

如果树中结点的各子树从左向右是有序的，子树间不能互换位置，则称该树为有序树，否则为无序树

#pragma once
//通过孩子兄弟实现
//树节点
template<typename T>
struct TreeNode
{T data;//数据域//指针域TreeNode* parent;//指向双亲结点的指针TreeNode* brother;//指向兄弟结点的指针TreeNode* child;//指向孩子结点的指针TreeNode(T d){data = d;parent = nullptr;brother = nullptr;child = nullptr;}
};//树
template <typename T>
class CMyTree
{TreeNode<T> *pRoot;//根节点
public:CMyTree();~CMyTree();void clear();bool isFind(T const& value);void insert(T const& findValue, T const& insertValue, bool isChild);
private:void clear(TreeNode<T>* root);//借助递归删除所有子树TreeNode<T>* find(TreeNode<T>*root, T const& value);
};template <typename T>
CMyTree<T>::~CMyTree()
{clear();
}template <typename T>
void CMyTree<T>::clear()
{if (pRoot)_clear(pRoot);
}template <typename T>
bool CMyTree<T>::isFind(T const& value)
{return find(pRoot, value) != nullptr;
}template <typename T>
void CMyTree<T>::insert(T const& findValue, T const& insertValue, bool isChild)
{//准备一个结点TreeNode<T>* insertNode = new TreeNode<T>;insertNode->data = insertValue;insertNode->parent = nullptr;insertNode->brother = nullptr;insertNode->child = nullptr;if (pRoot){//在非空树中找到findValue所在的结点TreeNode<T>* findNode = find(pRoot, findValue);if (findNode){//找到插入位置if (isChild){if (findNode->child) //有孩子结点，通过兄弟结点插入{TreeNode<T>* tempNode = findNode->child;while (tempNode->brother)tempNode = tempNode->brother;tempNode->brother = insertNode;insertNode->parent = tempNode->parent;}else  //按孩子结点插入{findNode->child = insertNode;insertNode->parent = findNode;}}else //兄弟结点插入{if (findNode->brother){TreeNode<T>* tempNode = findNode->brother;while (tempNode->brother)tempNode = tempNode->brother;tempNode->brother = insertNode;insertNode->parent = tempNode->parent;}else{findNode->brother = insertNode;insertNode->parent = findNode->parent;}}}else{//代表非空树种没有findValue结点。//插入规则随你定}}elsepRoot = insertNode;
}template <typename T>
void CMyTree<T>::clear(TreeNode<T>* root)
{if (root){clear(root->brother);clear(root->child);delete root;root = nullptr;}
}template <typename T>
TreeNode<T>* CMyTree<T>::find(TreeNode<T>* root, T const& value)
{if (root){if (root->data == value)return root;TreeNode<T>* tempNode = find(root->brother, value);if (tempNode)return tempNode;return find(root->child, value);}return nullptr;
}template <typename T>
CMyTree<T>::CMyTree()
{pRoot = nullptr;
}