主要描述二叉树。
李柱明博客:https://www.cnblogs.com/lizhuming/p/15487394.html
树:
结点:
结点的度:结点拥有的子树数。
叶结点或终结点:度为 0 的结点。
非终结点或分支结点:度不为 0 的结点。
内部结点:除根结点外,分支结点也称为内部结点。
树的度:树内各结点的度的最大值。
结点关系:
树的其它相关概念:
简单的顺序存储结构无法直接反映逻辑关系,不能满足树的实现要求。
故充分利用顺序存储和链式存储结构的特点,介绍三种不同的表示法:
引入:除根节点外,其余每个结点,不一定有孩子,但一定有且仅有一个双亲
定义:设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。
缺点:
上述第一个缺点引发的思考:
需要关注什么数据域就在数据结构中添加什么数据域。如双亲域、长子域、兄弟域等等。
参考代码:
/* 树的双亲表示法结点数据结构 */ #define MAX_TREE_SIZE 100 typedef int tree_elem_type; /* 结点结构 */ typedef struct tree_node { int parent; // 双亲位置 // int firstchild; // 长子位置 // int rightsib; // 右兄弟位置 tree_elem_type data; // 数据 }tree_node_t; /* 树结构 */ typedef struct tree { int root; // 根节点位置 int num; // 当前节点数 tree_node_t nodes[MAX_TREE_SIZE]; }tree_t;
多重链表表示法:
方案 1:
方案 2:
孩子表示法:
把每个结点的孩子结点排列起来,以单链表作存储结构,则 n 个结点有 n 个孩子链表,如果是叶子结点,则此单链表为空。然后 n 个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。
孩子表示法的两种结点数据结构:
缺点:找双亲需要遍历树。
参考代码:
/* 树的孩子表示法结点数据结构 */ #define MAX_TREE_SIZE 100 typedef int tree_elem_type; /* 孩子结点结构 */ typedef struct c_tree_node { int child; // 孩子下标 struct c_tree_node *next; // 下一个 }c_tree_node_t; /* 表头结构 */ typedef struct tree_top { c_tree_node_t *firstchild; // 头结点 tree_elem_type data; // 数据 }tree_top_t; /* 树结构 */ typedef struct tree { int root; // 根节点位置 int num; // 当前节点数 tree_top_t nodes[MAX_TREE_SIZE]; }tree_t;
引入:
参考代码:
/* 树的孩子兄弟表示法结点数据结构 */ typedef int tree_elem_type; typedef struct tree_node { struct tree_node *firstchild; // 长子域 struct tree_node *rightsib; // 右兄域 tree_elem_type data; // 数据 }tree_node_t;
二叉树的定义:
二叉树特点:
二叉树的五种基本形态:
左斜树&右斜树:
满二叉树:
定义:所有分支结点都存在左右子树,并且所有叶子都在同一层。
特点:
完全二叉树:
定义:对一棵具有 n 个结点的二叉树按层序编号,如果编号 i(1<=i<=n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同,则此二叉树为完全二叉树。
特点:
判断方法:给每个结点按满二叉树的结构逐层排序,如果编号出现空档,就不是,否则就是。
性质 1:在二叉树的第 i 层上至多有 2i-1 个结点(i>=1)。
性质 2:深度为 k 的二叉树至多有 2k-1 个结点(k>=1)。
性质 3:对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则 n0 = n2+1。
性质 4:具有 n 个结点的完全二叉树的深度为[log2n ] + 1([X]表示不大于 X 的最大整数)。
性质 5:如果对一颗有 n 个结点的完全二叉树(其深度为[log2n ] + 1)的结点按层序编号(从第 1 层到第[log2n ] + 1 层,每层从左到右),对任一结点 i(1<=i<=n)有:
有顺序存储结构和链式存储结构。
二叉树的顺序存储结构:
二叉树的链式存储结构:
链表每个结点包含一个数据域和两个指针域:
遍历是二叉树中非常重要的操作。
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点都被访问 1 次。
四种遍历方法:
前、中、后序表示的是节点与它的左右子树节点遍历打印的先后顺序。
实现思路:递归。
前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
代码实现思路:
中-> 左 -> 右。使用栈辅助实现。
参考代码(递归):
/* 顺序存储结构 */ void pre_order_traverse(bi_tree tree,int e) { visit(tree[e]); // 打印父节点 if(tree[2*e+1]!=nil) /* 左子树不空 */ pre_traverse(tree,2*e+1); // 递归 if(tree[2*e+2]!=nil) /* 右子树不空 */ pre_traverse(tree,2*e+2); // 递归 } /* 链式存储结构 */ void pre_order_traverse(bi_tree *tree) { if(tree==NULL) return; printf("%c",tree->data);/* 显示结点数据,可以更改为其它对结点操作 */ pre_order_traverse(tree->lchild); /* 再先序遍历左子树 */ pre_order_traverse(tree->rchild); /* 最后先序遍历右子树 */ }
中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树
代码实现思路:
左-> 中 -> 右。使用栈辅助实现。
参考代码(递归):
/* 顺序存储结构 */ void in_order_traverse(bi_tree tree,int e) { if(tree[2*e+1]!=nil) /* 左子树不空 */ in_traverse(tree,2*e+1); // 递归 visit(tree[e]); // 打印父节点 if(tree[2*e+2]!=nil) /* 右子树不空 */ in_traverse(tree,2*e+2); // 递归 } /* 链式存储结构 */ void in_order_traverse(bi_tree *tree) { if(tree==NULL) return; in_order_traverse(tree->lchild); /* 再先序遍历左子树 */ printf("%c",tree->data);/* 显示结点数据,可以更改为其它对结点操作 */ in_order_traverse(tree->rchild); /* 最后先序遍历右子树 */ }
后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。
代码实现思路:
左-> 右 -> 中。
参考代码(递归):
/* 顺序存储结构 */ void post_order_traverse(bi_tree tree,int e) { if(tree[2*e+1]!=nil) /* 左子树不空 */ post_traverse(tree,2*e+1); // 递归 if(tree[2*e+2]!=nil) /* 右子树不空 */ post_traverse(tree,2*e+2); // 递归 visit(tree[e]); // 打印父节点 } /* 链式存储结构 */ void post_order_traverse(bi_tree *tree) { if(tree==NULL) return; post_order_traverse(tree->lchild); /* 再先序遍历左子树 */ post_order_traverse(tree->rchild); /* 最后先序遍历右子树 */ printf("%c",tree->data);/* 显示结点数据,可以更改为其它对结点操作 */ }
根起,从上而下,从左至右。
对于顺序存储,只需要按下标顺序输出即可。
但是对于链式存储结构就复杂点,思路如下:借助队列的方式实现:
/* 顺序存储结构:直接打印数组 */ void level_order_traverse(bi_tree tree) { int i=MAX_TREE_SIZE-1; int j=0; while(tree[i]==nil) i--; /* 找到最后一个非空结点的序号 */ for(j=0;j<=i;j++) /* 从根结点起,按层序遍历二叉树 */ if(tree[j]!=nil) visit(tree[j]); /* 只遍历非空的结点 */ printf("\n"); } /* 链式存储结构:借助队列 */ void level_order_traverse(bi_tree_node* tree) { bi_tree_node* temp = NULL; queue_push(tree); // 跟节点入队 while (!queue_empty()) { temp = queue_pop(); printf("%d ", temp->data); //输出队首结点 if (temp->left) //把Pop掉的结点的左子结点加入队列 queue_push(temp->left); if (temp->right) // 把Pop掉的结点的右子结点加入队列 queue_push(temp->right); } }
二叉树的扩展二叉树:
二叉树除了根节点,其余节点最多有三条线:
树转换为二叉树的步骤:
加线:所有兄弟结点之间加一条线。
去线:对树中每个结点,只保留与第一个孩子的线。删除与其它孩子的线。
层次调整:
森林转换为二叉树的步骤:
二叉树转为树的步骤:
二叉树的根节点有右孩子,则说明该二叉树可以就可以转换为森林。
二叉树转换为森林的步骤:
树的遍历有两种:
森林的遍历也有两种: