首页 > 代码库 > 数据结构——树笔记1
数据结构——树笔记1
树属于非线性数据结构，它是一种层次结构：如果存在前驱节点，则是唯一
的，如果存在后继节点，则可以是多个。即树的元素之间是一对多的关系。
树是由n个节点构成的有限集合T，如果n = 0，则是空树，如果n不等于0，则
一个非空树，有且只有一个根结点root，如果n>1，则除了根结点外，其余节
点又可以划分为有限集T1，T2......Tm 其中每个有限集有是一棵树。称为子
树subtree.
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法（二叉树表示法）
森林：M棵互不相交的树的集合。
二叉树：
二叉树的特点是每个节点至多只有两颗子树，并且二叉树的子树有左右之
分，它的次序不能任意颠倒。
二叉树的特点：
在二叉树的第i层上至多有2的i-1次方个节点
深度为k的二叉树至多有2的k次方-1个节点
如果一颗二叉树的终端节点的数目为i，深度为2的节点数目为j，则i=j+1
满二叉树：深度为k且节点数目为2的k次方-1的二叉树
完全二叉树：只有在最下面一层的右边缺少若干个节点的满二叉树
二叉树的存储结构：
按顺序储存，即使用一组连续的储存单元，自上而下，自左而右的储存，每
个空节点也会占用一个储存单元。这样的储存方式只适合完全二叉树，因为
会浪费大量空间。
链式储存结构：二叉树的节点至少包括三个域，数据域和指向左右子树的指
针域，有时候也增加一个指向双亲的指针域来方便指向节点的双亲。
二叉树的遍历：以一定的规则将非线性的节点排列成线性序列
先序遍历二叉树：
先访问根结点，再先序遍历左子树，最后先序遍历右子树
中序遍历二叉树
先中序遍历左子树，在访问根结点，最后中序遍历右子树
后序遍历二叉树
先后序遍历左子树，在后序遍历右子树，最后访问根结点
在已知两种遍历的情况下可以得出原二叉树的形状，这两种遍历可以是先序
和后序，也可以是中序和后序
// 二叉树的初始化 void Init_BitTree(BiTree * T) { *T = NULL; return; } // 销毁二叉树 void Destroy_BitTree(BiTree * T) { if ((*T)->lchild) Destroy_BitTree(&((*T)->lchild)); if ((*T)->rchild) Destroy_BitTree(&((*T)->rchild)); free(*T); *T = NULL; return; } // 二叉树的插入，通过判断LR的值，判断插入选择 int Insert_Child(BiTree p, int LR, BiTree c) { if (p) // p指向的二叉树非空 { if (0 == LR) { c->rchild = p->lchild; // p原来的左子树称为c的右子树 p->lchild = c; // 子树c作为p的左子树 } else { c->rchild = p->rchild; p->rchild = c; return 1; } } return 0; } // 返回二叉树e的左孩子节点的元素值 int Left_Child(BiTree T, int e) { BiTree p; if (T) // 当二叉树T不为空时 { p = Point(T, e); // p是元素值e的节点的指针 if (p && p->lchild) // 如果p的节点不为空，且p的左孩子节点存在 return p->lchild->data; // 返回左孩子节点的元素值 } return 0; } // 返回二叉树e的右孩子节点的元素值 int Right_Child(BiTree T, int e) { BiTree p; if (T) // 当二叉树T不为空时 { p = Point(T, e); // p是元素值e的节点的指针 if (p && p->rchild) // 如果p的节点不为空，且p的左右孩子节点存在 return p->rchild->data; // 返回右孩子节点的元素值 } return 0; } // 在二叉树中寻找元素值为e的节点，此处假定该二叉树的节点元素值各不相同，如果找到返回该节点的地址，否则返回NULL BiTree Point(BiTree T, int e) { if (e == T->data) { return T; } else { if (T->lchild != NULL) Point(T->lchild, e); if (T->rchild != NULL) Point(T->rchild, e); } return NULL; } // 删除子树操作，根据LR的值选择删除的是左子树还是右子树 int Delete_Child(BiTree p, int LR) { if (p) // 判断p不空 { if (0 == LR) Destroy_BitTree(&(p->lchild)); else Destroy_BitTree(&(p->rchild)); return 1; } return 0; }
数据结构——树笔记1