您的位置: 首页  >  IT文章  >  观数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先

观数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先

分类: IT文章 • 2024-11-03 14:22:01
看数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先

二叉树的宽度是：每一层 节点数的最大值。

思路：根据层序遍历，求出 每一层的节点数，

//纠正 求 二叉树的 宽度问题，
//二叉树的宽度 为 各层次 节点数的 最大值
//算法思路，层序 遍历,

int treeWidth(Tree tree){
	if (tree != NULL)
	{
		int curWidth = 1;//当前层的 节点数
		int nextWidth = 0;//下一层的节点数
		int maxWidth = 1;//最大节点数
		LinkQueue queue;
		queueInit(&queue);
		enqueue(&queue,tree);
		while (!queueEmpty(queue))
		{
			while (curWidth != 0)
			{
				curWidth --;
				dequeue(&queue,&tree);
				if (tree->leftChild != NULL)
				{
					enqueue(&queue,tree->leftChild);
					nextWidth++;
				}
				if (tree->rightChild != NULL)
				{
					enqueue(&queue,tree->rightChild);
					nextWidth++;
				}
			}
			if(nextWidth > maxWidth){
				maxWidth = nextWidth;
			}
			curWidth = nextWidth;
			nextWidth = 0;
		}
		return maxWidth;
	}
	return 0;//空表宽度为0
}


查找任意节点的祖先：

祖先指的是：从根 到 节点 所经过的 所有节点。

//查找祖先
bool treeGetAllParent(Tree tree,ElementType data){
	if (tree != NULL)
	{
		if (tree->data == data)
		{
			return true;
		}
		if (treeGetAllParent(tree->leftChild,data) || treeGetAllParent(tree->rightChild,data))
		{
			printf("%d\t",tree->data);
			return true;
		}

	}
	return false;
}


判断是否是完全二叉树：

思路：层序遍历，在遍历中，遇到空节点 以后，如果 再遇到 一个 非空节点，就不是完全二叉树。

//判断是不是完全二叉树
//利用层序 遍历
//在层序遍历时，出现了 空子树以后，又出现了非空子树，不是完全二叉树
bool treeIsFull(Tree tree){
	bool isFindNull = false;//是不是发现空子树了
	LinkQueue queue;
	queueInit(&queue);
	enqueue(&queue,tree);
	while (!queueEmpty(queue))
	{
		dequeue(&queue,&tree);
		if (tree == NULL)
		{
			isFindNull = true;
		}
		else {
			if(isFindNull)//在 出现了空子树后，出现了 非空节点
			{
				return false;
			}
			else
			{
				//在还没发现空时，所有节点 都得 入队
				//在发现了空了，非空节点不需要入队
				//(算法优化）以前 无判断
				//enqueue(&queue,tree->leftChild);
				if (tree->leftChild != NULL || isFindNull == false)
				{
					enqueue(&queue,tree->leftChild);
				}
				if (tree->rightChild != NULL || isFindNull == false)
				{
					enqueue(&queue,tree->rightChild);
				}
			}
		}
	}
	//销毁队列
	queueDestory(&queue);
	return true;//空树 是完全二叉树
}

交互左右子树： 

//交换左右子树
void treeExchangeChild(Tree t){
	if (t != NULL)
	{
		if (t->leftChild != NULL || t->rightChild != NULL)
		{
			Tree temp = t->leftChild;
			t->leftChild = t->rightChild;
			t->rightChild = temp;
		}
		treeExchangeChild(t->leftChild);
		treeExchangeChild(t->rightChild);
	}
}

完整代码： 

// binaryTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <cstdlib>
#include "stack.h"
#include "queue.h"
#include <math.h>

typedef int ElementType;

typedef  struct TreeNode
{
	ElementType data;
	TreeNode * leftChild;
	TreeNode * rightChild;
} * Tree;

void treeInit(Tree * tree){
	*tree = NULL;
}
//其实 自己 不懂 这个 函数 初始化...
E_State treeCreate(Tree *tree){
	ElementType data;
	scanf("%d",&data);
	if (data == 0)
	{
		*tree = NULL;
	}else
	{
		*tree = (Tree)malloc(sizeof(TreeNode));
		(*tree)->data = data;
		treeCreate(&(*tree)->leftChild);
		treeCreate(&(*tree)->rightChild);
	}
	return E_State_Ok;
}


//后序遍历
void treeClear(Tree * tree){
	if (tree != NULL)
	{
		if ((*tree)->leftChild != NULL)
		{
			treeClear(&(*tree)->leftChild);
		}
		else if((*tree)->rightChild != NULL)
		{
			treeClear(&(*tree)->rightChild);
		}
		free(*tree);
		*tree = NULL;
	}
}

void treeDestory(Tree * tree){
	treeClear(tree);
}

//纠正 求 二叉树的 宽度问题，
//二叉树的宽度 为 各层次 节点数的 最大值
//算法思路，层序 遍历,

int treeWidth(Tree tree){
	if (tree != NULL)
	{
		int curWidth = 1;//当前层的 节点数
		int nextWidth = 0;//下一层的节点数
		int maxWidth = 1;//最大节点数
		LinkQueue queue;
		queueInit(&queue);
		enqueue(&queue,tree);
		while (!queueEmpty(queue))
		{
			while (curWidth != 0)
			{
				curWidth --;
				dequeue(&queue,&tree);
				if (tree->leftChild != NULL)
				{
					enqueue(&queue,tree->leftChild);
					nextWidth++;
				}
				if (tree->rightChild != NULL)
				{
					enqueue(&queue,tree->rightChild);
					nextWidth++;
				}
			}
			if(nextWidth > maxWidth){
				maxWidth = nextWidth;
			}
			curWidth = nextWidth;
			nextWidth = 0;
		}
		return maxWidth;
	}
	return 0;//空表宽度为0
}

//查找祖先
bool treeGetAllParent(Tree tree,ElementType data){
	if (tree != NULL)
	{
		if (tree->data == data)
		{
			return true;
		}
		if (treeGetAllParent(tree->leftChild,data) || treeGetAllParent(tree->rightChild,data))
		{
			printf("%d\t",tree->data);
			return true;
		}

	}
	return false;
}
//判断是不是完全二叉树
//利用层序 遍历
//在层序遍历时，出现了 空子树以后，又出现了非空子树，不是完全二叉树
bool treeIsFull(Tree tree){
	bool isFindNull = false;//是不是发现空子树了
	LinkQueue queue;
	queueInit(&queue);
	enqueue(&queue,tree);
	while (!queueEmpty(queue))
	{
		dequeue(&queue,&tree);
		if (tree == NULL)
		{
			isFindNull = true;
		}
		else {
			if(isFindNull)//在 出现了空子树后，出现了 非空节点
			{
				return false;
			}
			else
			{
				//在还没发现空时，所有节点 都得 入队
				//在发现了空了，非空节点不需要入队
				//(算法优化）以前 无判断
				//enqueue(&queue,tree->leftChild);
				if (tree->leftChild != NULL || isFindNull == false)
				{
					enqueue(&queue,tree->leftChild);
				}
				if (tree->rightChild != NULL || isFindNull == false)
				{
					enqueue(&queue,tree->rightChild);
				}
			}
		}
	}
	//销毁队列
	queueDestory(&queue);
	return true;//空树 是完全二叉树
}

//交换左右子树
void treeExchangeChild(Tree t){
	if (t != NULL)
	{
		if (t->leftChild != NULL || t->rightChild != NULL)
		{
			Tree temp = t->leftChild;
			t->leftChild = t->rightChild;
			t->rightChild = temp;
		}
		treeExchangeChild(t->leftChild);
		treeExchangeChild(t->rightChild);
	}
}

/*
//求二叉树节点的最大路径数.
//一棵二叉树中相距最远的两个节点之间的距离。
//"距离"为两节点之间边的个数
int treeMaxPath(Tree t){
}

//寻找节点child1 和 child2 的最近 共同祖先
//后序遍历 子树
Tree treeFindCommonAncestor(Tree tree,Tree child1,Tree child2){
}*/


//递归算法 先序
void preOrderTraverse(Tree tree){
	if (tree != NULL)
	{
		printf("%d\t",tree->data);
		preOrderTraverse(tree->leftChild);
		preOrderTraverse(tree->rightChild);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	Tree tree;
	printf("---------------创建树（先序,0代表子树为空）-----------------\n");
	treeCreate(&tree);
	printf("------------先序递归遍历----------------\n");
	preOrderTraverse(tree);
	int width = treeWidth(tree);
	char * isFull = treeIsFull(tree) ? "是" : "不是";
	printf("\n树的宽度是：%d,树是否是完全二叉树:%s\n",width,isFull);
	printf("-----------打印5的所有祖先-------------\n");
	treeGetAllParent(tree,5);//打印5的所有祖先。
	printf("\n");
	printf("-----------交互左右子树后-------------\n");
	treeExchangeChild(tree);
	preOrderTraverse(tree);
	printf("\n-----------创建完全二叉树-------------\n");
	Tree fullTree;
	treeCreate(&fullTree);
	isFull = treeIsFull(fullTree) ? "是" : "不是";
	printf("树是否是完全二叉树:%s\n",isFull);
	//及时释放内存是个好习惯..
	treeDestory(&fullTree);
	treeDestory(&tree);
	return 0;
}
运行截图：

观数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先

相关推荐