1.树 1.1 树的特性 树是不包含回路的连通无向图 树的特性： 一棵树的任意两个结点有且仅有唯一的一条路连通； 一颗树有n个结点，那么就一定恰好有n-1条边； 在一棵树加一条边将会构成一个回路； 1.1.1树的存储结构 //孩子结点 struct childnode { int child; //孩子结点的坐标 struct childnode *next;//指向下一个孩子的指针 }; //表头结构 struct tbox { int data; //存放在树中结点的数据 int parent; //存放双亲的下标 struct childnode *firstchild;//指向第一个孩子的指针 }; //树结构 struct tree { struct tbox t[2020];//结点数组 } 1.2 二叉树 1.2.1 特点：每个结点最多有两个儿子 1.2.2： 满二叉树：如果二叉树中每个内部的结点都有两个儿子 完全二叉树：除了最右边的位置有一个或几个叶结点缺少外，其他是丰满的。 如果完全二叉树的一个父结点编号为k 那么它左二子的编号为2k 右二子的编号为2k+1 如果已知儿子的编号是x 那么它父结点的编号就是x/2 如果一颗完全二叉树有n个结点，哪儿买这个完全二叉树的高度为log以2为底n 1.2.3二叉树的存储结构 1.链式存储结构 struct bitnode { int data; struct bitnode *lchild,*rchild;//分别指向左右结点 }; 1.2.4二叉树的遍历 前序遍历： 若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树 中序遍历 若树为空，则空操作返回，否则从根结点开始（并不是指先遍历根结点，而是当遍历下一个左节点为空时遍历根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历根节点的右子树。 后序遍历 若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右结点，最后访问根节点 1.2.5树的创建与前序遍历 #include #include #include typedef