利用二叉树的二叉链式存储结构设计并实现各种操作算法。
基本操作
二叉树的基本操作算法实现
(1) 利用二叉树字符串“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建二叉树的二叉链式存储结构；
(2) 输出该二叉树；
(3) 输出‘H’节点的左、右孩子结点值；
(4) 输出该二叉树的结点个数、叶子结点个数、二叉树的度和高度。
#include <iostream> using namespace std; typedef int Status; #define OK 1 #define MAXSIZE 100 //二叉树的二叉链表存储表示 typedef struct BiTNode { char data; struct BiTNode* lchild, * rchild; //定义左右孩子 }*BiTree, BiTNode; //中序遍历递归输出二叉树 void ShowBiTree(BiTree T) { if (T != NULL) { ShowBiTree(T->lchild);//中序遍历左子树 cout << T->data;//访问根节点 ShowBiTree(T->rchild);//中序遍历右子树 } } //‘H’节点的左、右孩子结点值 Status SearchBiTree(BiTree T) { if (T == NULL) return 0; else if (T->data == 'H' && T->lchild != NULL && T->rchild != NULL) { cout << "H" << "的左孩子为" << T->lchild->data << endl; cout << "H" << "的右孩子为" << T->rchild->data << endl; } else { SearchBiTree(T->lchild); SearchBiTree(T->rchild); } return OK; } //统计二叉树中结点的个数 int NodeCount(BiTree T) { if (T == NULL) return 0; else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; } //统计二叉树T中叶子结点个数 int LeafCount(BiTree T) { static int count=0; if (T != NULL){ if (T->lchild == NULL && T->rchild == NULL) count = count + 1; count = LeafCount(T->lchild); count = LeafCount(T->rchild); } return count; } //统计二叉树的度 int DegreeBiTree(BiTree T) { if (T == NULL) return 0; else if ((T->lchild != NULL && T->rchild == NULL) || (T->lchild == NULL && T->rchild != NULL)) return 1; else if (T->lchild != NULL && T->rchild != NULL) return 2; } //统计二叉树的深度 int Depth(BiTree T) { if (T == NULL) return 0; else { int m = Depth(T->lchild); int n = Depth(T->rchild); if (m > n) return (m + 1); else return (n + 1); } } //创建二叉树 Status CreateBiTree(BiTree& T) { BiTree S[MAXSIZE]; BiTNode* p = NULL; int top = 0, a = 0; T = NULL; char ch; cin >> ch;//输入树的结点 while (ch != '#') { switch (ch) { case '(':S[++top] = p; a = 1; break; //入栈，k=1为左子树； case ')':top--; break; //出栈； case ',':a = 2; break; //k=2为右子树 default: p = new BiTNode;//生成根节点 p->data = ch; p->lchild = p->rchild = NULL; if (T == NULL) T = p; else { switch (a) { case 1:S[top]->lchild = p; break; case 2:S[top]->rchild = p; break; } } break; } cin >> ch; } return OK; } int main() { cout << "输入二叉树(以#结束):"; BiTree T; CreateBiTree(T); cout << "中序遍历输出："; ShowBiTree(T); cout << endl; SearchBiTree(T); cout << "二叉树中结点的个数为："<<NodeCount(T) << endl; cout << "二叉树中叶子结点个数为："<< LeafCount(T) << endl; cout << "二叉树的度为："<<DegreeBiTree(T) << endl; cout << "二叉树的深度为："<< Depth(T) << endl; }
遍历
实现上述二叉树的先序、中序和后序遍历的递归和非递归算法。
#include <iostream> using namespace std; typedef int Status; #define OK 1 #define MAXSIZE 100 typedef int Status; //二叉树的二叉链表存储表示 typedef struct BiTNode { char data; struct BiTNode* lchild, * rchild; //定义左右孩子 }*BiTree, BiTNode; //创建二叉树 Status CreateBiTree(BiTree& T) { BiTree S[MAXSIZE]; BiTNode* p = NULL; int top = 0, a = 0; T = NULL; char ch; cin >> ch;//输入树的结点 while (ch != '#') { switch (ch) { case '(':S[++top] = p; a = 1; break; //入栈，k=1为左子树； case ')':top--; break; //出栈； case ',':a = 2; break; //k=2为右子树 default: p = new BiTNode;//生成根节点 p->data = ch; p->lchild = p->rchild = NULL; if (T == NULL) T = p; else { switch (a) { case 1:S[top]->lchild = p; break; case 2:S[top]->rchild = p; break; } } break; } cin >> ch; } return OK; } //先序遍历递归输出二叉树 void FShowBiTree(BiTree T) { if (T != NULL) { cout << T->data;//访问根节点 FShowBiTree(T->lchild);//先序遍历左子树 FShowBiTree(T->rchild);//先序遍历右子树 } } //中序遍历递归输出二叉树 void MShowBiTree(BiTree T){ if (T != NULL) { MShowBiTree(T->lchild);//中序遍历左子树 cout << T->data;//访问根节点 MShowBiTree(T->rchild);//中序遍历右子树 } } //后序遍历递归输出二叉树 void LShowBiTree(BiTree T) { if (T != NULL) { LShowBiTree(T->lchild);//后序遍历左子树 LShowBiTree(T->rchild);//后序遍历右子树 cout << T->data;//访问根节点 } } //先序遍历非递归算法 Status FShowBiTree01(BiTree T) { BiTree stack[MAXSIZE], p = T; int top = -1; while (p || top > -1) { cout << p->data; top++; stack[top] = p;//当前节点进栈 p = p->lchild;//在左子树上移动 //若左子树为空，则让栈顶元素出栈，并在右子树上寻找直到pCur不为空 while (!p && top > -1) { p = stack[top]; top--; p= p->rchild; } } return OK; } //中序遍历非递归算法 Status MShowBiTree01(BiTree T) { BiTree stack[MAXSIZE], p = T; int top = -1; while (p || top > -1) { if (p->lchild) { //如果当前节点有左子树，则入栈 top++; stack[top] = p; p = p->lchild; } else { cout << p->data;//无左子树，直接访问当前节点 p = p->rchild;//进入右子树继续访问 //无右子树，则栈顶元素出栈并打印 while (!p && top > -1) { p = stack[top]; top--; cout << p->data; p = p->rchild; } } } return OK; } //后序遍历非递归算法 Status LShowBiTree01(BiTree T) { BiTree p = T, S[100], pre=NULL; int top = 0, flag = 1; if (p) do { while (p) { S[top++] = p; p = p->lchild; } // p所有左节点入栈 flag = 1; while (top != 0 && flag == 1) { p = S[top - 1]; if (p->rchild == pre || p->rchild == NULL) { //右孩子不存在或右孩子已访问 top--; cout << p->data; pre = p; //指向被访问节点 } else { //继续遍历右子树 p = p->rchild; flag = 0; } } } while (top != 0); return OK; } int main() { cout << "输入二叉树(以#结束):"; BiTree T; CreateBiTree(T); cout << "先序递归遍历输出："; FShowBiTree(T); cout << endl; cout << "中序递归遍历输出："; MShowBiTree(T); cout << endl; cout << "后序递归遍历输出："; LShowBiTree(T); cout << endl; cout << "先序非递归遍历输出："; FShowBiTree01(T); cout << endl; cout << "中序非递归遍历输出："; MShowBiTree01(T); cout << endl; cout << "后序非递归遍历输出："; LShowBiTree01(T); cout << endl; }
