淘先锋技术网

首页 1 2 3 4 5 6 7

**

以二叉链表作为二叉树的存储结构,编写以下程序代码。

**
在这里插入图片描述

1、先序创建如图所示的二叉树,输出其前序、中序、后序遍历结果。
2、参考算法5.6,统计二叉树中结点的个数。ABC##DE#G##F###
3、统计二叉树中叶子结点的个数。

**

程序代码:

**

#include<iostream>
using namespace std;

typedef char TElemType;
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
} BiTNode, *BiTree;


void CreateBiTree(BiTree &T) { //先序遍历的顺序建立二叉链表
	char ch;
	cin>>ch;
	if(ch=='#')
		T=NULL;
	else {
		T=new BiTNode;
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

void InOrderTraverse(BiTree T) { //中序遍历二叉树T的递归算法
	if(T) {
		InOrderTraverse(T->lchild); //递归遍历左子树
		cout<<T->data; //访问根结点
		InOrderTraverse(T->rchild); //递归遍历右子树
	}
}

void PreOrderTraverse(BiTree T) { //前序遍历二叉树T的递归算法
	if(T) {
		cout<<T->data; //访问根结点
		PreOrderTraverse(T->lchild); //递归遍历左子树
		PreOrderTraverse(T->rchild); //递归遍历右子树
	}
}

void PostOrderTraverse(BiTree T) { //后序遍历二叉树T的递归算法
	if(T) {
		PostOrderTraverse(T->lchild); //递归遍历左子树
		PostOrderTraverse(T->rchild); //递归遍历右子树
		cout<<T->data; //访问根结点
	}
}

void Copy(BiTree T, BiTree &NewT) { //复制一棵和T完全相同的二叉树
	if(T==NULL) {
		NewT = NULL;
		return;
	} else {
		NewT = new BiTNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
}

int Depth(BiTree T) { //计算二叉树T的深度
	int m,n;
	if(T==NULL)
		return 0;
	else {
		m = Depth(T->lchild);
		n  = Depth(T->rchild);
		if(m>n) return (m+1);
		else return(n+1);
	}
}

int NodeCount(BiTree T) { //统计二叉树中结点个数
	if(T == NULL )
		return 0;
	else
		return NodeCount(T->lchild)+NodeCount(T->rchild)+1; 
	}

int Node2Count(BiTree T) { //统计度为2的结点个数

	if (T==NULL)
		return 0;
	else if((T->lchild!=NULL)&&(T->rchild!=NULL)) {
		return 1+Node2Count(T->lchild)+Node2Count(T->rchild);
	} else
		return Node2Count(T->lchild)+Node2Count(T->rchild);
}
int Node1Count(BiTree T) { //统计度为1的结点个数
	if (T==NULL)
		return 0;
	else
		return NodeCount(T)-2*Node2Count(T)-1;

}

int Node0Count(BiTree T) { //统计叶子结点个数
	if (T==NULL)
		return 0;
	else
		return Node2Count(T)+1;
}

int main() {
	BiTree T;
	cout<<"请按二叉树的先序顺序输入数据元素,如果结点为空用字符'#'表示"<<endl;
	CreateBiTree(T);
	cout<<"创建二叉树按先序遍历结果为;";
	PreOrderTraverse(T);
	cout<<endl;
	cout<<"创建二叉树按中序遍历结果为;";
	InOrderTraverse(T);
	cout<<endl;
	cout<<"创建二叉树按后序遍历结果为;";
	PostOrderTraverse(T);
	cout<<endl;
	cout<<"二叉树的深度为:"<<Depth(T)<<endl;
	cout<<"二叉树中数据元素的个数为:"<<NodeCount(T)<<endl;
	cout<<"二叉树的度为2结点个数为:"<<Node2Count(T)<<endl;
	cout<<"二叉树的度为1结点个数为:"<<Node1Count(T)<<endl;
	cout<<"二叉树的度为0结点个数为:"<<Node0Count(T)<<endl;
	BiTree NewT;
	Copy(T, NewT);
	cout<<"中序遍历复制得到的NewT:";
	InOrderTraverse(NewT);
	return 0;
}

运行截图:

在这里插入图片描述

总结:

1,二叉树与树一样具有递归性质,主要区别在于:
(1)二叉树每个结点至多只有两棵子树。
(2)二叉树的子树有左右之分,其次序不能任意颠倒。
2,满二叉树:一棵深度为k 且有2k -1个结点的二叉树。(特点:每层都“充满”了结点)
3,完全二叉树:深度为k 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。
4,二叉树性质:
(1)在二叉树的第i层上至多有2i-1个结点。
(2)深度为k的二叉树至多有2k-1个结点。
(3)对于任何一棵二叉树,若度为2的结点数有n2个,则叶子数n0必定为n2+1 (即n0=n2+1)
(4)具有n个结点的完全二叉树的深度必为 log2n +1。
(5) 如果对一棵有n个结点的完全二叉树(深度为log2n +1)的结点按层序编号(从第1层到第log2n + 1层,每层从左到右),则对任一结点 ( ),有如果 ,则结点 是二叉树的根,无双亲;如果 则其双亲结点是 。如果 ,则结点 无左孩子(结点 为叶子结点);否则,其左孩子是结点 。如果 ,则结点 无右孩子;否则,其右孩子是结点2i+1。
5,若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种,不能唯一确定一棵二叉树。