| 二叉树的基本操作(C++实现) | 您所在的位置：网站首页 › 遍历求二叉树 › 二叉树的基本操作(C++实现) |
二叉树的基本操作(C++实现)
|
基本概念
二叉树由结点的有限集合构成。 这个有限集合要么是空集，要么是一个根节点及两棵互不相交、分别称为这个跟的左子树和右子树的二叉树组成的集合。 二叉树的特点 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。左子树和右子树是有顺序的，次序不能随意颠倒。及时树中某结点只有一颗子树，也要区分它是左子树还是右子树。 二叉树的五种基本形态 空二叉树只有一个根节点根节点只有左子树根节点只有右子树根节点既有左子树，又有右子树 相关概念边（edge）：两个结点（node）的有序对（order pair），称为边 结点的度：一个节点含有的子树的个数成为该结点的度 叶节点：度为0的结点成为叶节点 路径（path） 路径长度（the length of the paths） 层数：根是第0层（其他结点的层数等于其父节点的层数加1） 深度：层数最大的叶节点的层数 二叉树相关结论
二叉树的顺序存储结构一般只适用于完全二叉树，通常我们表示二叉树时，都是使用链式存储结构的。 二叉链表二叉树每个结点最多有两个孩子，所以它有一个数据域和两个指针域。 我们称这样的链表叫做二叉链表。 如图： lchilddatarchild其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针 二叉树的二叉链表结构定义 /*定义二叉树的结构*/ typedef struct Node { char data; /*数据域*/ struct Node *lchild, *rchild; /*左子树和右子树*/ } * BiTree, BiNode; /*整棵树和结点名称*/ 二叉树的遍历遍历（traversal） 系统地访问数据结构中的结点，使得每个结点都正好被访问一次 深搜有限遍历二叉树： 以下是三种深度优先遍历的递归定义： 前序遍历规则：若二叉树为空，则操作返回，否则，先访问根节点，然后前序访问左子树，之后前序访问右子树 按中序遍历左子树，访问根节点，按中序遍历右子树 之前看过大佬对中序遍历的解释：把每一个结点都看成一颗颗葡萄，把这些葡萄垂直投影到同一平面上，然后从左到右访问，即为中序遍历。 后序遍历按后序遍历左子树，按后序遍历右子树，访问根节点 先序遍历：先根 再左 再右 中序遍历：先左 再根 再右 后序遍历：先左 再右 再根 这个根，指的是每个分叉子树（左右子树的根节点）根节点并不只是整棵树的根节点 代码 #include #include #include using namespace std; /*定义二叉树的结构*/ typedef struct Node { char data; /*数据域*/ struct Node *lchild, *rchild; /*左子树和右子树*/ } * BiTree, BiNode; /*整棵树和结点名称*/ /*先需创建二叉树*/ void CreateBiTree(BiTree &T) { char ch; cin >> ch; if (ch == '#') T = NULL; else { T = new BiNode; /*创建一个新节点*/ T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } /*递归创建*/ } void InOrderTraverse(BiTree T) { /*中序遍历*/ if (T) { InOrderTraverse(T->lchild); cout rchild); } } void PreOrderTraverse(BiTree T) { /*先序遍历*/ if (T) { cout lchild); PreOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T) { /*后序遍历*/ if (T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout if (T == NULL) return 0; else { int i = Depth(T->lchild); int j = Depth(T->rchild); return i > j ? i + 1 : j + 1; } } /*复制二叉树*/ void Copy(BiTree T, BiTree &NewT) { if (T = NULL) { NewT = NULL; return; } else { NewT = new BiNode; NewT->data = T->data; Copy(T->lchild, NewT->lchild); Copy(T->rchild, NewT->rchild); } } /*统计二叉树中叶子结点的个数*/ int LeafCount(BiTree T) { if (!T) return 0; if (!T->lchild && !T->rchild) return 1; /*如果二叉树左子树和右子树皆为空，说明该二叉树根节点为叶子结点，结果为1*/ else return LeafCount(T->lchild) + LeafCount(T->rchild); } /*二叉树中从每个叶子结点到跟结点的路径*/ void PrintAllPath(BiTree T, char path[], int pathlen) { int i; if (T != NULL) { path[pathlen] = T->data; /*将当前结点放入路径中*/ if (T->lchild == NULL && T->rchild == NULL) { /*若这个节点是叶子结点*/ for (i = pathlen; i >= 0; i--) cout if (T) return 1; else return 0; } int main() { BiTree T; //测试数据AB#CD##E##F#GH### cout |
【本文地址】
公司简介
联系我们