树形结构：二叉树的递归非递归遍历、BST

目录

一、二叉树递归遍历

二、二叉树的非递归

三、BST

一、二叉树递归遍历

二叉树介绍：

二叉树
1.有序树
2.树中包含的节点度不超过2，只能是0、1、2

二叉树的性质
一个深度为n的二叉树结点最多为  2^n - 1    最少为n个
二叉树中，第n层最多有  2^（n-1）个
二叉树中，度为0（n0）的结点数量等于  n0 = n2 + 1

满二叉树
除了叶子结点，所有结点的度都为2的二叉树
一个深度为n的满二叉树结点最多为  2^n - 1
满二叉树中不存在度为1的结点，且叶子结点都在最底层
n个结点的满二叉树的深度为   log2（n+1）

完全二叉树
除去最后一层结点为满二叉树，且最后一层结点从左到右依次分布
n个结点的完全二叉树的深度为  [log2n] + 1
 
将一颗n个结点的 完全二叉树 从上到下，从左到右依次编号对于任意一个结点（i）有如下结论：
i > 1        父亲结点为 i/2 
 -----------------------------------
2 * i > n       结点i没有左孩子     
否则            左孩子为 2 * i
------------------------------------
2 * i + 1 > n   结点没有右孩子
否则            右孩子为 2 * i + 1
------------------------------------
下面请看详细代码

#include <iostream>
using namespace std;

struct BinaryTree
{
	int value;
	BinaryTree* pLeft;
	BinaryTree* pRight;
};


//       递归

//前序打印
void PerOrderTraversal(BinaryTree* pRoot)
{
	if (pRoot == NULL)
	{
		return;
	}
	//根
	cout << pRoot->value <<" ";
	//左
	PerOrderTraversal(pRoot->pLeft);
	//右
	PerOrderTraversal(pRoot->pRight);
}
//中序打印
void InOrderTraversal(BinaryTree* pRoot)
{
	if (pRoot == NULL)
	{
		return;
	}
	//左
	InOrderTraversal(pRoot->pLeft);
	//根
	cout << pRoot->value << " ";
	//右
	InOrderTraversal(pRoot->pRight);

}
//后序打印
void PostOrderTraversal(BinaryTree* pRoot)
{
	if (pRoot == NULL)
	{
		return;
	}
	//左
	PostOrderTraversal(pRoot->pLeft);
	//右
	PostOrderTraversal(pRoot->pRight);
	//根
	cout << pRoot->value << " ";
}
int main()
{
	//根
	BinaryTree* pRoot = new BinaryTree;
	pRoot->value = 1;
	//-------------------------------------------------------
	//根的左
	pRoot->pLeft = new BinaryTree;
	pRoot->pLeft->value = 2;
	//左的左
	pRoot->pLeft->pLeft = new BinaryTree;
	pRoot->pLeft->pLeft->value = 4;
	pRoot->pLeft->pLeft->pLeft = nullptr;
	pRoot->pLeft->pLeft->pRight = nullptr;
	//左的右
	pRoot->pLeft->pRight = new BinaryTree;
	pRoot->pLeft->pRight->value = 5;
	pRoot->pLeft->pRight->pLeft = nullptr;
	pRoot->pLeft->pRight->pRight = nullptr;
	// ------------------------------------------------------
	//根的右
	pRoot->pRight = new BinaryTree;
	pRoot->pRight->value = 3;
	//右的左
	pRoot->pRight->pLeft = nullptr;
	//右的右
	pRoot->pRight->pRight = new BinaryTree;
	pRoot->pRight->pRight->value = 6;
	pRoot->pRight->pRight->pLeft = nullptr;
	pRoot->pRight->pRight->pRight = nullptr;

	PerOrderTraversal(pRoot);
	cout << endl;
	InOrderTraversal(pRoot);
	cout << endl;
	PostOrderTraversal(pRoot);
	cout << endl;
	return 0;
}

输出： 

1 2 4 5 3 6
4 2 5 1 3 6
4 5 2 6 3 1

D:\数据结构\树形结构\x64\Debug\树形结构.exe (进程 6220)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

二、二叉树的非递归

#include <iostream>
using namespace std;
#include <stack>
#include <queue>


struct BinaryTree
{
	int value;
	BinaryTree* pLeft;
	BinaryTree* pRight;
};


//递归

//前序打印
void PerOrderTraversal(BinaryTree* pRoot)
{
	if (pRoot == NULL)
	{
		return;
	}
	//根
	cout << pRoot->value <<" ";
	//左
	PerOrderTraversal(pRoot->pLeft);
	//右
	PerOrderTraversal(pRoot->pRight);
}
//中序打印
void InOrderTraversal(BinaryTree* pRoot)
{
	if (pRoot == NULL)
	{
		return;
	}
	//左
	InOrderTraversal(pRoot->pLeft);
	//根
	cout << pRoot->value << " ";
	//右
	InOrderTraversal(pRoot->pRight);

}
//后序打印
void PostOrderTraversal(BinaryTree* pRoot)
{
	if (pRoot == NULL)
	{
		return;
	}
	//左
	PostOrderTraversal(pRoot->pLeft);
	//右
	PostOrderTraversal(pRoot->pRight);
	//根
	cout << pRoot->value << " ";
}
//-------------------------------------------------------------------------------------------------------
// 非递归
//        前序
void UnRecPerOrderTraversal(BinaryTree* pRoot)
{

	if (pRoot == NULL)
	{
        return;
	}
	stack<BinaryTree*> st;
	
	loop
	//while (1)
	//{
	//	//loop
	//	while (pRoot != NULL)
	//	{
	//		//打印根
	//		cout << pRoot->value <<" ";

	//		//入栈（容器）
	//		st.push(pRoot);

	//		//向左走
	//		pRoot = pRoot->pLeft;
	//	}
	//	if (st.empty() == true)
	//		break;
	//	//出栈
	//	pRoot = st.top();
	//	st.pop();

	//	//向右走
	//	pRoot = pRoot->pRight;

	//}
	//cout << endl;

}

//      中序
void UnRecInOrderTraversal(BinaryTree* pRoot)
{
	//if (pRoot == NULL)
	//{
	//	return;
	//}
	//stack<BinaryTree*> st;

	loop
	//while (1)
	//{
	//	//loop
	//	while (pRoot != NULL)
	//	{
	//		//入栈（容器）
	//		st.push(pRoot);

	//		//向左走
	//		pRoot = pRoot->pLeft;
	//	}
	//	if (st.empty() == true)
	//		break;
	//	//出栈
	//	pRoot = st.top();
	//	st.pop();

	//	//打印根
	//	cout << pRoot->value << " ";

	//	//向右走
	//	pRoot = pRoot->pRight;

	//}
	//cout << endl;
}
//      后序
void UnRecPostOrderTraversal(BinaryTree* pRoot)
{
	//if (pRoot == NULL)
	//{
	//	return;
	//}
	//stack<BinaryTree*> st;
	//BinaryTree* pMark = NULL;
	loop
	//while (1)
	//{
	//	//loop
	//	while (pRoot != NULL)
	//	{
	//		//入栈（容器）
	//		st.push(pRoot);

	//		//向左走
	//		pRoot = pRoot->pLeft;
	//	}
	//	if (st.empty() == true)
	//		break;
	//	//判断当前栈顶元素是否有右 或者 当前栈顶元素的右是否被标记过
	//	if (st.top()->pRight == NULL || st.top()->pRight == pMark)
	//	{
	//		pMark = st.top();
	//		st.pop();
	//		cout << pMark->value << " ";
	//	}
	//	else
	//	{
	//		pRoot = st.top();
	//		pRoot = pRoot->pRight;
	//	}
	//}
	//cout << endl;
}
//----------------------------------------------------------------------------------------------------

//      深度遍历
void LevelTraversal(BinaryTree* pRoot)
{
//	if (pRoot == NULL)
	//{
	//	return;
	//}
	//queue<BinaryTree*> que;

	//que.push(pRoot);

	//while (que.empty() != true)
	//{
	//	//出队
	//	pRoot = que.front();
	//	que.pop();
	//	//非空
	//	//{
	//		//打印
	//		//左入队 右入队
	//	//}
	//	if (pRoot != NULL)
	//	{
	//		cout << pRoot->value << " ";
	//		que.push(pRoot->pLeft);
	//		que.push(pRoot->pRight);
	//	}
	//}
	//cout << endl;
}

int main()
{
	//根
	BinaryTree* pRoot = new BinaryTree;
	pRoot->value = 1;
	//-------------------------------------------------------
	//根的左
	pRoot->pLeft = new BinaryTree;
	pRoot->pLeft->value = 2;
	//左的左
	pRoot->pLeft->pLeft = new BinaryTree;
	pRoot->pLeft->pLeft->value = 4;
	pRoot->pLeft->pLeft->pLeft = nullptr;
	pRoot->pLeft->pLeft->pRight = nullptr;
	//左的右
	pRoot->pLeft->pRight = new BinaryTree;
	pRoot->pLeft->pRight->value = 5;
	pRoot->pLeft->pRight->pLeft = nullptr;
	pRoot->pLeft->pRight->pRight = nullptr;
	// ------------------------------------------------------
	//根的右
	pRoot->pRight = new BinaryTree;
	pRoot->pRight->value = 3;
	//右的左
	pRoot->pRight->pLeft = new BinaryTree;
	pRoot->pRight->pLeft->value = 6;
	pRoot->pRight->pLeft->pLeft = nullptr;
	pRoot->pRight->pLeft->pRight = nullptr;
	//右的右
	pRoot->pRight->pRight = new BinaryTree;
	pRoot->pRight->pRight->value = 7;
	pRoot->pRight->pRight->pLeft = nullptr;
	pRoot->pRight->pRight->pRight = nullptr;

	cout << "前序" << endl;
	PerOrderTraversal(pRoot);
	cout << endl;
	UnRecPerOrderTraversal(pRoot);


	cout << "-------------------------------------------" << endl;


	cout << "中序" << endl;
	InOrderTraversal(pRoot);
	cout << endl;
	UnRecInOrderTraversal(pRoot);


	cout << "-------------------------------------------" << endl;


	cout << "后序" << endl;
	PostOrderTraversal(pRoot);
	cout << endl;
	UnRecPostOrderTraversal(pRoot);



	cout << "-------------------------------------------" << endl;


	
	cout << "深度遍历" << endl;

	LevelTraversal(pRoot);

	cout << "-------------------------------------------" << endl;
	return 0;

	system("pause");
	return 0;
}

输出： 

前序
1 2 4 5 3 6 7
-------------------------------------------
中序
4 2 5 1 6 3 7
-------------------------------------------
后序
4 5 2 6 7 3 1
-------------------------------------------
深度遍历
-------------------------------------------

D:\数据结构\树形结构\x64\Debug\树形结构.exe (进程 16244)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

三、BST

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

#include <iostream>
using namespace std;


typedef struct BST
{
	int value;
	BST* pleft;
	BST* pright;
}List;
void Addbst(BST*& rpRoot, int value)
{
	BST* ptemp = new BST;
	ptemp->value = value;
	ptemp->pleft = nullptr;
	ptemp->pright = nullptr;

	//判断是否有结点
	if (rpRoot == nullptr)
	{
		rpRoot = ptemp;
		return;
	}
	BST* pmark = rpRoot;
	//寻找添加位置
	//比较添加结点的值和标记的值
	while (pmark != nullptr)
	{
		if (value < pmark->value)           //小于  向左走
		{
			if (pmark->pleft == nullptr)
			{
				pmark->pleft = ptemp;
				return;
			}
			pmark = pmark->pleft;
		}
		else if(value > pmark->value)		//大于  向右走
		{
			if (pmark->pright == nullptr)
			{
				pmark->pright = ptemp;
				return;
			}
			pmark = pmark->pright;
		}
		else							   //等于 数据有误结束									  								
		{
			cout << "数据有误" << endl;
			delete ptemp;
			ptemp = nullptr;
			return;
		}
	}
}
void Inordertraversal(BST*& rpRoot)
{
	if (rpRoot == nullptr)
	{
		return;
	}
	Inordertraversal(rpRoot->pleft);
	cout << rpRoot->value << " ";
	Inordertraversal(rpRoot->pright);
}

BST* SearchBST(BST* pRoot, int value, BST*& rpfather)
{
	while (pRoot != nullptr)
	{
		if (pRoot->value > value)
		{
			rpfather = pRoot;
			pRoot = pRoot->pleft;
		}
		else if(pRoot->value < value)
		{
			rpfather = pRoot;
			pRoot = pRoot->pright;
		}
		else
		{
			return pRoot;
		}
	}

	rpfather = nullptr;
	return nullptr;
}

void DeleteBST(BST*& rpRoot, int value)
{
	BST* pFather = nullptr;

	//找到要删除的结点和他的父亲
	BST* pDel = SearchBST(rpRoot, value, pFather);
	if (pDel == nullptr)
	{
		cout << "没有找到要删除的结点" << endl;
		return;
	}
	//分析孩子情况
	//两个孩子
	if (pDel->pleft != nullptr && pDel->pright != nullptr)
	{
		//找左的最右 或者 右的最左   替换掉要删除的结点
		BST* pMark = pDel;
		pFather = pDel;
		pDel = pDel->pleft;
		while (pDel->pright != nullptr)
		{
			pFather = pDel;
			pDel = pDel->pright;
		}
		//替换
		pMark->value = pDel->value;
	}
			

	//一个孩子
	//没有孩子
	//判断是不是根
	if (pFather == nullptr)
	{
		rpRoot = pDel->pleft != nullptr ? pDel->pleft : pDel->pright;
	}
	//非根
	//判断删除结点是父亲的左还是右
	if (pFather->pleft == pDel)
	{
		pFather->pleft = pDel->pleft != nullptr ? pDel->pleft : pDel->pright;
	}
	else
	{
		pFather->pright = pDel->pleft != nullptr ? pDel->pleft : pDel->pright;

	}
	//删除
	delete pDel;
	pDel = nullptr;
}

void BSTtoList(BST* pRoot,List*& rpHead,List*& rpEnd)
{

	if (pRoot == nullptr)
	{
		return;
	}
	BSTtoList(pRoot->pleft, rpHead, rpEnd);
	if (rpHead == nullptr)
	{
		rpHead = pRoot;
	}
	else
	{
		rpEnd->pright = pRoot;
		pRoot->pleft = rpEnd;
	}
	rpEnd = pRoot;

	BSTtoList(pRoot->pright, rpHead, rpEnd);
}
int main()
{
	BST* pRoot = nullptr;

	Addbst(pRoot, 34);
	Addbst(pRoot, 12);
	Addbst(pRoot, 50);
	Addbst(pRoot, 40);
	Addbst(pRoot, 17);
	Addbst(pRoot, 8);

	/*Inordertraversal(pRoot);
	cout << endl;*/

	/*BST* pfather = nullptr;
	BST* ptemp = SearchBST(pRoot, 8, pfather);*/
	DeleteBST(pRoot, 12);
	Inordertraversal(pRoot);
	cout << endl;
	/*DeleteBST(pRoot, 21);
	Inordertraversal(pRoot);
	cout << endl;*/

	List* pHead = nullptr;
	List* pEnd = nullptr;

	BSTtoList(pRoot, pHead, pEnd);

	return 0;
 }

输出：

8 17 34 40 50

D:\数据结构\树形结构\x64\Debug\树形结构.exe (进程 18648)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .