顺序存储结构

数据结构

const int MAX_TREE_SIZE = 100;
typedef int SeqBTree[MAX_TREE_SIZE + 1];//0位置存储结点个数

构建

数组依次递增对应按层构建二叉树

输出

凹入表示法输出

void PrintSeqBTree(const SeqBTree t,int i)//凹入表示法打印以i为根节点的完全二叉树
{
    
 int k = log(t[0]) / log(2) + 1;//层数
 if (i > t[0]) return;
 int m = log(i) / log(2);
 while (m--) cout << ' ';
 cout << t[i];
 m = k - (int)(log(i) / log(2) + 1);
 while (m--) cout << '-';
 cout << endl;
 PrintSeqBTree(t, i * 2);
 PrintSeqBTree(t, i * 2 + 1);
}

源码

#include<iostream>
#include<math.h>
using namespace std;
const int MAX_TREE_SIZE = 100;
typedef int SeqBTree[MAX_TREE_SIZE + 1];//0位置存储结点个数
void PrintSeqBTree(const SeqBTree t,int i)//凹入表示法打印以i为根节点的完全二叉树
{
    
 int k = log(t[0]) / log(2) + 1;//层数
 if (i > t[0]) return;
 int m = log(i) / log(2);
 while (m--) cout << ' ';
 cout << t[i];
 m = k - (int)(log(i) / log(2) + 1);
 while (m--) cout << '-';
 cout << endl;
 PrintSeqBTree(t, i * 2);
 PrintSeqBTree(t, i * 2 + 1);
}
int main()
{
    
 int i;
 SeqBTree bt;
 cout << "请输入二叉树的结点数：";
 cin >> bt[0];
 cout << "请依次输入二叉树的各个结点：" << endl;
 for (i = 1; i <= bt[0]; i++) cin >> bt[i];
 PrintSeqBTree(bt,1);
 return 0;
}

链式存储结构

数据结构

typedef struct BTNode {
    
 char data;
 BTNode* lChild;
 BTNode* rChild;
}BTNode, * BTTree;

构建二叉链表

由先序遍历序列和中序遍历序列构建

BTTree CreatBTTreeByPreAndInfixOrder(char* pre, char* in,int n)//根据先序和中序遍历序列建立二叉链表
{
    
 if (n <= 0) return NULL;
 int i;
 BTTree t = (BTTree)malloc(sizeof(BTNode));
 t->data = pre[0];
 for (i = 0; in[i] != pre[0]; i++);
 t->lChild = CreatBTTreeByPreAndInfixOrder(pre + 1, in, i);
 t->rChild = CreatBTTreeByPreAndInfixOrder(pre + i + 1, in + i + 1, n - i - 1);
 return t;
}

由中序遍历序列和后序遍历序列构建

BTTree CreatBTTreeByInfixAndPostOrder(char* in, char* post, int n)//根据中序和后序遍历序列建立二叉链表
{
    
 if (n <= 0) return NULL;
 int i;
 BTTree t = (BTTree)malloc(sizeof(BTNode));
 t->data = post[n - 1];
 for (i = 0; in[i] != post[n - 1]; i++);
 t->lChild = CreatBTTreeByInfixAndPostOrder(in, post, i);
 t->rChild = CreatBTTreeByInfixAndPostOrder(in + i + 1, post + i, n - i - 1);
 return t;
}

输出二叉链表

按先序遍历输出

void PrintBTTreeByPreorder(BTTree t)//打印先序遍历二叉链表
{
    
 if (t)
 {
    
  cout << t->data;
  PrintBTTreeByPreorder(t->lChild);
  PrintBTTreeByPreorder(t->rChild);
 }
}

按中序遍历输出

void PrintBTTreeByInfixorder(BTTree t)//打印中序遍历二叉链表
{
    
 if (t)
 {
    
  PrintBTTreeByInfixorder(t->lChild);
  cout << t->data;
  PrintBTTreeByInfixorder(t->rChild);
 }
}

按后序遍历输出

void PrintBTTreeByPostorder(BTTree t)//打印后序遍历二叉链表
{
    
 if (t)
 {
    
  PrintBTTreeByPostorder(t->lChild);
  PrintBTTreeByPostorder(t->rChild);
  cout << t->data;
 }
}

源码

#include<iostream>
#include<stdlib.h>
#include<String.h>
using namespace std;
typedef struct BTNode {
    
 char data;
 BTNode* lChild;
 BTNode* rChild;
}BTNode, * BTTree;
void PrintBTTreeByPreorder(BTTree t)//打印先序遍历二叉链表
{
    
 if (t)
 {
    
  cout << t->data;
  PrintBTTreeByPreorder(t->lChild);
  PrintBTTreeByPreorder(t->rChild);
 }
}
void PrintBTTreeByInfixorder(BTTree t)//打印中序遍历二叉链表
{
    
 if (t)
 {
    
  PrintBTTreeByInfixorder(t->lChild);
  cout << t->data;
  PrintBTTreeByInfixorder(t->rChild);
 }
}
void PrintBTTreeByPostorder(BTTree t)//打印后序遍历二叉链表
{
    
 if (t)
 {
    
  PrintBTTreeByPostorder(t->lChild);
  PrintBTTreeByPostorder(t->rChild);
  cout << t->data;
 }
}
BTTree CreatBTTreeByPreAndInfixOrder(char* pre, char* in,int n)//根据先序和中序遍历序列建立二叉链表
{
    
 if (n <= 0) return NULL;
 int i;
 BTTree t = (BTTree)malloc(sizeof(BTNode));
 t->data = pre[0];
 for (i = 0; in[i] != pre[0]; i++);
 t->lChild = CreatBTTreeByPreAndInfixOrder(pre + 1, in, i);
 t->rChild = CreatBTTreeByPreAndInfixOrder(pre + i + 1, in + i + 1, n - i - 1);
 return t;
}
BTTree CreatBTTreeByInfixAndPostOrder(char* in, char* post, int n)//根据中序和后序遍历序列建立二叉链表
{
    
 if (n <= 0) return NULL;
 int i;
 BTTree t = (BTTree)malloc(sizeof(BTNode));
 t->data = post[n - 1];
 for (i = 0; in[i] != post[n - 1]; i++);
 t->lChild = CreatBTTreeByInfixAndPostOrder(in, post, i);
 t->rChild = CreatBTTreeByInfixAndPostOrder(in + i + 1, post + i, n - i - 1);
 return t;
}
int main()
{
    
 char s1[20] = "BFDGAC", s2[20] = "FGDBCA";
 BTTree t = CreatBTTreeByInfixAndPostOrder(s1, s2, 6);
 PrintBTTreeByPreorder(t);
 return 0;
}