使用C语言创建二进制排序树

在实际应用中c语言二叉排序树，许多情况下在数据结构中涉及树木. 作为最简单的树，二叉树有许多重要用途. 二叉树被细分为许多类型. 这里我们只讨论二进制排序树. 这种树的一个好特征是，当以中间顺序遍历树时，您将获得一个以升序排列的数组. 下面使用一维数组创建二进制排序树.

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
typedef struct Tree
{
	int Data;
	struct Tree *LeftTree;//左子树
	struct Tree *RightTree;//右子树
}TreeNode, *TreeNodeP;
void InsertNode(TreeNodeP &TreeRoot, int Data)
{
	//新建一个节点
	TreeNodeP NodeP;
	NodeP = (TreeNodeP)malloc(sizeof(TreeNode));
	NodeP->Data = Data;
	NodeP->LeftTree = NodeP->RightTree = NULL;
	//如果树根还没创建，那就把当前新建的节点赋给根吧
	if (TreeRoot == NULL)
	{
		TreeRoot = NodeP;
	}
	//新插入的节点数值比根的小或等，走根的左边
	else if (Data <= TreeRoot->Data)
	{
		//左子树递归结束处
		if (TreeRoot->LeftTree == NULL)
			TreeRoot->LeftTree = NodeP;
		//左递归
		else
			InsertNode(TreeRoot->LeftTree, Data);
	}
	//新插入的节点数值比根的大，走根的右边
	else if (Data > TreeRoot->Data)
	{
		//右子树递归结束处
		if (TreeRoot->RightTree == NULL)
			TreeRoot->RightTree = NodeP;
		//右递归
		else
			InsertNode(TreeRoot->RightTree, Data);
	}
}
void TraveseTreeNode(TreeNodeP TreeRoot, int Mode)
{
	if (TreeRoot)
	{
		//先序遍历
		if (Mode == 1)
		{
			printf("NodeData=%d\n", TreeRoot->Data);
			TraveseTreeNode(TreeRoot->LeftTree, Mode);
			TraveseTreeNode(TreeRoot->RightTree, Mode);
		}
		//中序遍历
		else if (Mode == 2)
		{
			TraveseTreeNode(TreeRoot->LeftTree, Mode);
			printf("NodeData=%d\n", TreeRoot->Data);
			TraveseTreeNode(TreeRoot->RightTree, Mode);
		}
		//后序遍历
		else if (Mode == 3)
		{
			TraveseTreeNode(TreeRoot->LeftTree, Mode);
			TraveseTreeNode(TreeRoot->RightTree, Mode);
			printf("NodeData=%d\n", TreeRoot->Data);
		}
	}
}
int main()
{
	TreeNodeP Tree = NULL;
	int A[11] = { 1, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 };
	for (int i = 0; i < 11; i++)
	{
		InsertNode(Tree, A[i]);
	}
	TraveseTreeNode(Tree, 2);
	
	return 0;
}

运行程序，您将得到: 1 2 3 4 6 7 9 13 17 1820. 但是，二进制排序树的一个坏方面是每个节点上左右树的深度可能相对不同. . 例如，有一个1 2 3 4 6 7 9 13 17 18 20的数组c语言二叉排序树，它的树是1→2→3→4→6→→9→13→17→18→20

这棵树一无所有. 也就是说，节点上左右子树的深度不平衡，这个问题将通过平衡二叉树来解决. 我有时间以后再写.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-270533-1.html