二叉树的概念与性质
定义：二叉树是有限结点的集合
二叉树有五种形态，有四种表示方法，其中括号表示法是最重要的，下面的链式存储结构也是根据括号表示法来的==
二叉树的性质：
性质1：非空二叉树上的叶子节点数等于双分支节点数加1
性质2：非空二叉树的第i层上最多有2（i-1）个结点
性质3：高度位h的二叉树最多有2（h）-1个结点
二叉树有五种形态，有四种表示方法，其中括号表示法是最重要的，下面的链式存储结构也是根据括号表示法来的==
二叉树的性质：
性质1：非空二叉树上的叶子节点数等于双分支节点数加1
性质2：非空二叉树的第i层上最多有2（i-1）个结点
性质3：高度位h的二叉树最多有2（h）-1个结点
二叉树的存储结构
二叉树的存储结构分为顺序存储和链式存储。
书上的顺序存储介绍的十分少，一笔带过了。
我理解的顺序存储应该是可以变换的，怎么变换呢，得根据题目来。
第一种形式便是一个数组存储，如下图
![5f84933b5dffc552d5a498412cc2f6e7.png]()
那我们得到了头结点怎么去寻找其他的结点呢？？？可以利用我们的顺序存储，下标规则：双亲的结点下标为 i/2 左孩子的小标为2i 右孩子的下标为2i+1
第二种形式也是一个数组存储，但是题目给我们的结点并不是有序的，我们用一个结构体数组，扩大两个值，一个结点分别存储数值，左孩子的数组下标和右孩子的数组下标，如图
![7953b24d24c73d12a8fd63061e4c33df.png]()
链式存储结构：
![0a6a2d282423c27ebfb1bea053bc5b3c.png]()
链式结构中的创建二叉树主要是根据括号表示法来创建的，为了节省时间，我没有尝试去写，直接贴了教材的源码。
书上的顺序存储介绍的十分少，一笔带过了。
我理解的顺序存储应该是可以变换的，怎么变换呢，得根据题目来。
第一种形式便是一个数组存储，如下图
那我们得到了头结点怎么去寻找其他的结点呢？？？可以利用我们的顺序存储，下标规则：双亲的结点下标为 i/2 左孩子的小标为2i 右孩子的下标为2i+1第二种形式也是一个数组存储，但是题目给我们的结点并不是有序的，我们用一个结构体数组，扩大两个值，一个结点分别存储数值，左孩子的数组下标和右孩子的数组下标，如图
链式存储结构：
链式结构中的创建二叉树主要是根据括号表示法来创建的，为了节省时间，我没有尝试去写，直接贴了教材的源码。|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
//二叉树的基本运算算法 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; //数据元素 struct node *lchild; //指向左孩子节点 struct node *rchild; //指向右孩子节点 } BTNode; void CreateBTree(BTNode * &b,char *str) //创建二叉树 { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; //建立的二叉树初始时为空 ch=str[j]; while (ch!='\0') //str未扫描完时循环 { switch(ch) { case '(':top++;St[top]=p;k=1; break; //为左孩子节点 case ')':top--;break; case ',':k=2; break; //为孩子节点右节点 default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if (b==NULL) //*p为二叉树的根节点 b=p; else //已建立二叉树根节点 { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } } void DestroyBTree(BTNode *&b) { if (b!=NULL) { DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b); } } BTNode *FindNode(BTNode *b,ElemType x) { BTNode *p; if (b==NULL) return NULL; else if (b->data==x) return b; else { p=FindNode(b->lchild,x); if (p!=NULL) return p; else return FindNode(b->rchild,x); } } BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; } int BTHeight(BTNode *b) { int lchildh,rchildh; if (b==NULL) return(0); //空树的高度为0 else { lchildh=BTHeight(b->lchild); //求左子树的高度为lchildh rchildh=BTHeight(b->rchild); //求右子树的高度为rchildh return (lchildh>rchildh)? (lchildh+1):(rchildh+1); } } void DispBTree(BTNode *b) { if (b!=NULL) { printf("%c",b->data); if (b->lchild!=NULL || b->rchild!=NULL) { printf("("); //有孩子节点时才输出( DispBTree(b->lchild); //递归处理左子树 if (b->rchild!=NULL) printf(","); //有右孩子节点时才输出, DispBTree(b->rchild); //递归处理右子树 printf(")"); //有孩子节点时才输出) } } } /*以下主函数用做调试 void main() { BTNode *b; CreateBTree(b,"A(B(D,E),C(,F))"); DispBTree(b); printf("\n"); } */ |
二叉树的前中后遍历方法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
//先序、中序和后序递归遍历算法 #include "btree.cpp" void PreOrder(BTNode *b) //先序遍历的递归算法 { if (b!=NULL) { printf("%c ",b->data); //访问根结点 PreOrder(b->lchild); //先序遍历左子树 PreOrder(b->rchild); //先序遍历右子树 } } void InOrder(BTNode *b) //中序遍历的递归算法 { if (b!=NULL) { InOrder(b->lchild); //中序遍历左子树 printf("%c ",b->data); //访问根结点 InOrder(b->rchild); //中序遍历右子树 } } void PostOrder(BTNode *b) //后序遍历的递归算法 { if (b!=NULL) { PostOrder(b->lchild); //后序遍历左子树 PostOrder(b->rchild); //后序遍历右子树 printf("%c ",b->data); //访问根结点 } } int main() { BTNode *b; CreateBTree(b,"A(B(D(,G)),C(E,F))"); printf("b:");DispBTree(b);printf("\n"); printf("先序遍历序列:");PreOrder(b);printf("\n"); printf("中序遍历序列:");InOrder(b);printf("\n"); printf("后序遍历序列:");PostOrder(b);printf("\n"); DestroyBTree(b); return 1; } |
二叉树的非递归遍历方法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 |
//先序、中序和后序非递归遍历算法 #include "btree.cpp" typedef struct { BTNode *data[MaxSize]; //存放栈中的数据元素 int top; //存放栈顶指针，即栈顶元素在data数组中的下标 } SqStack; //顺序栈类型 void InitStack(SqStack *&s) //初始化栈 { s=(SqStack *)malloc(sizeof(SqStack));//分配一个是顺序栈空间，首地址存放在s中 s->top=-1; //栈顶指针置为-1 } void DestroyStack(SqStack *&s) //销毁栈 { free(s); } bool StackEmpty(SqStack *s) //判断栈是否为空 { return(s->top==-1); } bool Push(SqStack *&s,BTNode *e) //进栈 { if (s->top==MaxSize-1) //栈满的情况，即栈上溢出 return false; s->top++; //栈顶指针增1 s->data[s->top]=e; //元素e放在栈顶指针处 return true; } bool Pop(SqStack *&s,BTNode *&e) //出栈 { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; //取栈顶指针元素的元素 s->top--; //栈顶指针减1 return true; } bool GetTop(SqStack *s,BTNode *&e) //取栈顶元素 { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; //取栈顶元素 return true; } void PreOrder1(BTNode *b) //先序非递归遍历算法1 { BTNode *p; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st Push(st,b); //根节点进栈 while (!StackEmpty(st)) //栈不为空时循环 { Pop(st,p); //退栈节点p并访问它 printf("%c ",p->data); //访问节点p if (p->rchild!=NULL) //有右孩子时将其进栈 Push(st,p->rchild); if (p->lchild!=NULL) //有左孩子时将其进栈 Push(st,p->lchild); } printf("\n"); DestroyStack(st); //销毁栈 } void PreOrder2(BTNode *b) //先序非递归遍历算法2 { BTNode *p; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st p=b; while (!StackEmpty(st) || p!=NULL) { while (p!=NULL) //访问节点p及其所有左下节点并进栈 { printf("%c ",p->data); //访问节点p Push(st,p); //节点p进栈 p=p->lchild; //移动到左孩子 } if (!StackEmpty(st)) //若栈不空 { Pop(st,p); //出栈节点p p=p->rchild; //转向处理其右子树 } } printf("\n"); DestroyStack(st); //销毁栈 } void InOrder1(BTNode *b) //中序非递归遍历算法 { BTNode *p; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st if (b!=NULL) { p=b; while (!StackEmpty(st) || p!=NULL) { while (p!=NULL) //扫描节点p的所有左下节点并进栈 { Push(st,p); //节点p进栈 p=p->lchild; //移动到左孩子 } if (!StackEmpty(st)) //若栈不空 { Pop(st,p); //出栈节点p printf("%c ",p->data); //访问节点p p=p->rchild; //转向处理其右子树 } } printf("\n"); } DestroyStack(st); //销毁栈 } void PostOrder1(BTNode *b) //后序非递归遍历算法 { BTNode *p,*r; bool flag; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st p=b; do { while (p!=NULL) //扫描节点p的所有左下节点并进栈 { Push(st,p); //节点p进栈 p=p->lchild; //移动到左孩子 } r=NULL; //r指向刚刚访问的节点，初始时为空 flag=true; //flag为真表示正在处理栈顶节点 while (!StackEmpty(st) && flag) { GetTop(st,p); //取出当前的栈顶节点p if (p->rchild==r) //若节点p的右孩子为空或者为刚刚访问过的节点 { printf("%c ",p->data); //访问节点p Pop(st,p); r=p; //r指向刚访问过的节点 } else { p=p->rchild; //转向处理其右子树 flag=false; //表示当前不是处理栈顶节点 } } } while (!StackEmpty(st)); //栈不空循环 printf("\n"); DestroyStack(st); //销毁栈 } int main() { BTNode *b; CreateBTree(b,"A(B(D(,G)),C(E,F))"); printf("b:");DispBTree(b);printf("\n"); printf("先序遍历序列1:");PreOrder1(b); printf("先序遍历序列2:");PreOrder2(b); printf("中序遍历序列:");InOrder1(b); printf("后序遍历序列:");PostOrder1(b); DestroyBTree(b); return 1; } |
二叉树的层次遍历算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
//层次遍历算法 #include "btree.cpp" #define MaxSize 100 //-------------------------------------------------------- //--循环队列基本运算算法---------------------------------- //-------------------------------------------------------- typedef struct { BTNode *data[MaxSize]; //存放队中元素 int front,rear; //队头和队尾指针 } SqQueue; //顺序队类型 void InitQueue(SqQueue *&q) //初始化队列 { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0; } void DestroyQueue(SqQueue *&q) //销毁队列 { free(q); } bool QueueEmpty(SqQueue *q) //判断队列是否为空 { return(q->front==q->rear); } bool enQueue(SqQueue *&q,BTNode *e) //进队列 { if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return true; } bool deQueue(SqQueue *&q,BTNode *&e) //出队列 { if (q->front==q->rear) //队空下溢出 return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; } //-------------------------------------------------------- void LevelOrder(BTNode *b) { BTNode *p; SqQueue *qu; InitQueue(qu); //初始化队列 enQueue(qu,b); //根结点指针进入队列 while (!QueueEmpty(qu)) //队不为空循环 { deQueue(qu,p); //出队节点p printf("%c ",p->data); //访问节点p if (p->lchild!=NULL) //有左孩子时将其进队 enQueue(qu,p->lchild); if (p->rchild!=NULL) //有右孩子时将其进队 enQueue(qu,p->rchild); } } int main() { BTNode *b; CreateBTree(b,"A(B(D(,G)),C(E,F))"); printf("b:");DispBTree(b);printf("\n"); printf("层次遍历序列:");LevelOrder(b);printf("\n"); DestroyBTree(b); return 1; } |
