C++程序设计之树

1、 树（Tree）是n（n>=0）个节点的有限集。在一棵非空树中，有且仅有一个特定的称为根的节点，当n>1时其余节点可分为m（m>0）个互不相交的有限集T1，T2……Tm，其中，每一个集合本身又是一棵树，并且称为根的子树（subtree）。

2、 树是一种数据结构，可以表示为：Tree=(D,R)。 D是具有相同特性的数据元素的集合；若D只含一个数据元素，则R为空集，否则R是D上一个二元关系的集，即R={H}。 H为如下描桢郓羼抱述的二元关系：在D中存在惟一的称为根的数据元素，它在关系H下无前驱： (Di,{Hi})是一棵符合本定义的树，称为根root的子树。

3、树有10种基本操作

4、树形图表示 节点用圆圈表示，节点的名字写在圆圈旁边（有时亦可写在圆圈内）。

5、分析上图：A为根节点，可以分为3个子树T1={B，E，F，I，J}，T2={C}，T3={D，G，H}

6、节点的度（Degree）： 树中的一个节点拥有的子树数称为该节点的度（Degree）。一棵树的度是指该树中节点的最大度数，度为零的节点称为叶子（Leaf）或终端节点，度不为零的节点称为分支节点或非终端节点。

7、孩子（Child）和双亲（Parents） 树中某个节点的子树之根称为该节点的孩子(Child)或儿子，相应地，该节点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。

8、祖先（Ance衡痕贤伎stor）和子孙（Descendant） 若树中节点k到ks存在一条路径，则称k是ks的祖先（Ancestor），ks是k的子孙（Descendant）。一个节点的祖先是从根节点到该节点路径上所经过的所有节点，而一个节点的子孙则是以该节点为根的子树中的所有节点。

9、节点的层数（Level）和树的高度（Height） 节点的层数（Level）从根起算：根的层数为1，也有很多文献中将树根的层数定义为0。其余节点的层数等于其双亲节点的层数加1。树中节点的最大层数称为树的高度（Height）或深度（Depth）。

10、二叉树与普通的树形结构是截然不同的：

11、二叉树具有以下重要性质：1、二叉树第i层上的节点数目最多为2i-1(i≥1)。2、深度为k的二叉树至多有2k-1个节点（k≥1）。3、在任意一棵二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则n0=n2+1。

12、满二叉树与完全二叉树是二叉树的两种特殊情况。

13、满二叉树(Full Binary Tree)是一棵深度为k且有2k-1个节点的二叉树称为满二叉树。

14、满二叉树的特点：1、每一层上的节点数都达到最大值。2、满二叉树中不存在度数为1的节点，每个分支节点均有两棵高度相同的子树，且树叶都在最下一层上。

15、完全二叉树（Complete Binary Tree）：若一棵二叉树最多只有最下面的两层上节点的度数可以小于2，并且最下一层上的节点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

16、完全二叉树的特点：1、满二梆梯陶瘦叉树是完全二叉树，完全二叉树不一定是满二叉树。2、在满二叉树的最下一层上，从最右边开始连续删去若干节点后得到的二叉树仍然是 一棵完全二叉树。3、在完全二叉连含哲叨树中，若某个节点没有左孩子，则它一定没有右孩子，即该节点必是叶节点。

17、树的顺序存储，该方法是把二叉树的所有节点按照一定的线性次序存储到一片连续的存储单元中。树的编号，从树根起，自上层到下层，每层从左至右。

18、完全二叉树的顺序存储将完全二叉树中所有节点按编号顺序依次存储在一个向量bt[0……n]中。其中：bt[1……n]用来存储节点。bt[0]不用或用来存储节点数目。

19、一般二叉树的节点不一定总有2个子树，可以填充虚节点，使之成为完全二叉树。

20、二叉树的每个节点最多有两个孩子，一个树节点（TreeNode）包含一个数据域和两个指针域，指针域被称为“左指针（LeftNode）”和“右指针（RightNode）”，它们分别指向节点的左右子树。NULL表示一棵空树。

21、在一棵二叉树中，所有类型为BinTNode的节点，再加上一个指向开始节点（即根节点）的BinTree型头指针（即根指针）root，就构成了二叉树的链式存储结构，并将其称为二叉链表。

22、二叉树的链式存储结构，二叉链表。二叉链表的特点：1、一个二叉链表由根指针root惟一确定。2、具有n个节点的二叉链表中，共有2n个指针域。

23、二叉树遍历：遍历（Traversal）是指沿着某条搜索路线，依次对树中每个节点均做一次且仅做一次访问。1、NLR：前序遍历（PreorderTraversal，亦称先序遍历）。2、LNR：中序遍历（InorderTraversal）3、LRN：后序遍历（PostorderTraversal）N（Node）：根本身L（ Left subtree ）：根的左子树R（ Right subtree）：根的右子树