※数据结构※→☆非线性结构（tree）☆============二叉树结点 链式存储结构（tree node binary list）（二十）
二叉树
在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为，出度为2的结点数为，则=+ 1。
基本形态
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)只有左子树——(c)；
(4)只有右子树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
重要概念
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)深度——二叉树的层数，就是高度。
性质
(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；
(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I>1，则其父结点的编号为I/2；
如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i
======================================================================================================
树结点 链式存储结构（tree node list）
结点：
包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。
在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。
数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点
树结点（树节点）：
树节点相关术语：
节点的度：一个节点含有的子树的个数称为该节点的度；叶节点或终端节点：度为0的节点称为叶节点；非终端节点或分支节点：度不为0的节点；双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；节点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；堂兄弟节点：双亲在同一层的节点互为堂兄弟；节点的祖先：从根到该节点所经分支上的所有节点；子孙：以某节点为根的子树中任一节点都称为该节点的子孙。根据树结点的相关定义，采用“双亲孩子表示法”。其属性如下：
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．双亲孩子兄弟表示法 （二叉树专用）
又称为二叉树表示法，以二叉链表作为树的存储结构。
链式存储结构
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).
它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.
链式存储结构特点：
1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
5、每个结点是由数据域和指针域组成。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
C++完整个代码示例（代码在VS2005下测试可运行）
AL_TreeNodeBinList.h
#ifdef TEST_AL_TREENODEBINLISTAL_TreeNodeBinList<DWORD> cTreeNodeBinList;cTreeNodeBinList.SetLevel(1);DWORD dwLevel = cTreeNodeBinList.GetLevel();std::cout<<dwLevel<<std::endl;cTreeNodeBinList.SetData(10);DWORD dwData = cTreeNodeBinList.GetData();std::cout<<dwData<<std::endl;AL_TreeNodeBinList<DWORD> cTreeNodeBinListParent;cTreeNodeBinListParent.SetLevel(0);cTreeNodeBinListParent.SetData(0);BOOL bSetParent = cTreeNodeBinList.SetParent(0x00, &cTreeNodeBinListParent);std::cout<<bSetParent<<std::endl;AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild20(20);cTreeNodeBinListChild20.SetLevel(2);AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild21(21);cTreeNodeBinListChild21.SetLevel(2);AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild22(22);cTreeNodeBinListChild22.SetLevel(2);AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild23(23);cTreeNodeBinListChild23.SetLevel(2);BOOL bInsert = cTreeNodeBinList.Insert(0x00, &cTreeNodeBinListChild21);std::cout<<bInsert<<std::endl;bInsert = cTreeNodeBinList.InsertLeft(&cTreeNodeBinListChild20);std::cout<<bInsert<<std::endl;bInsert = cTreeNodeBinList.InsertRight(&cTreeNodeBinListChild22);std::cout<<bInsert<<std::endl;bInsert = cTreeNodeBinList.Insert(0x03, &cTreeNodeBinListChild23);std::cout<<bInsert<<std::endl;AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild30(30);cTreeNodeBinListChild30.SetLevel(3);AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild31(31);cTreeNodeBinListChild31.SetLevel(3);AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild32(32);cTreeNodeBinListChild32.SetLevel(3);AL_TreeNodeBinList<DWORD> cTreeNodeBinListChild33(33);cTreeNodeBinListChild33.SetLevel(3);bSetParent = cTreeNodeBinListChild31.SetParent(0x00, &cTreeNodeBinListChild21);std::cout<<bSetParent<<std::endl;bSetParent = cTreeNodeBinListChild30.SetParentLeft(&cTreeNodeBinListChild21);std::cout<<bSetParent<<std::endl;bSetParent = cTreeNodeBinListChild32.SetParentRight(&cTreeNodeBinListChild21);std::cout<<bSetParent<<std::endl;bSetParent = cTreeNodeBinListChild33.SetParent(0x03, &cTreeNodeBinListChild21 );std::cout<<bSetParent<<std::endl;AL_TreeNodeBinList<DWORD>*pParent = NULL;pParent = cTreeNodeBinList.GetParent();if (NULL != pParent) {std::cout<<pParent->GetLevel()<<" "<<pParent->GetData()<<" "<<pParent->GetDegree()<<std::endl;std::cout<<pParent->IsLeaf()<<" "<<pParent->IsBranch()<<" "<<pParent->IsParent(&cTreeNodeBinList)<<" "<<pParent->IsParent(&cTreeNodeBinListChild31)<<std::endl;}AL_TreeNodeBinList<DWORD>*pChild = NULL;pChild = cTreeNodeBinList.GetChildLeft();if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeBinList)<<" "<<pChild->IsParent(&cTreeNodeBinListChild31)<<std::endl;}pChild = cTreeNodeBinList.GetChildRight();if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(&cTreeNodeBinList)<<" "<<pChild->IsParent(&cTreeNodeBinListChild31)<<std::endl;}AL_ListSingle<AL_TreeNodeBinList<DWORD>*> cListSingle;AL_TreeNodeBinList<DWORD>*pList = NULL;BOOL bSibling = cTreeNodeBinList.GetSibling(cListSingle);if (TRUE == bSibling) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}cListSingle.Clear();bSibling = cTreeNodeBinListChild21.GetSibling(cListSingle);if (TRUE == bSibling) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}cListSingle.Clear();BOOL bAncestor = cTreeNodeBinListParent.GetAncestor(cListSingle);if (TRUE == bAncestor) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}bAncestor = cTreeNodeBinListChild32.GetAncestor(cListSingle);if (TRUE == bAncestor) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}cListSingle.Clear();BOOL bDescendant = cTreeNodeBinListParent.GetDescendant(cListSingle);if (TRUE == bDescendant) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}cListSingle.Clear();bDescendant = cTreeNodeBinListChild32.GetDescendant(cListSingle);if (TRUE == bDescendant) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}cListSingle.Clear();AL_TreeNodeBinList<DWORD> cTreeNodeBinListRoot(999);cTreeNodeBinListChild30.SetLevel(0);bSetParent = cTreeNodeBinListParent.SetParentLeft(&cTreeNodeBinListRoot);std::cout<<bSetParent<<std::endl;bDescendant = cTreeNodeBinListRoot.GetDescendant(cListSingle);if (TRUE == bDescendant) {for (DWORD dwCnt=0; dwCnt<cListSingle.Length(); dwCnt++) {if (TRUE == cListSingle.Get(pList, dwCnt)) {if (NULL != pList) {std::cout<<pList->GetLevel()<<" "<<pList->GetData()<<" "<<pList->GetDegree()<<std::endl;std::cout<<pList->IsLeaf()<<" "<<pList->IsBranch()<<" "<<pList->IsParent(&cTreeNodeBinList)<<" "<<pList->IsParent(&cTreeNodeBinListChild31)<<std::endl;}}}}cListSingle.Clear();#endif
