1. 首页
  2. 文章中心
  3. 综合-数据结构和算法

数据结构：二叉树的遍历

69 阅读 0 评论
我是靠谱客的博主 殷勤冰棍，这篇文章主要介绍数据结构：二叉树的遍历，现在分享给大家，希望可以做个参考。

一、树的性质

1、树的度：树的度是树内各节点中度的最大值。
2、二叉树的性质
  • 在二叉树的第i层上之多有2i-1个结点（i >= 1）。
  • 深度为k的二叉树至多有2k-1个结点。
  • 对于任何一棵二叉树T，如果其终端节点数为n0，度为2的结点数为n2，则：n0 = n2 + 1;
  • 满二叉树：深度为k，且含有2k-1个结点的二叉树。
  • 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，称之为完全二叉树。
  • 具有n个结点的完全二叉树的深度为log2n + 1。
  • 如果对任一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（1 <= i <= n），有：
    当i=1时，其为根节点；如果i>1，则其双亲结点为 i/2 取下；
    当2i > n时，则结点i没有 左孩子，否则2i为结点i的左孩子；
    当2i+1 > n时，则结点i没有 右孩子，否则2i+1 为结点i的右孩子；

二、二叉树的存储结构

1、顺序存储
复制代码
1
2
3
4
#define MAXSIZE 100
typedef TElemType sqBiTree[MAXSIZE];
sqBiTree bt;
2、链式存储
复制代码
1
2
3
4
5
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

三、二叉树的遍历

1、先序遍历

parent -> lchild -> rchild

复制代码
1
2
3
4
5
6
7
8
void PostOrderTraverse(BiTree T){
if(T){
cout<<T->data;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
}
}
2、中序遍历
2.1 递归操作

lchild -> parent -> rchild

复制代码
1
2
3
4
5
6
7
8
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}
2.2 非递归操作
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InOrderTraverse(BiTree T){
InitStack(S); //初始化一个栈
p = T; 
q = new BiTNode;
while(p || !StackEmpty(S)){
if(p){
Push(S,p); //遍历结点p
p = p->lchild; //准备遍历结点p的左孩子
}
else{ //如果p的左孩子为空
Pop(S,q); //将栈顶元素pop出（p）
cout<<q->data; //输出该元素
p=q->rchild; //遍历p的右孩子
}
}
}
3、后序遍历

lchild -> rchild -> parent

复制代码
1
2
3
4
5
6
7
8
void PreOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
cout<<T->data;
}
}

给定一棵树的序列：BDCEAFHG，只能通过“先序和中序遍历” 或者 “后序和中序遍历” 获得树的结构。
“先序和后序遍历” 不能获得树的结构。

四、二叉树遍历算法的应用

1、利用先序遍历 创建 二叉树
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
//当输入为 '#' 时，表示输入结束。
void CreateBiTree(BiTree &T){
cin>>ch;
if(ch == '#'){T=NULL;}
else{
T=new BiTNode;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
2、利用先序遍历 复制二叉树
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//利用先序遍历 复制二叉树
void Copy(BiTree T,BiTree &NewT){
if(!T){
NewT = NULL;
return;
}
else{
NewT=new BiTNode;
NewT->data = T->data;
Copy(T->lchild,NewT->lchild);
Copy(T->rchild,NewT->rchild);
}
}
3、计算二叉树的深度
复制代码
1
2
3
4
5
6
7
8
9
10
int Depth(BiTree T){
if(!T){return 0;}
else{
m = Depth(T->lchild);
n = Depth(T->rchild);
if(m>n){return (m+1);}
else{return (n+1);}
}
}
4、统计二叉树中结点个数
复制代码
1
2
3
4
5
6
7
8
9
int NodeCount(BiTree T){
if(!T){return 0;}
else{
m = NodeCount(T->lchild);
n = NodeCount(T->rchild);
return (m+n+1);
}
}

参考资料：《数据结构》 严蔚敏

最后

以上就是殷勤冰棍最近收集整理的关于数据结构：二叉树的遍历的全部内容，更多相关数据结构：二叉树内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(46)

相关文章

二叉树三种遍历方式的非递归实现
二叉树三种遍历方式的非递归实现
二叉树三种遍历方式递归实现分别按照二叉树先序，中序和后序打印所有的节点。
二叉树三种遍历方式递归实现分别按照二叉树先序，中序和后序打印所有的节点。
递归 非递归 遍历二叉树
递归 非递归 遍历二叉树
非递归遍历二叉树
非递归遍历二叉树
数据结构：二叉树的遍历
数据结构：二叉树的遍历
数据结构和算法-二叉树概念、三种遍历
数据结构和算法-二叉树概念、三种遍历
算法和数据结构——顺序二叉树的遍历
算法和数据结构——顺序二叉树的遍历
数据结构与算法：二叉树遍历二叉树遍历发散
数据结构与算法：二叉树遍历二叉树遍历发散

评论列表共有 0 条评论

立即
投稿
返回
顶部