在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。
今天我们来实现一下二叉树的创建，三种遍历，以及查找等。
拿这个二叉树来说吧
#ifndef _TREE_H
#define _TREE_H
#define ElemType char
typedef struct BinTreeNode //二叉树节点类型
{
ElemType data;
BinTreeNode* leftChild;
BinTreeNode* rightChild;
}BinTreeNode;
typedef struct //二叉树根结点
{
BinTreeNode* root;
ElemType ref;
}BinTree;
void InitBinTree(BinTree *t); //初始化根结点
void CreateBinTree(BinTree* t); //创建二叉树
void CreateBinTree(BinTreeNode* &t);
void CreateBinTree(BinTree* t,const char* &p); //根据给好的字符串创建二叉树，毕竟每次运行都手动输入一遍字符串太难受了
void CreateBinTree(BinTreeNode* &t,const char* &p);
void PreOrder(BinTree* t); //前序遍历
void PreOrder(BinTreeNode* t);
void InOrder(BinTree* t); //中序遍历
void InOrder(BinTreeNode* t);
void PosOrder(BinTree* t); //后序遍历
void PosOrder(BinTreeNode* t);
int Height(BinTree* t); //求二叉树的深度
int Height(BinTreeNode* t);
int Size(BinTree* t); //求二叉树的大小
int Size(BinTreeNode* t);
BinTreeNode* Find(BinTree* t,char key); //根据键值查找所在节点
BinTreeNode* Find(BinTreeNode* t,char key);
BinTreeNode* Parent(BinTree* t,char key); //根据键值查找对应父节点
BinTreeNode* Parent(BinTreeNode* t,char key);
#endif首先是头文件
#include<iostream>
using namespace std;
#include<assert.h>
#include"Tree.h"
void InitBinTree(BinTree *t) //初始化根结点
{
t->root=NULL;
t->ref='#';
}
void CreateBinTree(BinTree* t) //凡是参数为BinTree* t的函数均为用户接口
{
CreateBinTree(t->root);
}
void CreateBinTree(BinTreeNode* &t) //此处为手动输入的创建函数，&的作用为引用
{
ElemType item;
cin>>item;
if(item=='#')
{
t=NULL;
}
else
{
t=(BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t!=NULL);
t->data=item;
CreateBinTree(t->leftChild);
CreateBinTree(t->rightChild);
}
}
void PreOrder(BinTree* t) //前序遍历
{
PreOrder(t->root);
}
void PreOrder(BinTreeNode* t)
{
if(t) //t为非空节点时
{
cout<<t->data<<" ";
PreOrder(t->leftChild);
PreOrder(t->rightChild);
}
}
void InOrder(BinTree* t) //中序遍历
{
InOrder(t->root);
}
void InOrder(BinTreeNode* t)
{
if(t)
{
InOrder(t->leftChild);
cout<<t->data<<" ";
InOrder(t->rightChild);
}
}
void PosOrder(BinTree* t) //后序遍历
{
PosOrder(t->root);
}
void PosOrder(BinTreeNode* t)
{
if(t)
{
PosOrder(t->leftChild);
PosOrder(t->rightChild);
cout<<t->data<<" ";
}
}
int Height(BinTree* t)
{
return Height(t->root);
}
int Height(BinTreeNode* t) //通过递归分别求左子数和右子树的高度，返回较大值
{
if(t==NULL)
return 0;
int leftHeight=Height(t->leftChild);
int rightHeight=Height(t->rightChild);
return (leftHeight>rightHeight?leftHeight:rightHeight)+1;
}
int Size(BinTree* t)
{
return Size(t->root);
}
int Size(BinTreeNode* t) //此处也可以使用static求大小
{
if(t==NULL)
return 0;
return Size(t->leftChild)+Size(t->rightChild)+1;
}
void CreateBinTree(BinTree *t, const char *&p) //不通过手动输入创建二叉树，博主使用的为ABC##DE##F##G#H##，其中#为结束的标志
{
CreateBinTree(t->root, p);
}
void CreateBinTree(BinTreeNode *&t, const char *&p)
{
if(*p=='#'||*p=='\0')
t=NULL;
else
{
t=(BinTreeNode*)malloc(sizeof(BinTreeNode));
assert("t!=NULL");
t->data=*p;
CreateBinTree(t->leftChild,++p);
CreateBinTree(t->rightChild,++p);
}
}
BinTreeNode* Find(BinTree* t,ElemType key) //根据键值求节点地质
{
return Find(t->root,key);
}
BinTreeNode* Find(BinTreeNode* t,ElemType key)
{
if(t==NULL)
return NULL;
if(t->data==key)
return t;
BinTreeNode* p = Find(t->leftChild,key);
if(p)
return p;
return Find(t->rightChild,key);
}
BinTreeNode* Parent(BinTree* t,ElemType key) //根据键值求父节点
{
return Parent(t->root,key);
}
BinTreeNode* Parent(BinTreeNode* t,ElemType key)
{
if(t==NULL)
return NULL;
BinTreeNode* p=Find(t,key);
if(p==NULL||p==t)
return NULL;
if(t->leftChild==p||t->rightChild==p)
return t;
BinTreeNode* q=Parent(t->leftChild,key);
if(q)
return q;
return Parent(t->rightChild,key);
}头文件中函数声明的实现
#include<iostream>
using namespace std;
#include"Tree.h"
int main()
{
const char *p="ABC##DE##F##G#H##";
BinTreeNode* Targe,*par;
BinTree T;
InitBinTree(&T);
CreateBinTree(&T,p);
cout<<"Pre:";
PreOrder(&T);
cout<<endl;
cout<<"In:";
InOrder(&T);
cout<<endl;
cout<<"Pos:";
PosOrder(&T);
cout<<endl;
cout<<"Size:"<<Size(&T)<<endl;
cout<<"Height:"<<Height(&T)<<endl;
Targe=Find(&T,'E');
cout<<"Find:"<<Targe->data<<endl;
par=Parent(&T,'E');
cout<<"Parent of E:"<<par->data<<endl;
}主函数部分
运行结果：
