关于二叉树遍历与计算二叉树高度和输出叶节点

文章目录

一、二叉链表

二、二叉树的遍历方法

三、二叉树遍历的性质（利用此性质来判断二叉树是否确定）

四、计算二叉树的高度

五、输出叶节点

一、二叉链表

顺序链表适用性不强，直接链表
二叉链表：一个数据域和两个指针域

二叉链表的结构：

typedef char TElemType;

typedef struct BiTNode
{
   
	TElemType data;//结点数据
	struct BiTNode* lchild, * rchild;  //左右孩子指针
}BiTNode,*BiTree;

#include<stdio.h>
#include<stdlib.h>
typedef char TElemType;
typedef struct BiTNode
{
   
	TElemType data;
	struct BiTNode* lchild, * rchild;  //左右孩子指针
}BiTNode,*BiTree;
void CreatBiTree(BiTree *T);
void Preorder(BiTree T);
void Inorder(BiTree T);
void Postorder(BiTree T);
void LevelorderTraversal(BiTree BT );
int main()
{
   
	BiTree T=(struct BiTNode*)malloc(sizeof(struct BiTNode));
	CreatBiTree(&T);
	Preorder(T);
	puts(" ");
	Inorder(T);
	puts(" ");
	Postorder(T);
	puts(" ");
	LevelorderTraversal(T);
}
//按前序输入
void CreatBiTree(BiTree *T) //二级指针
{
   
	TElemType ch;
	scanf("%c",&ch);
	if (ch == '#')
	{
   
		*T = NULL;
	}
	else
	{
   
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
		{
   
			return;
		}
		(*T)->data = ch; //生成根结点
		CreatBiTree(&(*T)->lchild);//构造左子树
		CreatBiTree(&(*T)->rchild);//构造右子树
	}
}
void Preorder(BiTree T)
{
   
	if (T == NULL)
	{
   
		return;
	}

	printf("%c",T->data);
	Preorder(T->lchild);
	Preorder(T->rchild);
}
void Inorder(BiTree T)
{
   
	if (T == NULL)
	{
   
		return;
	}

	Inorder(T->lchild);
	printf("%c",T->data);
	Inorder(T->rchild);
}
void Postorder(BiTree T)
{
   
	if (T == NULL)
	{
   
		return;
	}

	Postorder(T->lchild);
	Postorder(T->rchild);
	printf("%c", T->data);
}
void LevelorderTraversal( BiTree BT )
{
   
	BiTree p;
	BiTree q[1004];
	int head=0;int tail=0;
	if(BT)
	{
   
		q[tail++]=BT;
	while(head!=tail)
	{
   
		p=q[head++];
		printf("%c",p->data);
		if(p->lchild)
		{
   
			q[tail++]=p->lchild;
		}
		if(p->rchild)
		{
   
			q[tail++]=p->rchild;
		}
	}
	}
}

二、二叉树的遍历方法:

采用递归的思想

一、前序遍历（先序遍历）

• 若二叉树为空，则空操作返回，
• 否则： 根结点->左子树->右子树

void Preorder(BiTree T)
{
   
	if (T)
	{
   
	printf("%c",T->data);
	Preorder(T->lchild);
	Preorder(T->rchild);
	}
}

二、中序遍历

• 若二叉树为空，则空操作返回，
• 否则：左子树->根结点->右子树

void Inorder(BiTree T)
{
   
	if (T )
	{
   
	Inorder(T->lchild);
	printf("%c",T->data);
	Inorder(T->rchild)
	};
}

三、后序遍历

• 若二叉树为空，则空操作返回
• 否则：左子树->右子树->根结点

void Postorder(BiTree T)
{
   
	if (T )
	{
   
	Postorder(T->lchild);
	Postorder(T->rchild);
	printf("%c", T->data);
	}
}

四、层序遍历

• 若二叉树为空，则空操作返回
• 否则：从上而下逐层遍历，在一层中，从左到右对结点逐个访问

void LevelorderTraversal( BinTree BT )
{
   
	BinTree p;
	BinTree q[1004];
	int head=0;int tail=0;
	if(BT)
	{
   
		q[tail++]=BT;
	while(head!=tail)
	{
   
		p=q[head++];
		printf(" %c",p->Data);
		if(p->Left)
		{
   
			q[tail++]=p->Left;
		}
		if(p->Right)
		{
   
			q[tail++]=p->Right;
		}
	}
	}
}

三、二叉树遍历的性质（利用此性质来判断二叉树是否确定）：

• 已知前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
• 已知后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
• 已知前序和后序遍历，是不能确定一颗二叉树的

二叉树的叶结点遍历的相对位置不变

四、计算二叉树的高度

int GetHeight( BinTree BT )
{
   
	if(!BT)
	{
   
		return 0;
	}
	int depth=0;
	int leftDepth=GetHeight(BT->Left );
	int rightDepth=GetHeight(BT->Right);
	depth = leftDepth>rightDepth?leftDepth:rightDepth;
	return (depth+1);//记得+1.因为有根节点一层
}

五、输出叶节点

void PreorderTraversal( BinTree BT )
{
   
	if(BT)
	{
   
	if(!BT->Left&&!BT->Right)//判断是否是叶子 
	printf(" %c",BT->Data);
	PreorderTraversal( BT->Left );
	PreorderTraversal( BT->Right );
	}
	
}