基本术语：
节点的度：书中某一节点拥有的子节点数量。
数的度：该树中所有节点的度的最大值。
叶节点（终端节点）:度为零的节点。
分支节点（非终端节点）:度不为零的节点。
根节点（开始节点）：树中的第一个节点。
内部节点：树中除了根节点之外的节点。
节点的层数：若根节点层数为1，根节点的第n代子节点的层数为n。
树的高度：书中的节点的最大层数。
有序树和无序树：若树中某一节点的子节点无序，则该树为无序树，否则为有序树。
森林：去掉一棵树的根节点后得到的n棵树。
树的特点：
1.树是一种很基础很重要的非线性结构。
2.除表头（树根）和表尾（叶节点）外，任何一个节点只有一个直接前驱，但有多个直接后继。
3.树是数据的有限集，树分为空树和非空树。
非空树：有且只有一个根节点。若根节点的子节点大于1，可以理解为这棵非空树有m棵相互独立的非空树组成。
4.树的递归特性（★★★）：一颗非空树有若干子树组成，每一棵子树又由更小的子组成。
C++实现：
[MyTree.h]：无序树类模板头文件
#pragma oncetemplate<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;
}
测试结果：
