树是一类重要的非线性数据结构,是以分支关系定义的层次结构
定义:树(tree)是n(n>=0)个结点的有限集T,其中:
n=0时为空树
n>0时,有且仅有一个特定的结点,称为树的根(root)
当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,
其中每一个集合本身又是一棵树,称为根的子树(subtree)
特点:
非空树中至少有一个结点——根
树中各子树是互不相交的集合
基本概念:
结点(node)——表示树中的元素,包括数据项及若干指向其子树的分支
结点的度(degree)——结点拥有的子树数
叶子(leaf)——度为0的结点
孩子(child)——结点子树的根称为该结点的孩子
双亲(parents)——孩子结点的上层结点叫该结点的~
兄弟(sibling)——同一双亲的孩子
树的度——一棵树中最大的结点度数
结点的层次(level)——从根结点算起,根为第一层,它的孩子为第二层……
深度(depth)——树中结点的最大层次数
森林(forest)——m(m>=0)棵互不相交的树的集合
二叉树
定义:二叉树是n(n>=0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为
左子树和右子树的互不相交的树构成
特点:
每个结点至多有二棵子树(即不存在度大于2的结点)
二叉树的子树有左、右之分,且其次序不能任意颠倒
性质:1.在二叉树的第i层至多有 2i-1 个结点(i>=1)
2.深度为k的二叉树至多有 2k-1 个结点(k>=1)
3.对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
证明:n1为二叉树T中度为1的结点数
因为:二叉树中所有结点的度均小于或等于2
所以:其结点总数n=n0+n1+n2
又二叉树中,除根结点外,其余结点都只有一个分支进入
设B为分支总数,则n=B+1
又:分支由度为1和度为2的结点射出,即 B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
即:n0=n2+1
满二叉树
定义:一个深度为k,且有2k-1个结点的二叉树
完全二叉树
定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都
与深度为k的满二叉树中编号从1至n的结点一一对应
特点:
叶子结点只可能在层次最大的两层上出现
对任一结点,若其右分支下子孙的最大层次为i,则其左分支下子孙的最大层次必为i或i+1
性质:4.具有k个结点的完全二叉树,深度为(log2k)向下取整再加一
性质:5.如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1<=i<=n),有:
(1) 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是i/2
(2) 如果2i>n,则结点i无左孩子;如果2i<=n,则其左孩子是2i
(3) 如果2i+1>n,则结点i无右孩子;如果2i+1<=n,则其右孩子是2i+1
二叉树的遍历
方法
先序遍历:先访问根结点,然后分别先序遍历左子树、右子树
中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树
后序遍历:先后序遍历左、右子树,然后访问根结点
按层次遍历:从上到下、从左到右访问各结点
参考代码:
void printq(Tree *T) { if(T!=NULL){ printf("%c",T->c); printq(T->l); printq(T->r); } }
void printz(Tree *T) { if(T!=NULL){ printz(T->l); printf("%c",T->c); printz(T->r); } }
void printh(Tree *T) { if(T!=NULL){ printh(T->l); printh(T->r); printf("%c",T->c); } }
void ccbl(Tree *T) { q.push(T); while(!q.empty()){ T=q.front(); q.pop(); printf("%c",T->c); if(T->l!=NULL) q.push(T->l); if(T->r!=NULL) q.push(T->r); } }
原文:http://www.cnblogs.com/happy-lcj/p/3855452.html