一、基本概念
BinaryTree.png
二叉树：每个结点的子结点个数不大于2的树，叫做二叉树。
根结点：最顶部的那个结点叫做根结点，根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。
子结点：除了根结点外的结点，都叫子结点。
叶子结点：没有子结点的结点，叫做叶子结点。比如上图中的“1”结点、“5”结点和“11”结点。
二叉树的遍历，有三种：
（1）前序遍历：先遍历根结点，再遍历左子树，最后遍历右子树。上图的前序遍历顺序为：7->4->1->5->12->8->11->13
（2）中序遍历：先遍历左子树，再遍历根结点，最后遍历右子树。上图的中序遍历顺序为：1->4->5->7->8->11->12->13
（3）后序遍历：先遍历左子树，再遍历右子树，最后遍历根结点。上图的后序遍历顺序为：1->5->4->11->8->13->12->7
二叉排序树：左子结点 <= 根结点 <= 右子结点的二叉树，叫做二叉排序树（或排序二叉树）。上图就是一个二叉排序树。
二、二叉树的建立和遍历
#include<iostream>
using namespace std;
struct BTreeNode //定义二叉树结点的数据结构
{
int data;
BTreeNode *leftChild; //左子结点指针
BTreeNode *rightChild; //右子结点指针
};
class Btree
{
private: //private可以不写，因为默认就是private
BTreeNode *root; //根结点的指针
void preOrderTraverse(BTreeNode *); //前序遍历具体过程，内部接口
void inOrderTraverse(BTreeNode *); //中序遍历具体过程，内部接口
void postOrderTraverse(BTreeNode *);//后序遍历具体过程，内部接口
public:
Btree() //构造函数
{
root = NULL;
}
void createBtree(int);
void preOrder() //前序遍历方法，对外接口
{
preOrderTraverse(root);
}
void inOrder() //中序遍历方法，对外接口
{
inOrderTraverse(root);
}
void postOrder() //后序遍历方法，对外接口
{
postOrderTraverse(root);
}
};
void Btree::createBtree(int x)
{
BTreeNode *newnode = new BTreeNode;
newnode->data = x;
newnode->leftChild = NULL;
newnode->rightChild = NULL;
if(NULL == root) //如果没有根结点，则第一个结点就是根结点
{
root = newnode;
}
else //根据数值大小判断是左子结点还是右子结点
{
BTreeNode *father;
BTreeNode *current = root;
while(current != NULL) //找到要插入newnode的节点指针
{
father = current;
if(current->data > x)
{
current = current->leftChild;
}
else
{
current = current->rightChild;
}
}
//newnode插入到father结点的左（或右）子结点位置
if(father->data > x)
{
father->leftChild = newnode;
}
else
{
father->rightChild = newnode;
}
}
}
void Btree::preOrderTraverse(BTreeNode *root)
{
if(root)
{
cout << root->data << " ";
preOrderTraverse(root->leftChild);
preOrderTraverse(root->rightChild);
}
}
void Btree::inOrderTraverse(BTreeNode *root)
{
if(root)
{
inOrderTraverse(root->leftChild);
cout << root->data << " ";
inOrderTraverse(root->rightChild);
}
}
void Btree::postOrderTraverse(BTreeNode *root)
{
if(root)
{
postOrderTraverse(root->leftChild);
postOrderTraverse(root->rightChild);
cout << root->data << " ";
}
}
int main()
{
Btree btree;
int a[] = {7, 4, 1, 5, 12, 8, 13, 11};
//排序二叉树：左子结点<根节点<右子节点
cout << "建立排序二叉树: ";
int cnt = sizeof(a) / sizeof(int);
for(int i = 0; i < cnt; i++)
{
cout << a[i] << " ";
btree.createBtree(a[i]);
}
cout << endl;
cout << "前序遍历: ";
btree.preOrder();
cout << endl;
cout << "中序遍历: ";
btree.inOrder();
cout << endl;
cout << "后序遍历: ";
btree.postOrder();
cout << endl;
return 0;
}
运行结果：
建立排序二叉树： 7 4 1 5 12 8 13 11
前序遍历：7 4 1 5 12 8 11 13
中序遍历：1 4 5 7 8 11 12 13
后序遍历：1 5 4 11 8 13 12 7
加入少儿信息学奥赛QQ群请扫左侧二维码，关注微信公众号请扫右侧二维码
QQ群和公众号.png
