1.树的概念
非线性数据结构,有n个结点组成的有层次关系的集合 结点的度:一个结点含有的子树的个数(就是它下面的分指数) 叶子结点:度为0的结点 分支结点:除了叶子结点之外的结点 双亲结点(父结点):上面的结点 子结点:下面的结点 兄弟结点:有相同父结点的结点 树的度:最大结点的度 结点的层次:根节点为第一层 树的深度:最大的层数 堂兄弟结点:双亲在同一层的结点 祖先结点:到则合格结点的所有的结点 子孙节点:结点之下的所有结点 森林:M棵互不相交的树组成的集合
2.树的表示方法
1.双亲表示法 节点指向它的双亲 struct Node{ TDataType_data; struct Node* parent; }; 2.孩子表示法 typedef int DataType; struct Node{ struct Node* Child1; struct Node* Child2; struct Node* Child3; }; 3.孩子兄弟表示法 typedef int DataType; struct Node{ struct Node* Child1; struct Node* Child2; struct Node* Child3; struct Node* pNextBrother; DataType data; };
3.二叉树
二叉树概念: 1.空树 2.根节点+根节点的左子树+根节点的右子树 3.最多两棵子树 满二叉树:每层节点数都达到最大值 完全二叉树:与其对应的满二叉树的节点编号一致
二叉树性质: 1.规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点 2.只有根节点的二叉树深度为1,则深度为k的二叉树的最大节点数是2^k-1 3.对任意二叉树,如果其叶子节点个数为n0,度为2的非叶子节点个数为n2,则 n0=n2+1 4.具有n个结点的完全二叉树的深度为log以2为底的 n+1 5.对于有n个结点的完全二叉树,从0开始编号,对于第i个节点 若i>0,双亲序号为(i-1)/2 若i=0,则一定是根节点 左孩子是2i+1<n,否则无左孩子 右孩子是2i+2<n,否则无右孩子
二叉存储方式: 顺序结构: 完全二叉树:使用数组存储 普通二叉树:先补充全二叉树,数组里补NULL 链式结构: 左右指针域和数据域
