资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

【剑指Offer|C++】面试题8:寻找二叉树的下一个节点|上一个节点-创新互联

题目:给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

创新互联长期为超过千家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为资源企业提供专业的成都网站设计、成都网站建设资源网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。

题目算是比较新颖的了
题解:

//结构体定义
struct BinaryTreeNode
{int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode* parent;
}

//找下一个节点
BinaryTreeNode* GetNext(BinaryTreeNode* node)
{//特殊处理
	if(node == nullptr)
		return nullptr;
	
	BinaryTreeNode* next = nullptr;//定义要返回的结果指针
	if(node->right != nullptr)//有右子树:找到右子树的最左节点
	{BinaryTreeNode* pRight = node->right;
		while(pRight ->left != nullptr)
		{	pRight = pRight->left;
		}
		next = pRight;
	}
	else if(node->parent != nullptr)//非根节点
	{BinaryTreeNode* current = node;
		BinaryTreeNode* pParent = node->parent;
		while(pParent != nullptr && current == pPrent->right)//没有右子树且他还是父节点的右子节点:向上遍历直到找到一个节点是父节点的左子节点,该父节点就是要找的这个节点
		{	current = pParent;
			pParent= pParent->parent;
		}
		next = pParent;//没有右子树且是父节点的左子节点:该节点的父节点就是要找的节点
	}
}

拓展:寻求上一个节点

跟上述思路相反:
如果有左子树,即为左子树的最右子节点。
如果无左子树,如果本身为父节点的的右子节点,即为父节点
为父节点的左子节点,即为祖父节点

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻名称:【剑指Offer|C++】面试题8:寻找二叉树的下一个节点|上一个节点-创新互联
文章起源:http://cdkjz.cn/article/dcojgo.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220