使用C++实现简单二叉树

本文主要是介绍使用C++实现简单二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、引出二叉树

二叉树是一种比较特殊的树形结构，每个节点最多含有两颗子树，而且子树必须有左右之分；二叉树也是程序应用得比较多的一种结构，通过孩子与双亲反应两个物体之间的某些特殊关系。

2、二叉树基本性质

(1) 在非空二叉树中，第i层的结点总数不超过

, i>=1；

(2) 深度为h的二叉树最多有

个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；

如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i [4 ]

3、二叉树的储存结构代码（链表）

二叉树可以采用顺序储存和链式储存两种方法，如下代码采用的事二叉树的链式储存结构。

typedef  int  DATA;
struct  BinaryTreeNode
{DATA   value;struct  BinaryTreeNode  *left;struct  BinaryTreeNode  *right;
};

4、关于二叉树的遍历

（1）先序遍历：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。

（2）中序遍历：如果二叉树为空，进行空操作；否则，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。

（3）后序遍历：如果二叉树为空，进行空操作；否则，先后根遍历左子树，然后后根遍历右子树，最后访问根结点。

5、二叉树的实现

typedef int DATA; //定义数据类型 struct BinaryTreeNode
{
DATA value;
struct BinaryTreeNode *left,*right;
};
class Tree
{
public:Tree()//初始化参数 {root = NULL;}void create_Tree(int);//新建二叉树 void Preorder(BinaryTreeNode *);//先序遍历 void inorder(BinaryTreeNode *);//中序遍历 
void Postorder(BinaryTreeNode *); //后序遍历 
void getPreorder(){          //调用先序遍历 
Preorder(root); cout<<endl;
}                 
void getinorder(){           //调用中序遍历 inorder(root); cout<<endl;
} 
void getPostorder(){           //调用后序遍历 
Postorder(root); cout<<endl;
}
private:BinaryTreeNode *root;
}; 
/*.................................................................*/
void Tree::create_Tree(int x)
{
BinaryTreeNode *node = new BinaryTreeNode;
node->value = x;
node->right = node->left = NULL;
if(root == NULL)                     //当根节点为空时，建立根节点 root = node;else                                 //当有根结点存在是，寻找空子节点，按照X的值大小存储在子节点为空的左或者右子树上 {BinaryTreeNode *back;BinaryTreeNode *current = root;
while(current!=NULL)
{
back = current;
if(current->value>x)current = current->left;elsecurrent = current->right;} 
if(back->value>x)back->left = node;elseback->right = node;}
}
/*..............................................*/
void Tree::Preorder(BinaryTreeNode *temp)
{
if(temp!=NULL)
{
cout<<temp->value<<" ";
Preorder(temp->left);
Preorder(temp->right);
}
}
/*..............................................*/
void Tree::inorder(BinaryTreeNode *temp)
{
if(temp!=NULL)
{
inorder(temp->left);
cout<<temp->value<<" ";
inorder(temp->right);
}
}
/*..............................................*/
void Tree::Postorder(BinaryTreeNode *temp)
{
if(temp!=NULL)
{
Postorder(temp->left);
Postorder(temp->right);
cout<<temp->value<<" ";
}
} 
int main(int argc, char *argv[])
{
Tree tree;
int array[]={4,3,5,43,56,3,24,4,6,452};
int count = sizeof(array)/sizeof(array[0]);
cout<<"传入二叉树参数为:";    
for(int i = 0;i<count;i++)              //循环传入参数 
{
tree.create_Tree(array[i]);
cout<<array[i]<<",";
}
cout<<endl<<"前序遍历:"; 
tree.getPreorder();
cout<<endl<<"中序遍历:"; 
tree.getinorder();
cout<<endl<<"后序遍历:"; 
tree.getPostorder();
return 0;
}

新手第一次发博文，望大家多多见谅。这只是一个很基础二叉树，小伙伴可以给这个二叉树类补充方法哦，同时也欢迎批评和指正，嘿嘿！

这篇关于使用C++实现简单二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！