数据结构|二叉树

新建结构体

#include <stdio.h>

struct BinaryTreeNode
{
	int m_nValue;
	BinaryTreeNode*m_pLeft;
	BinaryTreeNode*m_pRight;
};

求二叉树的结点数

采用递归分别遍历左右子树最后加上根节点。

int GetNodeNum(BinaryTreeNode * pRoot)
{
	if (pRoot == NULL) {
		return 0;
	}else {
		return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
	}
}

二叉树的深度

int GetDepth(BinarytreeNode * pRoot)
{
	if (pRoot == Null) {
		return 0;
	}else {
		int a = GetDepth(pRoot->m_pleft);
		int b = GetDepth(pRoot->m_pright);
		return a > b ? (a+1) : (b+1);
	}
}

前序遍历

void Preorder1(BinaryTreeNode * pRoot)
{
	if (pRoot == NULL)
		return;
	printf("%c",pRoot->data);
	Preorder1(pRoot->m_pleft);
	Preorder1(pRoot->m_plight);
}

第k层结点个数

int GetNode(BinaryTreeNode * pRoot, int k)
{
	if(pRoot == NULL || k<1)
		return 0;
	if(k == 1)
		return 1;
	int numl = GetNode(pRoot->m_pLeft, k-1);
	int numr = GetNode(pRoot->m_pRight, k-1);
}