计算机：二叉树是每个节点最多有两个子树的树结构
图论：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2
1 五种形态
- 空二叉树
- 只有一个根结点的二叉树
- 只有左子树
- 只有右子树
- 完全二叉树
2 遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）
-
先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树 -
中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树 -
后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根 -
层次遍历
即按照层次访问。访问根，访问子女，再访问子女的子女
3 性质
- **一个二叉树第i 层的最大结点数为：2i-1，i ≥ 1 **
- **深度为k 的二叉树有最大结点总数为：2k-1，k ≥ 1 **
- **对任何非空二叉树T，若n0 表示叶结点的个数，n2 是度为2 的非叶结点个数，那么两者满足关系n0 = n2 + 1 **
4 程序描述
-
数据来源
括号表示法，以及类似表示方法 -
类型
typedef struct BTNode * BinaryTree;
typedef char ElementType;
typedef struct Node{
ElementType data;
struct Node * left;
struct Node * right;
} BTNode;
- 函数
BinaryTree InitBinaryTree()：创建一个二叉树，通过某个方式构建二叉树
boolean IsEmpty(BinaryTree tree)：判别BT 是否为空
BTNode * InsertNode(BTNode * parent, BTNode * new，int position) ：插入新节点（0，左；1，右）
void Traversal(BinaryTree tree)：遍历，按某顺序访问每个结点
void PreOrder(BinaryTree tree)：先序——根、左子树、右子树
void InOrder(BinaryTree tree)：中序——左子树、根、右子树
void PostOrder(BinaryTree tree)：后序——左子树、右子树、根
void HierarchyOrder(BinaryTree tree)：层次遍历——从上到下
void Print(BinaryTree tree)：打印二叉树
void Destroy(BinaryTree tree)：销毁二叉树
- 其他操作
BTNode * Search(BinaryTree tree,ElementType x) ： 二叉树中查找元素
网友评论