树,根,子树;结点,结点的度,叶子(终端结点),分支结点(非终端结点),内部结点,树的度;孩子,双亲,兄弟,祖先,子孙,堂兄弟;层次(根所在层为第1层),深度,高度;有序树,无序树,二叉树是有序树;森林。
满二叉树:深度为k,有2k-1个结点。
完全二叉树:给满二叉树的结点编号,从上至下,从左至右,n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。
二叉树的五种基本形态:
①空树:T==NULL
②左右子树均空:T->lchild==NULLandT->rchild==NULL
③右子树为空:T->rchild==NULL
④左子树为空:T->lchild==NULL
⑤左右子树均非空。
二叉树的遍历:
按层次遍历,先序遍历,中序遍历,后序遍历。按层次遍历:“从上至下,从左至右”,利用队列。
先序遍历:DLR;中左右
中序遍历:LDR;左中右
后序遍历LRD。左右中
|