数据结构—树与二叉树(概念及二叉树的前序，中序，后序遍历的代码实现) 数据结构

目录

序章
树
树的定义
树的基本术语
线性结构与树结构比较
二叉树
二叉树的定义
二叉树的五种基本形态
二叉树的性质
【数据结构—树与二叉树(概念及二叉树的前序，中序，后序遍历的代码实现)】两种特殊形式的二叉树
满二叉树
完全二叉树
完全二叉树性质(接上面的性质)
二叉树的储存结构
顺序储存结构
二叉树的链式储存结构
二叉树的遍历
创建二叉树
序章先来了解一下树形结构的特点

文章图片

树树的定义定义：树是n(n>=0)个结点的有限集。
当n==0时，成为空树；
当n>0时，如果有且只有一个结点，则称为根(root)结点。否则其余结点可分为m(m>=0)个互不相交的有限集T1,T2....Tn，其中每一个集合本身又是一棵树，并称为树的子树。

文章图片

就像这棵树，1就是她的根，而2(4,5)，3，6则是她的子树。
树的基本术语
文章图片

接下来我们通过一棵树来加深一下各个术语的含义；

文章图片

从整张图里分析一下：A的结点的度为3，因为他有B，C，D所组成的子树。
由此可推B(2),C(1),D(3),E(2),F(0),G(0),H(1),I(0),J(0),k(0),L(0),M(0)。
所以树的度为3，因为树内各节点度的最大值就是3。
不难发现，分支结点就是 度!=0 的结点，叶子就是 度 == 0 的结点。
这里补充一点，
有序树：树中结点的各子树从左至右有次序。
无序树：没有次序。
森林：是m(M>=0)棵互不相交的树的集合。(树可以是森林但是森林不一定是树)
线性结构与树结构比较

线性结构	树结构
第一个数据元素(无前驱)	根节点(无双亲)
最后一个数据元素(无后继)	叶子结点(无孩子)
其他数据元素(一前驱一后继)	其他结点-中间结点(一双亲，多孩子)
一对一	多对多

二叉树二叉树的定义二叉树是n(n>=0)个结点的有限集，她或者是空集(n==0)，或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。
特点：
1.二叉树中的结点的度<=2.
2.子树有左右之分，其次序不能颠倒。
3.二叉树可以是空集。
二叉树的五种基本形态

文章图片

二叉树的性质性质1：在二叉树的第 i 层上至多有2^(i-1)个结点(i>=1).
这个性质很好想，因为二叉树最多就2个分支，所以每层是以2为底的指数型增长。
性质2：深度为 k 的二叉树至多有2^k-1个结点(k>=1)。
就是把每层的结点的加上，所以就成了

文章图片
，所以就成了等比求和，S =

文章图片
或者

文章图片

性质3：对任何一棵二叉树T，如果其叶子数为n(0)，度为2的结点为n(2)，则n(0) = n(2) + 1。
这个有些难想，我们可以简单的推理一下，度为2的结点会生成出2个边，度为1的结点(这里表示为n(1))生成的边为1，所以
总边数B = n(2)*2+n(1) = n - 1.(n为总结点数)因为根结点无双亲，所以就少她一个边，所以这里“-1”就行。
总结点数n = n(2)*2+n(1)*1+1 = n(2)+n(1)+n(0) 一棵二叉树的总结点就是由叶子结点，度为2的结点和度为1的结点所构成。
这里发现可以建立一个等式 n(2)+n(1)+n(0)-1= n(2)*2+n(1) 化简一下就是n(0) = n(2) + 1。
在讲性质4和性质5时，我们要先说一下两种特殊形式的二叉树。
两种特殊形式的二叉树满二叉树定义：一棵深度为k，且有2^k-1个结点的二叉树。
特点：
1.每一层上的结点数都是最大结点数(即每层都满).
2.叶子结点全部都在最底层.
完全二叉树定义:深度为k,且有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应.
特点:
1.叶子只可能分布在层次最大的两层上.
2.对任意结点,如果其右子树的最大层次为 i ,则其左子树的最大层次必为 i 或 i+1.

文章图片

不难发现满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树.
完全二叉树性质(接上面的性质) 性质4:具有n个结点的完全二叉树的深度为[log以2为底的n次方]+1;
[x]表示不大于x的最大整数.
这里举个例子,比如有5个结点的完全二叉树,他就在log以2为底的4~在log以2为底的8之间,所以就是2+1 = 3层.
性质5:

文章图片

这里可以画一个完全二叉树来方便理解.

文章图片

二叉树的储存结构

文章图片

顺序储存结构因为完全二叉树的那些性质,所以可以用一个数组来表示,取结点的时候可以用下标,但是有一点很麻烦,就是不能随时删除和添加.

//二叉树顺序储存表示 #define MAXTISE 100 //（按满二叉树的结点层次） int SqBiTree[MAXTISE];

二叉树的链式储存结构

文章图片

不过一般都用的是二叉链表,下面的二叉树的遍历就以二叉链表为准.
代码实现:

//二叉链表储存结构 typedef struct BiNode{ int data; struct BiNode *lchild,*rchild; //左右孩子指针 }BiNode,*BiTree; //三叉链表储存结构 typedef struct TriTNode{ int data; struct TriTNode *lchild,*parent,*rchild; //左右孩子指针 }TriTNode,*TriTree;

二叉树的遍历 DLR-----先根遍历根->左子树->右子树

文章图片

代码实现:

//先序遍历 int PreOrderTraverse(BiTree T){ if(T==NULL) return -1; else{ cout << T->data; //访问根节点 PreOrderTraverse(T->lchild); //递归遍历左子树 PreOrderTraverse(T->rchild); //递归遍历右子树 } }

LDR------中序遍历左子树->根->右子树

文章图片

代码实现(递归版):

//中序遍历 int InOrderTraverse(BiTree T){ if(T==NULL) return -1; //空二叉树 else{ InOrderTraverse(T->lchild); //遍历左二叉树 cout << T->data; //访问根节点 InOrderTraverse(T->rchild); //遍历右二叉树 } }

代码实现(非递归版):
非递归实现的话,可以用一个栈来当辅助空间,把左孩子结点都存进去,知道左孩子结点为NULL,输出最后一个不为NULL的左孩子,返回最后一个不为NULL的左孩子结点的双亲,检查有没有右孩子,如果有在检查有没有左孩子.....如果该结点没有左右孩子,则输出该结点,也就是该结点双亲结点的左孩子.

//中序遍历(非递归) int InOrderTraverse_(BiTree T){ BiTree P,q,s[109]; //s为模拟栈 //stack s; P = T; int top = 0; for(int i=0; i<109; i++){//初始化栈 s[i] = NULL; } while(P!=NULL||top){//树不为NULL，栈不为空时 while(P!=NULL){//树不为NULL,入栈，并检查左孩子是否为NULL //cout << P->data << " "; s[top++] = P; P = P->lchild; }if(top>0){//栈不为空时 q = s[top-1]; //q为此结点的双亲 cout << q->data; top--; //出栈 P = q->rchild; //检查有没有右孩子 } } }

LRD----后序遍历左子树->右子树->根

文章图片

代码实现:

//后序遍历 int PostOrderTraverse(BiTree T){ if(T==NULL) return -1; else{ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout << T->data; } }

层次遍历------输出每一层上的结点.
这里需要用到循环队列,我们这里手写一下循环队列

//顺序循环队列(用来进行层次遍历) typedef struct{ BiTree *data; //存放队中元素 int front,rear; //队头和队尾指针 }SqQueue; //顺序循环队列类型//队列初始化 void InitQueue(SqQueue &Q){ Q.data = https://www.it610.com/article/new BiTree[109]; Q.front = Q.rear = 0; }//入队列 void enQueue(SqQueue &Q,BiTree &T){ Q.data[Q.rear] = T; Q.rear = (Q.rear+1)%109; } //出队列 void deQueue(SqQueue &Q,BiTree &T){ T = Q.data[Q.front]; Q.front = (Q.front+1)%109; } //判断队列是否为空 int QueueLength(SqQueue &Q){ return ((Q.rear-Q.front+109)%109); }

首先根结点入队,然后出队,如果她有左孩子或者右孩子,那这个孩子就是她孩子的双亲,也是该子树的根. 之后重复之前的操作.
层次遍历的代码实现:

//二叉树层次遍历 void LevelOrder(BiTree b){ SqQueue q; BiTree T; T = b; InitQueue(q); //初始化队列 enQueue(q,T); //根入队列 while(QueueLength(q)!=0){ deQueue(q,T); //出队列 cout << T->data <<" "; if(T->lchild!=NULL) enQueue(q,T->lchild); //判断是否有左孩子 if(T->rchild!=NULL) enQueue(q,T->rchild); //判断是否有右孩子 } }

创建二叉树二叉树的创建是以先序遍历的形式录入,这里以数字为例;
-1表示为NULL

文章图片

那来看看这棵二叉树是怎么录入的:
0 1 2 3 -1 -1 4 5 -1 -1 6 -1 -1 -1(注意一下,空出第一个位置)
代码实现:

//创建二叉树 int ch; void CreatBiTree(BiTree &T){ cin >> ch; if(ch==-1) T = NULL; else{ T = new BiNode; T->data = https://www.it610.com/article/ch; //生成根节点 CreatBiTree(T->lchild); //构造左子树 CreatBiTree(T->rchild); //构造右子树 } }

创建完成后,看一下这棵二叉树的遍历后的结果:

文章图片

整体代码:

#include #include #include using namespace std; //二叉树顺序储存表示 #define MAXTISE 100 //（按满二叉树的结点层次） int SqBiTree[MAXTISE]; //二叉链表储存结构 typedef struct BiNode{ int data; struct BiNode *lchild,*rchild; //左右孩子指针 }BiNode,*BiTree; //三叉链表储存结构 typedef struct TriTNode{ int data; struct TriTNode *lchild,*parent,*rchild; //左右孩子指针 }TriTNode,*TriTree; //顺序循环队列(用来进行层次遍历) typedef struct{ BiTree *data; //存放队中元素 int front,rear; //队头和队尾指针 }SqQueue; //顺序循环队列类型//队列初始化 void InitQueue(SqQueue &Q){ Q.data = https://www.it610.com/article/new BiTree[109]; Q.front = Q.rear = 0; }//入队列 void enQueue(SqQueue &Q,BiTree &T){ Q.data[Q.rear] = T; Q.rear = (Q.rear+1)%109; } //出队列 void deQueue(SqQueue &Q,BiTree &T){ T = Q.data[Q.front]; Q.front = (Q.front+1)%109; } //判断队列是否为空 int QueueLength(SqQueue &Q){ return ((Q.rear-Q.front+109)%109); }//先序遍历 int PreOrderTraverse(BiTree T){ if(T==NULL) return -1; else{ cout << T->data; //访问根节点 PreOrderTraverse(T->lchild); //递归遍历左子树 PreOrderTraverse(T->rchild); //递归遍历右子树 } }//中序遍历 int InOrderTraverse(BiTree T){ if(T==NULL) return -1; //空二叉树 else{ InOrderTraverse(T->lchild); //遍历左二叉树 cout << T->data; //访问根节点 InOrderTraverse(T->rchild); //遍历右二叉树 } }//后序遍历 int PostOrderTraverse(BiTree T){ if(T==NULL) return -1; else{ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout << T->data; } }//中序遍历(非递归) int InOrderTraverse_(BiTree T){ BiTree P,q,s[109]; //s为模拟栈 //stack s; P = T; int top = 0; for(int i=0; i<109; i++){//初始化栈 s[i] = NULL; } while(P!=NULL||top){//树不为NULL，栈不为空时 while(P!=NULL){//树不为NULL,入栈，并检查左孩子是否为NULL //cout << P->data << " "; s[top++] = P; P = P->lchild; }if(top>0){//栈不为空时 q = s[top-1]; //q为此结点的双亲 cout << q->data; top--; //出栈 P = q->rchild; //检查有没有右孩子 } } }//二叉树层次遍历 void LevelOrder(BiTree b){ SqQueue q; BiTree T; T = b; InitQueue(q); //初始化队列 enQueue(q,T); //根入队列 while(QueueLength(q)!=0){ deQueue(q,T); //出队列 cout << T->data; if(T->lchild!=NULL) enQueue(q,T->lchild); //判断是否有左孩子 if(T->rchild!=NULL) enQueue(q,T->rchild); //判断是否有右孩子 } }//创建二叉树 int ch; void CreatBiTree(BiTree &T){ cin >> ch; if(ch==-1) T = NULL; else{ T = new BiNode; T->data = https://www.it610.com/article/ch; //生成根节点 CreatBiTree(T->lchild); //构造左子树 CreatBiTree(T->rchild); //构造右子树 } }int main() { BiTree T; int n; while(cin >> n){ CreatBiTree(T); cout << "前序遍历" << endl; PreOrderTraverse(T); cout << endl; cout << "中序遍历" << endl; InOrderTraverse(T); cout << endl; cout << "后序遍历"<< endl; PostOrderTraverse(T); cout << endl; cout << "中序遍历非递归" << endl; InOrderTraverse_(T); cout << endl; cout << "层次遍历" << endl; LevelOrder(T); cout << endl; } return 0; }