二叉链表是什么结构,画出二叉链表存储结构
文章目录 顺序存储结构数据结构构建输出源码 链式存储结构数据结构构建二叉链表由先序遍历序列和中序遍历序列构建由中序遍历序列和后序遍历序列构建 输出二叉链表按先序遍历输出按中序遍历输出按后序遍历输出 源码
顺序存储结构 数据结构 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;}