一.二叉树的定义
二叉树有左右儿子之分
完美二叉树(满二叉树)除了最下面的没有儿子其他结点都有两个儿子,叶节点比较齐的,完全二叉树不是满二叉数允许缺失最后的结点
满二叉树可以达到2^k-1
边的总数=节点数-1
二.二叉树的存储结构
三.二叉树的遍历
前序遍历中序遍历后续遍历,结点所走的路径相同
#include<iostream>
using namespace std;
typedef int ElementType;
typedef struct TNode* Position;typedef Position BinTree;
typedef BinTree Element;
typedef struct TNode{ElementType Data;BinTree L;BinTree R;
};
typedef struct SNode* Stakc;
typedef struct SNode {Element *Data;int MaxSize;int top;
};
typedef struct QNode* Queue;
typedef struct QNode {Element* Data;int MaSize;int front;int back;
};
Queue Crq(int MaxSize) {Queue q = new QNode();q->Data = new Element[MaxSize];q->front = q->back = -1;q->MaSize = MaxSize;return q;
}
bool IsEmptyq(Queue q) {return q->front == q->back;
}
bool IsFullq(Queue q) {return q->front == q->back + 1;
}
void Pushq(Queue q,Element BT) {if (IsFullq(q)) {cout << "队列已满" << endl;return;}q->back = (q->back + 1) % q->MaSize;q->Data[q->back] = BT;
}
Element Delete(Queue q) {if (IsEmptyq(q)) {return NULL;}q->front = (q->front + 1) % q->MaSize;return q->Data[q->front];
}
Stakc Cr(int MaxSize) {Stakc s = new SNode();s->Data = new Element[MaxSize];s->MaxSize = MaxSize;s->top = -1;return s;
}
bool IsFull(Stakc s) {return s->MaxSize == s->top - 1;
}
bool IsEmpty(Stakc s) {return s->top == -1;
}
void Push(Stakc s, BinTree BT) {if (IsFull(s)) {cout << "堆栈已满无法插入" << endl;return;}s->Data[++s->top] = BT;
}
Element Pop(Stakc s) {if (IsEmpty(s)) {return NULL;}return s->Data[s->top--];
}
//二叉树插入
void insertTree(BinTree zs, ElementType num,int x ) {//x==0左插x==1右插BinTree ss,node;ss = zs;node = new TNode();node->Data = num;node->L = node->R = NULL;if (x == 0) {while (ss->L) {ss= ss->L;}ss->L = node;}else {while (ss->R) {ss = ss->R;}ss->R = node;}
}
//递归中序遍历
void InorderTraversal(BinTree BT)
{if (BT) {InorderTraversal(BT->L);/* 此处假设对BT结点的访问就是打印数据 */printf("%d ", BT->Data); /* 假设数据为整型 */InorderTraversal(BT->R);}
}
//递归前序遍历
void InorderTravers(BinTree BT) {if (BT) {cout << BT->Data<<" ";InorderTravers(BT->L);InorderTravers(BT->R);}
}
//递归后续遍历
void InorderH(BinTree BT) {if (BT) {InorderH(BT->L);InorderH(BT -> R);cout << BT->Data << " ";}
}
//非递归中序遍历
void fdgz(BinTree BT) {Stakc s = Cr(100);BinTree T = BT;while (T || !IsEmpty(s) ){while (T) {Push(s, T);T = T->L;}if (!IsEmpty(s)) {T = Pop(s);cout << T->Data << " ";T = T->R;}}
}
//非递归前序遍历
void fdgq(BinTree BT) {Stakc s = Cr(100);BinTree T = BT;while (T || !IsEmpty(s)) {while (T) {cout << T->Data << " ";Push(s, T);T = T->L;}if (!IsEmpty(s)) {T = Pop(s);T = T->R;}}
}
//非递归后续遍历(待实现)
void fdgh(BinTree BT) {Stakc s = Cr(100);BinTree T = BT;while (T || !IsEmpty(s)) {while (T) {Push(s, T);T = T->L;}if (!IsEmpty(s)) {T = Pop(s);cout << T->Data << " ";T = T->R;Push(s, T);}}
}
//层序遍历
void cencibanli(BinTree BT) {BinTree T = BT;Queue q = Crq(100);if (T == NULL)return;Pushq(q, T);while (!IsEmptyq(q)) {T = Delete(q);cout << T->Data << " ";if (T->L)Pushq(q, T->L);if (T->R)Pushq(q, T->R);}
}
//求叶子节点
void leaf(BinTree BT) {BinTree T = BT;if (T) {if (!T->L && !T->R)cout << T->Data << " ";leaf(T->L);leaf(T->R);}
}
//求树的高度
int treehigt(BinTree BT) {int HL, HR, MAXH;BinTree T = BT;if (T) {HL = treehigt(T->L);HR = treehigt(T->R);MAXH = max(HL, HR);return (MAXH + 1);}elsereturn 0;
}
int main()
{int x = 0;BinTree t1 = new TNode();t1->Data = 1;t1->R = t1->L = NULL;for (int i = 2; i <= 10; i++){insertTree(t1, i,x);x = ~x;}cout << "中序遍历";InorderTraversal(t1);cout << endl;cout << "前序遍历";InorderTravers(t1);cout << endl;cout << "后续遍历";InorderH(t1);cout << endl;cout << "层次遍历";cencibanli(t1);cout << endl;cout << "叶子结点:";leaf(t1);cout << endl;cout << "树的高度";cout << treehigt(t1) << endl;;system("pause");return 0;}