基本術語： 節點的度：書中某一節點擁有的子節點數量。 數的度：該樹中所有節點的度的最大值。 葉節點（終端節點）:度為零的節點。 分支節點（非終端節點）:度不為零的節點。 根節點（開始節點）：樹中的第一個節點。 內部節點：樹中除了根節點之外的節點。 節點的層數：若根節點層數為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;
}
測試結果：
