基本
结点的度:结点拥有的子树的数目。
叶子:度为零的结点。
分支结点:度不为零的结点。
树的度:树中结点的最大的度。
层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1。
树的高度:树中结点的最大层次。
无序树:如果树中结点的各子树之间的次序是不重要的,可以交换位置。
有序树:如果树中结点的各子树之间的次序是重要的, 不可以交换位置。
森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。
性质
1:二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
2:深度为k的二叉树至多有2{k}-1个结点(k≥1)。
3:包含n个结点的二叉树的高度至少为log2 (n+1)。
4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。
C实现
用先序序列创建一棵二叉树,并且输出字符D位于二叉树的层数。
#include "stdio.h" #include "stdlib.h" typedef struct BiTNode{ char data; /*结点的数据域*/ struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/ } BiTNode , *BiTree; /*创建一棵二叉树*/ void CreatBiTree(BiTree *T){ char c; scanf("%c",&c); if(c == ' ') *T = NULL; else{ *T = (BiTNode * )malloc(sizeof(BiTNode)); /*创建根结点*/ (*T)->data = c; /*向根结点中输入数据*/ CreatBiTree(&((*T)->lchild)); /*递归地创建左子树*/ CreatBiTree(&((*T)->rchild)); /*递归地创建右子树*/ } } /*访问二叉树结点,输出包含D字符结点位于二叉树中的层数*/ void visit(char c,int level){ if(c == 'D') printf("%c is at %d lever of BiTree\n",c,level); } /*遍历二叉树*/ void PreOrderTraverse(BiTree T,int level){ if(T){ /*递归结束条件,T为空*/ visit(T->data,level); /*访问根结点*/ PreOrderTraverse(T->lchild,level+1); /*先序遍历T的左子树*/ PreOrderTraverse(T->rchild,level+1); /*先序遍历T的右子数*/ } } void main() { int level = 1; BiTree T = NULL; /*最开始T指向空*/ CreatBiTree(&T); /*创建二叉树*/ PreOrderTraverse(T,level); /*遍历二叉树,找到包含D字符结点位于二叉树中的层数*/ } 本文转自我爱物联网博客园博客,原文链接:http://www.cnblogs.com/yydcdut/p/3678697.html如需转载请自行联系原作者