C++数据结构之树

树在数据结构是一个极其重要的存在，例如二叉树，排序二叉树，平衡二叉树，红黑树等等在许多项目中运用比较广，而且也是平时考察的重点，所以今天就来系统地谈一谈树

树

定义：n个结点的有限集合，当n等于0时，称为空树，n个结点的树只有n-1条边,有如下性质。

1. 有且仅有一个特定的称为根的结点

2. 当n>1时，其余结点可分为m个互不相交的有限集合，其中每一个集合本身又是一颗树，称为根节点的子树（n个结点的树中只有n-1条边）

3. 树中的一个结点的子结点的个数称为该结点的度，树中最大度数称为树的度

4. 度大于0的结点称为分支节点，度为0的结点称为叶子结点

5. 结点的层次，结点的高度（是树中结点的最大层数），结点的深度

6. 有序树和无序数

7. 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的

8. 路径长度：路径上所经历边的个数

9. 森林：m棵互不相交的树的集合

10. 树中的结点数等于所有结点的度数加1

11. 度为m的树中第i层上至多有m**(i-1)个结点

12. 高度为h的m叉结点至多有(m**h -1)/(m-1)个结点

13. 具有n个结点的m叉树的最小高度为[logm (n(m-1)+1)]

二叉树
二叉树是n(n=0)个结点的有限集合

• n=0，二叉树为空
• n>0，由根节点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树叶分别是一颗二叉树

基本形态

• 空，根节点，左子树，右子树，二叉树

满二叉树：一棵高度为h，且含有2**h-1的结点的二叉树为满二叉树（对于编号为i的结点，若存在，其双亲的编号为i/2，左孩子为2i，右孩子为2i+1）

完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树（相当于满二叉树的子集）

二叉树的存储结构

顺序存储：用数组类似的一片连续的内存空间来存储，若存在左孩子，则为2i，右孩子为2i+1


顺序存储最坏情况下会非常浪费内存空间，因此比较适合完全二叉树。

链式存储：用链表来存放一颗二叉树，二叉树中每个结点用链表的一个链结点来存储.

typedef struct BiTNode {
	// 数据域
	ElemType data;
	// lchild指向左孩子，rchild指向右孩子
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

含有n个结点的链表中，有n-1个空链域

二叉树的遍历

先序遍历

1. 根节点
2. 左子树
3. 右子树

void PreOrder(BiTree T) {
	if (T != nullptr) {
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

中序遍历

1. 左子树
2. 根节点
3. 右子树

void InOrder(BiTree T) {
	if (T != nullptr) {
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

后序遍历

1. 左子树
2. 右子树
3. 根节点

void PostOrder(BiTree T) {
	if (T != nullptr) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

中序遍历非递归算法

• 初始时一次扫描根节点的所有左侧结点并将它们一一进栈
• 出栈一个结点，访问他
• 扫描该结点的右孩子结点并将其进栈
• 一次扫描右孩子结点的所有左侧结点并一一进栈
• 反复该过程直到栈空为止

#include <stack>
void InOrder(BiTree T) {
	// 初始化一个栈
	stack<BiTree> s;
	// 构造一个二叉树
	BiTree p = T;
	while (p != nullptr || s.empty() == 1) {
		if (p != nullptr) {
			// 进栈
			s.push(p);
			p = p->lchild;
		} else {
			// 返回栈顶元素
			p = s.top();
			s.pop();
			p = p->rchild();
	}
	}
}

层次遍历

• 初始将跟入队并访问根节点，然后出队
• 若有左子树，则将左子树的根入队
• 若有右子树，则将右子树的根入队
• 然后出队，访问该结点
• 反复该过程直到队列为空为止

#include <queue>
void LevelOrder(BiTree T) {
	queue<BiTree> q;
	BiTree b;
	q.push(b);
	while(q.empty() == 1) {
		q.pop(b);
		if (b->lchild != nullptr) {
			q.push(b->lchild);
		}
		if (b->rchild != nullptr) {
			q.push(p->rchild);
		}
	}
}

线索二叉树
对于二叉树中的空指针域，为了不浪费内存，故使用线索化的线索二叉树，基本原理：
若无左子树，则将左指针指向前驱结点；
若无右子树，则将右指针指向后驱结点；

typedef struct ThreadNode {
	ElemType  data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;
}ThreadNode, *ThreadTree;

待写

最后

以上就是端庄发箍为你收集整理的C++数据结构之树的全部内容，希望文章能够帮你解决C++数据结构之树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。