结点：
包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。
在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。
在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。
数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点
树结点（树节点）：
树节点相关术语：
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 叶节点或终端节点：度为0的节点称为叶节点；
- 非终端节点或分支节点：度不为0的节点；
- 双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
根据树结点的相关定义，采用“双亲孩子表示法”。其属性如下：
DWORD m_dwLevel; //Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on; T m_data; //the friend class can use it directly AL_TreeNodeSeq<T>* m_pParent; //Parent position AL_ListSeq<AL_TreeNodeSeq<T>*> m_listChild; //All Child tree node
树的几种表示法
在实际中，可使用多种形式的存储结构来表示树，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。
1．双亲表示法
由于树中的每个结点都有唯一的一个双亲结点，所以可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，每个结点含两个域，数据域存放结点本身信息，双亲域指示本结点的双亲结点在数组中位置。
2．孩子表示法
1.多重链表：每个结点有多个指针域，分别指向其子树的根
1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域.
2）结点不同构：结点指针个数不等，为该结点的度d
2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表
3．双亲孩子表示法
1.双亲表示法，PARENT（T，x）可以在常量时间内完成，但是求结点的孩子时需要遍历整个结构。
2.孩子链表表示法，适于那些涉及孩子的操作，却不适于PARENT（T，x）操作。
3.将双亲表示法和孩子链表表示法合在一起，可以发挥以上两种存储结构的优势，称为带双亲的孩子链表表示法
4．双亲孩子兄弟表示法 （二叉树专用）
又称为二叉树表示法，以二叉链表作为树的存储结构。
顺序存储结构
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.
顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。
顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
优点：
随机存取表中元素。缺点：插入和删除操作需要移动元素。
本代码默认list可以容纳的item数目为100个，用户可以自行设置item数目。当list饱和时，由于Tree是非线性结构，动态扩展内存相当麻烦。因此示例中的Demo及代码将不会动态扩展内存。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
C++完整个代码示例（代码在VS2005下测试可运行）
AL_TreeNodeSeq.h
/**
@(#)$Id: AL_TreeNodeSeq.h 48 2013-09-23 05:48:41Z xiaoting $
@brief Each of the data structure corresponds to a data node storage unit, this storage unit is called storage node, the node can
also be referred to.
The related concepts of tree node
1.degree degree node: A node of the subtree containing the number is called the node degree;
2.leaf leaf nodes or terminal nodes: degree 0 are called leaf nodes;
3.branch non-terminal node or branch node: node degree is not 0;
4.parent parent node or the parent node: If a node contains a child node, this node is called its child node's parent;
5.child child node or child node: A node subtree containing the root node is called the node's children;
6.slibing sibling nodes: nodes with the same parent node is called mutual sibling;
7.ancestor ancestor node: from the root to the node through all the nodes on the branch;
8.descendant descendant nodes: a node in the subtree rooted at any node is called the node's descendants.
////////////////////////////////Sequential storage structure//////////////////////////////////////////
Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called
the linear order of the table storage structure.
Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical
location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency.
Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming
language (e.g., c / c) of the array to describe.
The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing
all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between
the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node
corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main
disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
Benefits:
Random Access table elements.
Disadvantages:
insert and delete operations need to move elements.
@Author $Author: xiaoting $
@Date $Date: 2013-09-23 13:48:41 +0800 (周一, 23 九月 2013) $
@Revision $Revision: 48 $
@URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeNodeSeq.h $
@Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeNodeSeq.h 48 2013-09-23 05:48:41Z xiaoting $
*/
#ifndef CXX_AL_TREENODESEQ_H
#define CXX_AL_TREENODESEQ_H
#ifndef CXX_AL_LISTSEQ_H
#include "AL_ListSeq.h"
#endif
///////////////////////////////////////////////////////////////////////////
// AL_TreeNodeSeq
///////////////////////////////////////////////////////////////////////////
template<typename T>
class AL_TreeNodeSeq
{
public:
/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
~AL_TreeNodeSeq();
/**
* GetLevel
*
* @param
* @return DWORD
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;
* @attention
*/
DWORD GetLevel() const;
/**
* SetLevel
*
* @param DWORD dwLevel <IN>
* @return
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;
* @attention
*/
VOID SetLevel(DWORD dwLevel);
/**
* GetData
*
* @param
* @return T
* @note
* @attention
*/
T GetData() const;
/**
* SetData
*
* @param const T& tTemplate <IN>
* @return
* @note
* @attention
*/
VOID SetData(const T& tTemplate);
/**
* GetParent
*
* @param
* @return AL_TreeNodeSeq<T>*
* @note parent node pointer, not to manager memory
* @attention
*/
AL_TreeNodeSeq<T>* GetParent() const;
/**
* SetParent
*
* @param DWORD dwIndex <IN>
* @param AL_TreeNodeSeq<T>* pParent <IN>
* @return BOOL
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the index (from the left of parent's child )
*/
BOOL SetParent(DWORD dwIndex, AL_TreeNodeSeq<T>* pParent);
/**
* SetParentLeft
*
* @param AL_TreeNodeSeq<T>* pParent <IN>
* @return BOOL
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the left (from the left of parent's child )
*/
BOOL SetParentLeft(AL_TreeNodeSeq<T>* pParent);
/**
* SetParentRight
*
* @param AL_TreeNodeSeq<T>* pParent <IN>
* @return BOOL
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the right (from the right of parent's child )
*/
BOOL SetParentRight(AL_TreeNodeSeq<T>* pParent);
/**
* Insert
*
* @param DWORD dwIndex <IN>
* @param AL_TreeNodeSeq<T>* pInsertChild <IN>
* @return BOOL
* @note inset the const AL_TreeNodeSeq<T>* into the child notes at the position
* @attention
*/
BOOL Insert(DWORD dwIndex, AL_TreeNodeSeq<T>* pInsertChild);
/**
* InsertLeft
*
* @param AL_TreeNodeSeq<T>* pInsertChild <IN>
* @return BOOL
* @note inset the const AL_TreeNodeSeq<T>* into the child notes at the left
* @attention
*/
BOOL InsertLeft(AL_TreeNodeSeq<T>* pInsertChild);
/**
* InsertRight
*
* @param AL_TreeNodeSeq<T>* pInsertChild <IN>
* @return BOOL
* @note inset the const AL_TreeNodeSeq<T>* into the child notes at the right
* @attention
*/
BOOL InsertRight(AL_TreeNodeSeq<T>* pInsertChild);
/**
* GetChild
*
* @param DWORD dwIndex <IN>
* @return AL_TreeNodeSeq<T>*
* @note the dwIndex must is little than the node degree
* @attention
*/
AL_TreeNodeSeq<T>* GetChild(DWORD dwIndex) const;
/**
* GetChildLeft
*
* @param
* @return AL_TreeNodeSeq<T>*
* @note
* @attention
*/
AL_TreeNodeSeq<T>* GetChildLeft() const;
/**
* GetChildRight
*
* @param
* @return AL_TreeNodeSeq<T>*
* @note
* @attention
*/
AL_TreeNodeSeq<T>* GetChildRight() const;
/**
* GetDegree
*
* @param
* @return DWORD
* @note degree node: A node of the subtree containing the number is called the node degree;
* @attention
*/
DWORD GetDegree() const;
/**
* IsLeaf
*
* @param
* @return BOOL
* @note leaf nodes or terminal nodes: degree 0 are called leaf nodes;
* @attention
*/
BOOL IsLeaf() const;
/**
* IsBranch
*
* @param
* @return BOOL
* @note non-terminal node or branch node: node degree is not 0;
* @attention
*/
BOOL IsBranch() const;
/**
* IsParent
*
* @param const AL_TreeNodeSeq<T>* pChild <IN>
* @return BOOL
* @note parent node or the parent node: If a node contains a child node, this node is called its child
* @attention
*/
BOOL IsParent(const AL_TreeNodeSeq<T>* pChild) const;
/**
* GetSibling
*
* @param AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling <OUT>
* @return BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention
*/
BOOL GetSibling(AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling) const;
/**
* GetAncestor
*
* @param AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor <OUT>
* @return BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention
*/
BOOL GetAncestor(AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor) const;
/**
* GetDescendant
*
* @param AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant <OUT>
* @return BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention
*/
BOOL GetDescendant(AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant) const;
protected:
public:
/**
* Construction
*
* @param
* @return
* @note private the Construction, avoid the others use it
* @attention
*/
AL_TreeNodeSeq();
/**
* Construction
*
* @param const T& tTemplate <IN>
* @return
* @note
* @attention private the Construction, avoid the others use it
*/
AL_TreeNodeSeq(const T& tTemplate);
/**
*Copy Construct
*
* @param const AL_TreeNodeSeq& cAL_TreeNodeSeq
* @return
*/
AL_TreeNodeSeq(const AL_TreeNodeSeq& cAL_TreeNodeSeq);
/**
*Assignment
*
* @param const AL_TreeNodeSeq& cAL_TreeNodeSeq
* @return AL_TreeNodeSeq&
*/
AL_TreeNodeSeq& operator = (const AL_TreeNodeSeq& cAL_TreeNodeSeq);
public:
protected:
private:
DWORD m_dwLevel; //Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;
T m_data; //the friend class can use it directly
AL_TreeNodeSeq<T>* m_pParent; //Parent position
AL_ListSeq<AL_TreeNodeSeq<T>*> m_listChild; //All Child tree node
};
///////////////////////////////////////////////////////////////////////////
// AL_TreeNodeSeq
///////////////////////////////////////////////////////////////////////////
/**
* Construction
*
* @param
* @return
* @note private the Construction, avoid the others use it
* @attention
*/
template<typename T>
AL_TreeNodeSeq<T>::AL_TreeNodeSeq():
m_dwLevel(0x00),
m_pParent(NULL)
{
m_listChild.Clear();
}
/**
* Construction
*
* @param const T& tTemplate <IN>
* @return
* @note
* @attention private the Construction, avoid the others use it
*/
template<typename T>
AL_TreeNodeSeq<T>::AL_TreeNodeSeq(const T& tTemplate):
m_dwLevel(0x00),
m_data(tTemplate),
m_pParent(NULL)
{
m_listChild.Clear();
}
/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T>
AL_TreeNodeSeq<T>::~AL_TreeNodeSeq()
{
//it doesn't matter to clear the pointer or not.
m_dwLevel = 0x00;
m_pParent = NULL;
m_listChild.Clear();
}
/**
* GetLevel
*
* @param
* @return DWORD
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;
* @attention
*/
template<typename T> DWORD
AL_TreeNodeSeq<T>::GetLevel() const
{
return m_dwLevel;
}
/**
* SetLevel
*
* @param DWORD dwLevel <IN>
* @return
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;
* @attention
*/
template<typename T> VOID
AL_TreeNodeSeq<T>::SetLevel(DWORD dwLevel)
{
m_dwLevel = dwLevel;
}
/**
* GetData
*
* @param
* @return T
* @note
* @attention
*/
template<typename T> T
AL_TreeNodeSeq<T>::GetData() const
{
return m_data;
}
/**
* SetData
*
* @param const T& tTemplate <IN>
* @return
* @note
* @attention
*/
template<typename T> VOID
AL_TreeNodeSeq<T>::SetData(const T& tTemplate)
{
m_data = tTemplate;
}
/**
* GetParent
*
* @param
* @return AL_TreeNodeSeq<T>*
* @note parent node pointer, not to manager memory
* @attention
*/
template<typename T> AL_TreeNodeSeq<T>*
AL_TreeNodeSeq<T>::GetParent() const
{
return m_pParent;
}
/**
* SetParent
*
* @param DWORD dwIndex <IN>
* @param AL_TreeNodeSeq<T>* pParent <IN>
* @return BOOL
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the index (from the left of parent's child )
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::SetParent(DWORD dwIndex, AL_TreeNodeSeq<T>* pParent)
{
BOOL bSetParent = FALSE;
bSetParent = pParent->Insert(dwIndex, this);
if (TRUE == bSetParent) {
//current node insert to the parent successfully
m_pParent = pParent;
}
return bSetParent;
}
/**
* SetParentLeft
*
* @param AL_TreeNodeSeq<T>* pParent <IN>
* @return
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the left (from the left of parent's child )
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::SetParentLeft(AL_TreeNodeSeq<T>* pParent)
{
return SetParent(0x00, pParent);
}
/**
* SetParentRight
*
* @param AL_TreeNodeSeq<T>* pParent <IN>
* @return
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the right (from the right of parent's child )
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::SetParentRight(AL_TreeNodeSeq<T>* pParent)
{
return SetParent(pParent->GetDegree(), pParent);
}
/**
* Insert
*
* @param DWORD dwIndex <IN>
* @param AL_TreeNodeSeq<T>* pInsertChild <IN>
* @return BOOL
* @note inset the const AL_TreeNodeSeq<T>* into the child notes at the position
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::Insert(DWORD dwIndex, AL_TreeNodeSeq<T>* pInsertChild)
{
BOOL bInsert = FALSE;
bInsert = m_listChild.Insert(dwIndex, pInsertChild);
if (TRUE == bInsert) {
if (GetLevel()+1 != pInsertChild->GetLevel()) {
//deal with the child level
INT iLevelDiff = pInsertChild->GetLevel() - GetLevel();
pInsertChild->SetLevel(GetLevel()+1);
AL_ListSeq<AL_TreeNodeSeq<T>*> listDescendant;
if (FALSE == GetDescendant(listDescendant)) {
return FALSE;
}
AL_TreeNodeSeq<T>* pDescendant = NULL;
for (DWORD dwCnt=0; dwCnt<listDescendant.Length(); dwCnt++) {
if (TRUE == listDescendant.Get(pDescendant, dwCnt)) {
if (NULL != pDescendant) {
//set child level
pDescendant->SetLevel(pDescendant->GetLevel()-iLevelDiff+1);
}
else {
//error
return FALSE;
}
}
else {
//error
return FALSE;
}
}
}
//child node insert to the current successfully
pInsertChild->m_pParent = this;
}
return bInsert;
}
/**
* InsertLeft
*
* @param AL_TreeNodeSeq<T>* pInsertChild <IN>
* @return BOOL
* @note inset the const AL_TreeNodeSeq<T>* into the child notes at the left
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::InsertLeft(AL_TreeNodeSeq<T>* pInsertChild)
{
return Insert(0x00, pInsertChild);
}
/**
* InsertRight
*
* @param AL_TreeNodeSeq<T>* pInsertChild <IN>
* @return BOOL
* @note inset the const AL_TreeNodeSeq<T>* into the child notes at the right
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::InsertRight(AL_TreeNodeSeq<T>* pInsertChild)
{
return Insert(GetDegree(), pInsertChild);
}
/**
* GetChild
*
* @param DWORD dwIndex <IN>
* @return AL_TreeNodeSeq<T>*
* @note the dwIndex must is little than the node degree
* @attention
*/
template<typename T> AL_TreeNodeSeq<T>*
AL_TreeNodeSeq<T>::GetChild(DWORD dwIndex) const
{
AL_TreeNodeSeq<T>* pChild = NULL;
if (TRUE == m_listChild.Get(pChild, dwIndex)) {
return pChild;
}
return NULL;
}
/**
* GetChildLeft
*
* @param
* @return AL_TreeNodeSeq<T>*
* @note
* @attention
*/
template<typename T> AL_TreeNodeSeq<T>*
AL_TreeNodeSeq<T>::GetChildLeft() const
{
return GetChild(0x00);
}
/**
* GetChildRight
*
* @param
* @return AL_TreeNodeSeq<T>*
* @note
* @attention
*/
template<typename T> AL_TreeNodeSeq<T>*
AL_TreeNodeSeq<T>::GetChildRight() const
{
return GetChild(GetDegree());
}
/**
* GetDegree
*
* @param
* @return DWORD
* @note degree node: A node of the subtree containing the number is called the node degree;
* @attention
*/
template<typename T> DWORD
AL_TreeNodeSeq<T>::GetDegree() const
{
return m_listChild.Length();
}
/**
* IsLeaf
*
* @param
* @return BOOL
* @note leaf nodes or terminal nodes: degree 0 are called leaf nodes;
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::IsLeaf() const
{
return (0x00 == GetDegree()) ? TRUE:FALSE;
}
/**
* IsBranch
*
* @param
* @return BOOL
* @note non-terminal node or branch node: node degree is not 0;
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::IsBranch() const
{
return (0x00 != GetDegree()) ? TRUE:FALSE;
}
/**
* IsParent
*
* @param const AL_TreeNodeSeq<T>* pChild <IN>
* @return BOOL
* @note parent node or the parent node: If a node contains a child node, this node is called its child
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::IsParent(const AL_TreeNodeSeq<T>* pChild) const
{
// AL_TreeNodeSeq<T>* pCompare = NULL;
// for (DWORD dwCnt=0; dwCnt<GetDegree(); dwCnt++) {
// if (TRUE == m_listChild.Get(pCompare, dwCnt)) {
// if (pCompare == pChild) {
// //find the child
// return TRUE;
// }
// }
// }
// return FALSE;
if (this == pChild->m_pParent) {
return TRUE;
}
return FALSE;
}
/**
* GetSibling
*
* @param AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling <OUT>
* @return BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::GetSibling(AL_ListSeq<AL_TreeNodeSeq<T>*>& listSibling) const
{
BOOL bSibling = FALSE;
if (NULL == m_pParent) {
//not parent node
return bSibling;
}
listSibling.Clear();
AL_ListSeq<AL_TreeNodeSeq<T>*>& listParentChild = m_pParent->m_listChild;
AL_TreeNodeSeq<T>* pParentChild = NULL;
for (DWORD dwCnt=0; dwCnt<m_pParent->GetDegree(); dwCnt++) {
pParentChild = m_pParent->GetChild(dwCnt);
if (NULL != pParentChild) {
//get the child
if (pParentChild == this) {
//itself
continue;
}
listSibling.InsertEnd(pParentChild);
bSibling = TRUE;
}
else {
//error can not get the child
return FALSE;
}
}
return bSibling;
}
/**
* GetAncestor
*
* @param AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor <OUT>
* @return BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::GetAncestor(AL_ListSeq<AL_TreeNodeSeq<T>*>& listAncestor) const
{
if (NULL == m_pParent) {
//not parent node
return FALSE;
}
listAncestor.Clear();
AL_TreeNodeSeq<T>* pParent = m_pParent;
while (NULL != pParent) {
listAncestor.InsertEnd(pParent);
pParent = pParent->m_pParent;
}
return TRUE;
}
/**
* GetDescendant
*
* @param AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant <OUT>
* @return BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention
*/
template<typename T> BOOL
AL_TreeNodeSeq<T>::GetDescendant(AL_ListSeq<AL_TreeNodeSeq<T>*>& listDescendant) const
{
if (TRUE == IsLeaf()) {
//child node
return FALSE;
}
listDescendant.Clear();
AL_TreeNodeSeq<T>* pDescendant = NULL;
for (DWORD dwCnt=0; dwCnt<GetDegree(); dwCnt++) {
pDescendant = GetChild(dwCnt);
if (NULL != pDescendant) {
//get the child
listDescendant.InsertEnd(pDescendant);
}
else {
//error can not get the child
return FALSE;
}
}
//loop the all node in listDescendant
DWORD dwDescendantLoop = 0x00;
AL_TreeNodeSeq<T>* pDescendantLoop = NULL;
while (TRUE == listDescendant.Get(pDescendant, dwDescendantLoop)) {
dwDescendantLoop++;
if (NULL != pDescendant) {
for (DWORD dwCnt=0; dwCnt<pDescendant->GetDegree(); dwCnt++) {
pDescendantLoop = pDescendant->GetChild(dwCnt);
if (NULL != pDescendantLoop) {
//get the descendant
listDescendant.InsertEnd(pDescendantLoop);
}
else {
//error can not get the descendant
return FALSE;
}
}
}
else {
//error
return FALSE;
}
}
return TRUE;
}
#endif // CXX_AL_TREENODESEQ_H
/* EOF */
测试代码
#ifdef TEST_AL_TREENODESEQ
AL_TreeNodeSeq<DWORD> cTreeNodeSeq;
cTreeNodeSeq.SetLevel(1);
DWORD dwLevel = cTreeNodeSeq.GetLevel();
std::cout<<dwLevel<<std::endl;
cTreeNodeSeq.SetData(10);
DWORD dwData = cTreeNodeSeq.GetData();
std::cout<<dwData<<std::endl;
AL_TreeNodeSeq<DWORD> cTreeNodeSeqParent;
cTreeNodeSeqParent.SetLevel(0);
cTreeNodeSeqParent.SetData(0);
cTreeNodeSeq.SetParent(0x00, &cTreeNodeSeqParent);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild20(20);
cTreeNodeSeqChild20.SetLevel(2);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild21(21);
cTreeNodeSeqChild21.SetLevel(2);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild22(22);
cTreeNodeSeqChild22.SetLevel(2);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild23(23);
cTreeNodeSeqChild23.SetLevel(2);
cTreeNodeSeq.Insert(0x00, &cTreeNodeSeqChild21);
cTreeNodeSeq.InsertLeft(&cTreeNodeSeqChild20);
cTreeNodeSeq.InsertRight(&cTreeNodeSeqChild22);
cTreeNodeSeq.Insert(0x03, &cTreeNodeSeqChild23);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild30(30);
cTreeNodeSeqChild30.SetLevel(3);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild31(31);
cTreeNodeSeqChild31.SetLevel(3);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild32(32);
cTreeNodeSeqChild32.SetLevel(3);
AL_TreeNodeSeq<DWORD> cTreeNodeSeqChild33(33);
cTreeNodeSeqChild33.SetLevel(3);
cTreeNodeSeqChild31.SetParent(0x00, &cTreeNodeSeqChild20);
cTreeNodeSeqChild30.SetParentLeft(&cTreeNodeSeqChild20);
cTreeNodeSeqChild32.SetParentRight(&cTreeNodeSeqChild20);
cTreeNodeSeqChild33.SetParent(0x03, &cTreeNodeSeqChild20 );
AL_TreeNodeSeq<DWORD>* pParent = NULL;
pParent = cTreeNodeSeq.GetParent();
if (NULL != pParent) {
std::cout<<pParent->GetLevel()<<" "<<pParent->GetData()<<" "<<pParent->GetDegree()<<std::endl;
std::cout<<pParent->IsLeaf()<<" "<<pParent->IsBranch()<<" "<<pParent->IsParent(&cTreeNodeSeq)<<" "<<pParent->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
AL_TreeNodeSeq<DWORD>* pChild = NULL;
pChild = cTreeNodeSeq.GetChild(0x01);
if (NULL != pChild) {
std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;
std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeSeq)<<" "<<pChild->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
pChild = cTreeNodeSeq.GetChild(0x00);
if (NULL != pChild) {
std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;
std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeSeq)<<" "<<pChild->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
pChild = cTreeNodeSeq.GetChildLeft();
if (NULL != pChild) {
std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;
std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeSeq)<<" "<<pChild->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
pChild = cTreeNodeSeq.GetChild(0x03);
if (NULL != pChild) {
std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;
std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeSeq)<<" "<<pChild->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
pChild = cTreeNodeSeq.GetChildRight();
if (NULL != pChild) {
std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;
std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeSeq)<<" "<<pChild->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
AL_ListSeq<AL_TreeNodeSeq<DWORD>*> cListSeq;
AL_TreeNodeSeq<DWORD>* pList = NULL;
BOOL bSibling = cTreeNodeSeq.GetSibling(cListSeq);
if (TRUE == bSibling) {
for (DWORD dwCnt=0; dwCnt<cListSeq.Length(); dwCnt++) {
if (TRUE == cListSeq.Get(pList, dwCnt)) {
if (NULL != pList) {
std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;
std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeSeq)<<" "<<pList->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
}
}
}
cListSeq.Clear();
bSibling = cTreeNodeSeqChild20.GetSibling(cListSeq);
if (TRUE == bSibling) {
for (DWORD dwCnt=0; dwCnt<cListSeq.Length(); dwCnt++) {
if (TRUE == cListSeq.Get(pList, dwCnt)) {
if (NULL != pList) {
std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;
std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeSeq)<<" "<<pList->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
}
}
}
cListSeq.Clear();
bSibling = cTreeNodeSeqParent.GetAncestor(cListSeq);
if (TRUE == bSibling) {
for (DWORD dwCnt=0; dwCnt<cListSeq.Length(); dwCnt++) {
if (TRUE == cListSeq.Get(pList, dwCnt)) {
if (NULL != pList) {
std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;
std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeSeq)<<" "<<pList->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
}
}
}
bSibling = cTreeNodeSeqChild33.GetAncestor(cListSeq);
if (TRUE == bSibling) {
for (DWORD dwCnt=0; dwCnt<cListSeq.Length(); dwCnt++) {
if (TRUE == cListSeq.Get(pList, dwCnt)) {
if (NULL != pList) {
std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;
std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeSeq)<<" "<<pList->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
}
}
}
cListSeq.Clear();
bSibling = cTreeNodeSeqParent.GetDescendant(cListSeq);
if (TRUE == bSibling) {
for (DWORD dwCnt=0; dwCnt<cListSeq.Length(); dwCnt++) {
if (TRUE == cListSeq.Get(pList, dwCnt)) {
if (NULL != pList) {
std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;
std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeSeq)<<" "<<pList->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
}
}
}
cListSeq.Clear();
bSibling = cTreeNodeSeqChild33.GetDescendant(cListSeq);
if (TRUE == bSibling) {
for (DWORD dwCnt=0; dwCnt<cListSeq.Length(); dwCnt++) {
if (TRUE == cListSeq.Get(pList, dwCnt)) {
if (NULL != pList) {
std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;
std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeSeq)<<" "<<pList->IsParent(&cTreeNodeSeqChild33)<<std::endl;
}
}
}
}
cListSeq.Clear();
#endif