文章目錄

• • 先序創建二叉樹
  • 二叉樹的中序、后須、層次遍歷
  • 二叉排序樹的建立

先序創建二叉樹

/*二叉鏈表存儲結構*/ typedef struct BiTNode {TElemType data;struct BiTNode* lchid, * rchid; }BiTNode,*BiTree;/*先序創建二叉樹*/ BiTree CreateBiTree(){BiTree T;//根節點TElemType item;cin >> item;if (item == '#') { //葉節點數據標志T = NULL; //若某一節點為葉子節點，則其左右子樹均為NULL，0表示建空樹}else {T = (BiTree)malloc(sizeof(BiTNode));T->data = item;T->lchid = CreateBiTree();T->rchid = CreateBiTree();}return T; }

二叉樹的中序、后須、層次遍歷

/*非遞歸中序遍歷*/ void InOrderTraverse(BiTree t) {SqStack S;InitStack(S);BiTree p = t;while (p||!StackEmpty(S)){if (p) {Push(S, (SElemType)p);p = p->lchid;}else {Pop(S, (SElemType&)p);cout << p->data;p = p->rchid;}}} /*遞歸后序遍歷*/ void PostOrder(BiTree t) {if (t) {PostOrder(t->lchid);PostOrder(t->rchid);cout << t->data;} }/*遞歸層序遍歷*/ void LevelOrder(BiTree t) {if (t){LinkQueue Q;InitQueue(Q); //設置一空隊列 EnQueue(Q, (int)t); //根結點入隊while (!QueueEmpty(Q)) //當隊非空時重復執行下列操作{DeQueue(Q, (int&)t);// Visit(p->data); //出隊訪問cout << t->data;if (t->lchid) {EnQueue(Q, (QElemType)t->lchid);}if (t->rchid) {EnQueue(Q, (QElemType)t->rchid);}}DestoryQueue(Q);} }

二叉排序樹的建立

/*二叉鏈表存儲結構*/ typedef struct BiTNode {int data;struct BiTNode* lchild, * rchild; }BiTNode, * BiTree;int SearchBST(BiTree T, int key, BiTree f, BiTree& p) //查找成功，參數p指向查找到的結點，f指向它的雙親；否則p指向key應插入的父結點或指向空（當T為空時） {if (!T){p = f;return 0;}else if (key == T->data){p = T;return 1;}else if (key < T->data)return (SearchBST(T->lchild, key, T, p));elsereturn (SearchBST(T->rchild, key, T, p)); }int InsertBST(BiTree& T, int e) //在二叉排序樹中插入值為elem的元素，T指向二叉排序樹根結點 {BiTree p = NULL, f = NULL;if (!SearchBST(T, e, f, p)) // 如果查找不成功{BiTree s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p) // 若二叉樹為空被插結點作為樹的根結點T = s; else if (e< p->data) //被插結點插入到p的左子樹中p->lchild = s;else //被插結點插入到p的右子樹中p->rchild = s; return 1;}else // 查找成功,不插return 0; }

總結

以上是生活随笔為你收集整理的二叉树、二叉排序树及其遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。