1、二叉树的数据结构
typedef struct TreeNode{
char value;\\符号
struct TreeNode * LeftChild;\\左孩子
struct TreeNode * RightChild;\\右孩子
}TreeNode,*Tree;
2、二叉树的创建
Tree CreatTree()
{
char value;
TreeNode * Node;
scanf("%c",&value);
if(value=='#')//#代表空节点，用来控制树的结构
Node=NULL;
else{
Node=(TreeNode *)malloc(sizeof(TreeNode));
Node->value=value;
Node->LeftChild=CreatTree();
Node->RightChild=CreatTree();
}
return Node;
}
树的结构:
Paste_Image.png
输入:AB#C##D## ;
3、二叉树的遍历
二叉树的遍历分为前序遍历、中序遍历、后序遍历。主要分别在于根节点的遍历优先级。前序：根、左、右；中序：左、根、右；后序：左、右、根。
①递归遍历
Tree Travel(Tree tree)
{
if(tree==NULL)
return NULL;
else
{
/****前序遍历****/
printf("%c\t",tree->value);
Travel(tree->LeftChild);
Travel(tree->RightChild);
/****中序遍历****/
Travel(tree->LeftChild);
printf("%c\t",tree->value);
Travel(tree->RightChild);
/****后序遍历****/
Travel(tree->LeftChild);
Travel(tree->RightChild);
printf("%c\t",tree->value);
}
}
②非递归遍历
void PreTravel(Tree tree)
{
stack<Tree> s;
while(tree||!s.empty())
{
while(tree)
{
printf("%c\t",tree->value);
s.push(tree);
tree=tree->LeftChild;
}
tree=s.top();
s.pop();
tree=tree->RightChild;
}
}
void MiddleTravel(Tree tree)
{
stack<Tree> s;
while(tree||!s.empty())
{
while(tree)
{
s.push(tree);
tree=tree->LeftChild;
}
tree=s.top();
printf("%c\t",tree->value);
s.pop();
tree=tree->RightChild;
}
}
void PostTravel(Tree T) // 后序遍历的非递归
{
stack<Tree> S;
Tree curr = T ; // 指向当前要检查的节点
Tree previsited = NULL; // 指向前一个被访问的节点
while(curr != NULL || !S.empty()) // 栈空时结束
{
while(curr != NULL) // 一直向左走直到为空
{
S.push(curr);
curr = curr->LeftChild;
}
curr = S.top();
// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
if(curr->RightChild== NULL || curr->RightChild== previsited)
{
cout<<curr->value<<" ";
previsited = curr;
S.pop();
curr = NULL;
}
else
curr = curr->RightChild; // 否则访问右孩子
}
}
4、求二树的高度
对此问题我们可以采用递归的思想，将问题进行分解。树的高度=max{左子树的高度，右子树的高度}+1。
Paste_Image.png
int Height(Tree tree)
{
int high;
int left_high;
int right_high;
if(tree==NULL)
return 0;
left_high=Height(tree->LeftChild);
right_high=Height(tree->RightChild);
if(left_high>right_high)
high=left_high+1;
else
high=right_high+1;
return high;
}
5、二叉树的层次遍历
算法步骤：
①将根结点压进队列Q;
②对队列Q进行出队操作，打印出队结点信息，然后将出队结点的左右孩子结点（当其孩子结点存在的情况下）压入队列Q；
③重复步骤②的操作直至队列为空
void HierarchyTravel(Tree tree)
{
LinkQueue q;;
Init(&q);
EnQueue(&q,*tree);
TreeNode node;
printf("HierarchyTravel：");
while(!QueueEmpty(&q))
{
DeQueue(&q,&node);
printf("%c\t",node.value);
if(node.LeftChild)
EnQueue(&q,*node.LeftChild);
if(node.RightChild)
EnQueue(&q,*node.RightChild);
}
}
6、测试代码
#include "stdafx.h"
#include "stdlib.h"
typedef struct TreeNode{
char value;
struct TreeNode * LeftChild;
struct TreeNode * RightChild;
}TreeNode,*Tree;
typedef struct QNode{
TreeNode Node;
struct QNode * next;
}QNode,*QueueNode;
typedef struct LinkQueue{
QueueNode front;
QueueNode rear;
}LinkQueue;
Tree CreatTree()
{
char value;
TreeNode * Node;
scanf("%c",&value);
if(value=='#')
Node=NULL;
else{
Node=(TreeNode *)malloc(sizeof(TreeNode));
Node->value=value;
Node->LeftChild=CreatTree();
Node->RightChild=CreatTree();
}
return Node;
}
void PreTravel(Tree tree)
{
if(tree)
{
printf("%c\t",tree->value);
PreTravel(tree->LeftChild);
PreTravel(tree->RightChild);
}
}
void MiddleTravel(Tree tree)
{
if(tree)
{
MiddleTravel(tree->LeftChild);
printf("%c\t",tree->value);
MiddleTravel(tree->RightChild);
}
}
void PostTravel(Tree tree)
{
if(tree)
{
PostTravel(tree->LeftChild);
PostTravel(tree->RightChild);
printf("%c\t",tree->value);
}
}
void Init(LinkQueue *q)//队列初始化
{
q->front=q->rear=(QueueNode)malloc(sizeof(QNode));
if(!q->front)
exit(0);
q->front->next=NULL;
}
void EnQueue(LinkQueue *q,TreeNode treenode)//入队
{
QueueNode qnode;
qnode=(QueueNode)malloc(sizeof(QNode));
qnode->Node=treenode;
/****插入队列****/
qnode->next=q->rear->next;
q->rear->next=qnode;
/****改队尾指针****/
q->rear=qnode;
}
void DeQueue(LinkQueue *q,TreeNode *node)//出队
{
QueueNode p;
p=q->front->next;
*node=p->Node;
q->front->next=p->next;
if(q->rear==p) //p将被释放，需要对q->rear进行处理。（不能缺)
q->rear=q->front;
free(p);
}
int QueueEmpty(LinkQueue *q)//判断队列是否为空
{
if(q->rear==q->front)
return 1;
else
return 0;
}
void HierarchyTravel(Tree tree)
{
LinkQueue q;;
Init(&q);
EnQueue(&q,*tree);
TreeNode node;
while(!QueueEmpty(&q))
{
DeQueue(&q,&node);
printf("%c\t",node.value);
if(node.LeftChild)
EnQueue(&q,*node.LeftChild);
if(node.RightChild)
EnQueue(&q,*node.RightChild);
}
}
int Height(Tree tree)
{
int high;
int left_high;
int right_high;
if(tree==NULL)
return 0;
left_high=Height(tree->LeftChild);
right_high=Height(tree->RightChild);
if(left_high>right_high)
high=left_high+1;
else
high=right_high+1;
return high;
}
int _tmain(int argc, _TCHAR* argv[])
{
Tree tree;
int high;
printf("输入二叉树节点:");
tree=CreatTree();
printf("\n中序遍历:");
MiddleTravel(tree);
printf("\n先序遍历:");
PreTravel(tree);
printf("\n后序遍历:");
PostTravel(tree);
high=Height(tree);
printf("\n层次遍历:");
HierarchyTravel(tree);
printf("\n树高是:%d\n",high);
system("PAUSE");
return 0;
}
Paste_Image.png
7、二叉树的非递归遍历代码
#include "stdafx.h"
#include "stdlib.h"
#include <stack>
#include <iostream>
using namespace std;
typedef struct TreeNode{
char value;
struct TreeNode * LeftChild;
struct TreeNode * RightChild;
}TreeNode,*Tree;
Tree CreatTree()
{
char value;
TreeNode * Node;
scanf("%c",&value);
if(value=='#')
Node=NULL;
else{
Node=(TreeNode *)malloc(sizeof(TreeNode));
Node->value=value;
Node->LeftChild=CreatTree();
Node->RightChild=CreatTree();
}
return Node;
}
void PreTravel(Tree tree)
{
stack<Tree> s;
while(tree||!s.empty())
{
while(tree)
{
printf("%c\t",tree->value);
s.push(tree);
tree=tree->LeftChild;
}
tree=s.top();
s.pop();
tree=tree->RightChild;
}
}
void MiddleTravel(Tree tree)
{
stack<Tree> s;
while(tree||!s.empty())
{
while(tree)
{
s.push(tree);
tree=tree->LeftChild;
}
tree=s.top();
printf("%c\t",tree->value);
s.pop();
tree=tree->RightChild;
}
}
void PostTravel(Tree T) // 后序遍历的非递归
{
stack<Tree> S;
Tree curr = T ; // 指向当前要检查的节点
Tree previsited = NULL; // 指向前一个被访问的节点
while(curr != NULL || !S.empty()) // 栈空时结束
{
while(curr != NULL) // 一直向左走直到为空
{
S.push(curr);
curr = curr->LeftChild;
}
curr = S.top();
// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
if(curr->RightChild== NULL || curr->RightChild== previsited)
{
cout<<curr->value<<" ";
previsited = curr;
S.pop();
curr = NULL;
}
else
curr = curr->RightChild; // 否则访问右孩子
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Tree tree;
int high;
printf("输入二叉树节点:");
tree=CreatTree();
printf("\n中序遍历:");
MiddleTravel(tree);
printf("\n先序遍历:");
PreTravel(tree);
printf("\n后序遍历:");
PostTravel(tree);
/* high=Height(tree);
printf("\n层次遍历:");
HierarchyTravel(tree);
printf("\n树高是:%d\n",high);*/
system("PAUSE");
return 0;
}
