数据结构(C)核心知识点+易错点:二叉树(二叉树的先序,中序,后续遍历的递归和非递归算法,层序遍历算法)
一,二叉树
1.二叉树的性质
性质1:在二叉树的第i层上至多有2^i-1个结点(i>=1)。
性质2:深度为k的二叉树至多有2^k-1个结点(k>=1).
性质3:对任一棵二叉树,若其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
性质4:具有n个结点的完全二叉树的深度为log2n(下取整后) +1。
注意
性质3由性质树的节点数比数的边数多一(因为除了根节点,每个节点头上都有一条边连着),树的度数=每个节点度数(分支数)和=树的边数。即n0+n1+n2=n1+2n2+1
其实也可这样理解:n个叶子节点看做选手参加比赛,度为2的节点表两两进行PK,每次pK都会淘汰一名选手,最后只留下一个冠军即根节点,即参赛选手比淘汰选手多一。
这里要重点区分一下离散数学中树的度和数据结构中树的度,实际上后者指的是离散数学上的根树,所以每个节点的度=该节点分支数而不是依附于该节点的边数
2,满二叉树的性质
满二叉树是同高度的树中,节点数最多的二叉树
3,完全二叉树
性质1: 若对一棵有n个结点的完全二叉树结点按层序编号(从第1层到第log2n +1层,每层从左到右),对任一结点i(1<=i<=n),有:
(1)若i=1,i无双亲,是二叉树的根;若i>1,其双亲是i/2
(2)若2i>n,i为叶子结点,无左孩子;否则,其左孩子是2i。
(3)如果2i+1>n,则i无右孩子;否则,其右孩子是2i+1。
性质2:完全二叉树中只存在没有左右孩子的或没有右孩子的节点,不存在没有左孩子的节点
性质3:度为1的节点个数最多为1,可以为0。
性质4:如果完全二叉树缺孩子,那么只能在树的最后一层的最右边。
性质5:完全二叉树的层序遍历的序列是连续的,即所有为空的节点都分布在序列最后,前面非空的节点中间必定不会出现空指针,这也是判断完全二叉树的算法思想。
二, 二叉树的存储结构
1、顺序存储结构
特点:用一组地址连续的存储单元依次自上而下、自左至右 (即存层序序列) 存储完全二叉树的结点。仅适用于完全二叉树(在排序和查找中经常用到)。因为对非完全二叉树可能对存储空间造成极大的浪费,比如单支树。
2.链式存储(常用二叉链表)
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
三,二叉树的递归遍历
0.建立二叉树**(先序,输入时要把空节点也输入进去)**
#include"queue.h"
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define TURE 1
#define FALSE -1
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
typedef char TElemType;
Status CreateBiTree(BiTree &T)
{
char ch;
ch=getchar();
if(ch==' ') T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit OVERFLOW;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status PrintTElem(TElemType e)
{
putchar(e);
return OK;
}
遍历的要领就是抓准递归结束的条件,和访问该节点的步骤在递归逻辑中的位置,直到什么时候返回,知道返回后下一步是什么
1.先序遍历
Status PreTraverse(BiTree T,Status (* Visit)(TElemType e))
{
if(T)
{
if((*Visit)(T->data))
if(PreTraverse(T->lchild,Visit))
if(PreTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else return OK;
}
2.中序遍历
Status MidTraverse(BiTree T,Status (* Visit)(TElemType e))
{
if(T)
{
if(MidTraverse(T->lchild,Visit))
if((*Visit)(T->data))
if(MidTraverse(T->rchild,Visit))
return OK;
return ERROR;//若访问不到结点值,出错(基本上不会出现这一步,如果出现将一路返回error)
}
else return OK;
}
3.后序遍历
Status LastTraverse(BiTree T,Status (* Visit)(TElemType e))
{
if(T)
{
if(LastTraverse(T->lchild,Visit))
if(LastTraverse(T->rchild,Visit))
if((*Visit)(T->data))
return OK;
return ERROR;
}
else return OK;
}
四,二叉树的非递归遍历
1.先序非递归
思想:①根不空先将根进栈,然后依次访问其左孩子并将左孩子进栈直到左孩子为空②将空孩子出栈③将最后一个访问的左孩子(栈顶)元素出栈,并将其右孩子入栈作为根④重复上面三步,直到栈空
int NPreTraverse3(BiTree &T,int(*visit)(char e))//前序遍历非递归
{
SqStack S;
InitStack(S);
BiTree p = T;
Push(S, p);
while (!StackEmpty(S))
{
while (GetTop(S, p) && p)
{
visit(p->data);
Push(S, p->lchild);
}
Pop(S, p);
if (!StackEmpty(S))
{
Pop(S, p);
Push(S, p->rchild);
}
}
return 0;
}
2,中序非递归
思想:①根不空根入栈,然后左孩子依次进栈直到空左孩子进栈②空指针出栈③最后一个左孩子(栈顶元素)出栈并访问,然后将其右孩子入栈作为根④重复前面三步
int NMidTraverse(BiTree &T,int(*visit)(char e))
{ InitStack(S); Push(S,T);//根指针入栈
while(!StackEmpty(S))//在栈不空的情况下
{ while(GetTop(S,p)&&p)
Push(S,p->lchild);//向左走到头
Pop(S,p);//空指针退栈
if(!StackEmpty(S))
{ Pop(S,p);//元素出栈
if(!visit(p->data)) return ERROR;
Push(S,p->rchild); //右子树入栈 }
}
return OK;
} //NInOrderTraverse
3.后序非递归
思想:p指向当前的节点,cur指向前一个节点
①根节点入栈,如果栈不为空,则判断栈顶元素节点的左右节点是否为空,同时判断前一个节点是否是当前节点的左孩子或者右孩;②如果①为真,则输出当前节点且栈顶元素出栈,同时令cur等于当前节点;③如果①为假,则当前节点的孩子节点入栈④当栈为空时,退出循环;
int NLastOrderTraverse2(BiTree &T,int(*visit)(char e))//后序非递归遍历
{
SqStack S;
InitStack(S);
BiTree p = T, cur = NULL;
Push(S, p);
while (!StackEmpty(S))//栈不为空
{
GetTop(S, p);
if ((p->lchild == NULL && p->rchild == NULL) || (cur == p->lchild || cur == p->rchild))//
{
visit(p->data);
Pop(S, p);
cur = p;
}
else {
if (p->rchild != NULL)
Push(S, p->rchild);
if (p->lchild != NULL)
Push(S, p->lchild);
}
}
return 0;
}
五.二叉树的层序遍历
void SeqTraverse(BiTree T)
{
SqQueue Q ;
InitQueue(Q);
EnQueue(Q, T);
BiTree root;
while (!QueueEmpty(Q))
{
DeQueue(Q,root);
putchar(root->data);
if (root->lchild)
EnQueue(Q, root->lchild);
if(root->rchild)
EnQueue(Q, root->rchild);
}
}