vlambda博客
学习文章列表

数据结构-二叉树遍历算法的应用


概要

主要介绍二叉树相关的代码实现,二叉树遍历算法的具体应用,理解其相关代码的具体实现的方法及原理


先序遍历建立二叉链表

void CreateBitree(BiTNode *&T) {
char ch;
scanf (“%c”, &ch);
if (ch==‘#’) T=NULL;
else {
T=(BiTree)malloc(sizeof(BiTNode));
T->data=ch;
CreateBitree(T->lchild);
CreateBitree(T-> rchild);
}
}

首先输入当前根结点的数据,如果是#,则将当前根结点置为NULL,否则,申请一个新结点,存入当前根结点的数据,分别用当前根结点的左指针和右指针进行递归调用,创建左、右子树。


输出二叉树中的叶子结点

void  DispLeaf(BiTree  T)  { 	//先序遍历二叉树
if(T!=NULL) {
if(T->lchild==NULL && T->rchild==NULL)
printf (“%d”,T->data); //访问叶子结点
DispLeaf (T->lchild); //先序遍历左子树
DispLeaf (T->rchild); //先序遍历右子树
}
}

当二叉树为空时,叶子为0。当二叉树只有一个根结点时,根结点就是叶子结点,输出叶子结点。在其他情况下,输出左子树与右子树中的叶子结点。


输出二叉树中的叶子结点个数

int CountLeaf(BiTNode *T){//返回所有叶子节点个数
int m,n;
if(T==NULL) return 0;
if(T->lchild==NULL && T->rchild==NULL) return 1;
else {
m=CountLeaf(T->lchild);
n=CountLeaf(T->rchild);
return (m+n);
}
}

当二叉树为空时,叶子结点个数为0。当二叉树只有一个根结点时,根结点就是叶子结点,叶子结点个数为1。其他时候,计算左子树和右子树叶子结点的和。


计算二叉树的高度

int BiTreeDepth(BiTNode *T){//求高度
int m,n;
if(T==NULL) return 0;
else {
m=BiTreeDepth(T->lchild);
n=BiTreeDepth(T->rchild);
if(m>n) return m+1;
else return n+1;
}
}

二叉树的高度为树中结点的最大层次。如果是空树,则高度为0;否则,计算左子树高度,记为m;计算右子树高度,记为n。二叉树的高度为m与n的较大者+1.


频讲解