一、二叉樹的遞歸遍歷

二叉樹的遞歸遍歷.c

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h>//二叉樹的結(jié)點 typedef struct BINARYNODE {char ch;struct BINARYNODE *lchild;struct BINARYNODE *rchild; }BinaryNode;void Recursion(BinaryNode* root) {if (root == NULL) //退出條件return;//先序遍歷printf("%c", root->ch); //訪問根結(jié)點Recursion(root->lchild); //左子樹遍歷Recursion(root->rchild); //右子樹遍歷//中序遍歷/*Recursion(root->lchild);printf("%c ", root->ch);Recursion(root->rchild);*///后序遍歷/*Recursion(root->lchild);Recursion(root->rchild);printf("%c ", root->ch);*/ }void CreateBinaryTree() {/*A/ \B F\ \C G/ \ /D E H*///創(chuàng)建結(jié)點BinaryNode node1 = { 'A',NULL,NULL }; //字符需用'' 字符串用""BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };node1.lchild = &node2;node1.rchild = &node6;node2.lchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;//遞歸遍歷Recursion(&node1); }int main() {CreateBinaryTree();return 0; }

運行結(jié)果：

二、求二叉樹的葉子結(jié)點數(shù)

求二叉樹的葉子結(jié)點數(shù).cpp

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h>//二叉樹的結(jié)點 typedef struct BINARYNODE {char ch;struct BINARYNODE *lchild;struct BINARYNODE *rchild; }BinaryNode; int num = 0; void CaculateLeafNum(BinaryNode* root) {if (root == NULL) //退出條件return;if (root->lchild == NULL && root->rchild == NULL){num++;}CaculateLeafNum(root->lchild); //左子樹遍歷CaculateLeafNum(root->rchild); //右子樹遍歷 }void CaculateLeafNum(BinaryNode* root,int *pNum) {if (root == NULL) //退出條件return;if (root->lchild == NULL && root->rchild == NULL){(*pNum)++;}CaculateLeafNum(root->lchild,pNum); //左子樹遍歷CaculateLeafNum(root->rchild,pNum); //右子樹遍歷 }void CreateBinaryTree() {/*A/ \B F\ \C G/ \ /D E H*///創(chuàng)建結(jié)點BinaryNode node1 = { 'A',NULL,NULL }; //字符需用'' 字符串用""BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };node1.lchild = &node2;node1.rchild = &node6;node2.lchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;//葉子結(jié)點個數(shù)/*CaculateLeafNum(&node1);printf("葉子結(jié)點數(shù)：%d",num);*/int leafNum = 0;CaculateLeafNum(&node1, &leafNum);printf("葉子結(jié)點數(shù)：%d", leafNum);}int main() {CreateBinaryTree();return 0; }

?

運行結(jié)果：

?

三、求樹的高度

求樹的高度.cpp

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h>//二叉樹的結(jié)點 typedef struct BINARYNODE {char ch;struct BINARYNODE *lchild;struct BINARYNODE *rchild; }BinaryNode;int getTreeHeight(BinaryNode* root) {if (root == NULL) //退出條件return 0;//求出左子樹的高度int lheight = getTreeHeight(root->rchild);//求出右子樹的高度int rheight = getTreeHeight(root->lchild);//取左子樹和右子樹中最大值+1int height = lheight > rheight ? lheight + 1 : rheight + 1;return height; }void CreateBinaryTree() {/*A/ \B F\ \C G/ \ /D E H*///創(chuàng)建結(jié)點BinaryNode node1 = { 'A',NULL,NULL }; //字符需用'' 字符串用""BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };node1.lchild = &node2;node1.rchild = &node6;node2.lchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;//求樹的高度int height = getTreeHeight(&node1);printf("樹的高度：%d\n", height);}int main() {CreateBinaryTree(); return 0; }

運行結(jié)果：

四、二叉樹的拷貝和釋放

二叉樹的拷貝和釋放.cpp

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h>//二叉樹的結(jié)點 typedef struct BINARYNODE {char ch;struct BINARYNODE *lchild;struct BINARYNODE *rchild; }BinaryNode;//遍歷二叉樹 void Recursion(BinaryNode* root) {if (root == NULL) //退出條件return;//先序遍歷printf("%c", root->ch); //訪問根結(jié)點Recursion(root->lchild); //左子樹遍歷Recursion(root->rchild); //右子樹遍歷 }//拷貝二叉樹 BinaryNode* CopyBinaryTree(BinaryNode* root) {if (root == NULL)return NULL;//拷貝左子樹BinaryNode* lchild=CopyBinaryTree(root->lchild);//拷貝右子樹BinaryNode* rchild=CopyBinaryTree(root->rchild);//創(chuàng)建結(jié)點BinaryNode* newnode =(BinaryNode*) malloc(sizeof(BinaryNode));newnode->ch = root->ch;newnode->lchild = lchild;newnode->rchild = rchild;return newnode;}//釋放二叉樹內(nèi)存 void FreeSpaceBinaryTree(BinaryNode* root) {if (root == NULL)return;//釋放左子樹FreeSpaceBinaryTree(root->lchild);//釋放右子樹FreeSpaceBinaryTree(root->rchild);//釋放當前結(jié)點FreeSpaceBinaryTree(root); } void CreateBinaryTree() {/*A/ \B F\ \C G/ \ /D E H*///創(chuàng)建結(jié)點BinaryNode node1 = { 'A',NULL,NULL }; //字符需用'' 字符串用""BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };node1.lchild = &node2;node1.rchild = &node6;node2.lchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;BinaryNode *root = CopyBinaryTree(&node1);Recursion(root);FreeSpaceBinaryTree(root);}int main() {CreateBinaryTree();return 0; }

運行結(jié)果：

五、二叉樹的非遞歸遍歷

LinkList.h

#include<stdlib.h> #include<stdio.h> #include<string.h> #define MAX_SIZE 1024 #define TRUE 1 #define FALSE 0//鏈表結(jié)點--存儲下一個結(jié)點指針 typedef struct LINKNODE {struct LINKNODE *next; }LinkNode;//鏈表--保存頭結(jié)點,和鏈表長度 typedef struct LINKLIST {struct LINKNODE head;int size; }LinkList;//初始化 LinkList* Init_linkList();//壓入元素 void Push_LinkList(LinkList* stack, LinkNode* data);//取出棧頂元素 LinkNode* Top_LinkList(LinkList* stack);//彈出棧頂元素 void Pop_LinkList(LinkList* stack);//判斷是否為空 int IsEmpty_LinkList(LinkList* stack);//返回棧元素個數(shù) int Size_LinkList(LinkList* stack);//清空棧元素 void Clear_LinkList(LinkList* stack);//銷毀棧元素 void FreeSpace_LinkList(LinkList* stack);

LinkList.c

#include"LinkList.h" //初始化 LinkList* Init_linkList() {LinkList* stack = (LinkList*)malloc(sizeof(LinkList));stack->head.next = NULL;stack->size = 0;return stack; }//壓入元素 void Push_LinkList(LinkList* stack, LinkNode* data) {if (stack == NULL){return;}if (data == NULL){return;}data->next = stack->head.next;//stack->head.next = data->next; //問題2：沒有繞對。。stack->head.next = data;stack->size++; }//返回棧頂元素 LinkNode* Top_LinkList(LinkList* stack) {if (stack == NULL){return NULL;}if (stack->size == 0) {return NULL;}return stack->head.next; }//彈出棧頂元素 void Pop_LinkList(LinkList* stack) {if (stack == NULL){return;}if (stack->size == 0) {return;}//第一個有效結(jié)點LinkNode *pNext = stack->head.next;//pNext->next = stack->head.next; 我的錯誤做法stack->head.next = pNext->next;stack->size--;}//判斷是否為空 int IsEmpty_LinkList(LinkList* stack) {if (stack == NULL){return -1;}if (stack->size == 0)return TRUE;return FALSE; }//返回棧元素個數(shù) int Size_LinkList(LinkList* stack) {if (stack == NULL){return -1;}return stack->size; }//清空棧元素 void Clear_LinkList(LinkList* stack) {if (stack == NULL){return;}stack->head.next = NULL;stack->size = 0; }//銷毀棧元素 void FreeSpace_LinkList(LinkList* stack) {if (stack == NULL){return;}free(stack); }

二叉樹的非遞歸遍歷.c

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #include"LinkList.h" #define MY_FALSAE 0 #define MY_TRUE 1 //二叉樹的結(jié)點 typedef struct BINARYNODE {char ch;struct BINARYNODE *lchild;struct BINARYNODE *rchild; }BinaryNode;//二叉樹的非遞歸遍歷 typedef struct BITREESTACKNODE {LinkNode node;BinaryNode* root;int flag; }BiTreeStackNode;//創(chuàng)建棧中結(jié)點 BiTreeStackNode* CreateBiTreeStackNode(BinaryNode* node, int flag) {BiTreeStackNode* newnode = (BiTreeStackNode*)malloc(sizeof(BiTreeStackNode));newnode->root = node;newnode->flag = flag;return newnode; }void NonRecursion(BinaryNode* root) {//創(chuàng)建棧LinkList *stack = Init_linkList();//把根結(jié)點扔到棧里Push_LinkList(stack, (LinkNode*)CreateBiTreeStackNode(root, MY_FALSAE));while (Size_LinkList(stack) > 0){//彈出棧頂元素BiTreeStackNode* node=(BiTreeStackNode*)Top_LinkList(stack);Pop_LinkList(stack);//判斷彈出的結(jié)點是否為空if (node->root == NULL){continue;}if (node->flag == MY_TRUE){printf("%c", node->root->ch);}//先序。放入順序和遍歷順序正好相反else {//當前結(jié)點的右結(jié)點入棧Push_LinkList(stack, (LinkNode*)CreateBiTreeStackNode(node->root->rchild, MY_FALSAE));//當前結(jié)點的左結(jié)點入棧Push_LinkList(stack, (LinkNode*)CreateBiTreeStackNode(node->root->lchild, MY_FALSAE));//當前結(jié)點入棧node->flag = MY_TRUE;Push_LinkList(stack, (LinkNode*)node);} } }//遍歷二叉樹 void Recursion(BinaryNode* root) {if (root == NULL) //退出條件return;//先序遍歷printf("%c", root->ch); //訪問根結(jié)點Recursion(root->lchild); //左子樹遍歷Recursion(root->rchild); //右子樹遍歷 }//二叉樹的非遞歸遍歷 void CreateBinaryTree() {/*A/ \B F\ \C G/ \ /D E H*///創(chuàng)建結(jié)點BinaryNode node1 = { 'A',NULL,NULL }; //字符需用'' 字符串用""BinaryNode node2 = { 'B',NULL,NULL };BinaryNode node3 = { 'C',NULL,NULL };BinaryNode node4 = { 'D',NULL,NULL };BinaryNode node5 = { 'E',NULL,NULL };BinaryNode node6 = { 'F',NULL,NULL };BinaryNode node7 = { 'G',NULL,NULL };BinaryNode node8 = { 'H',NULL,NULL };node1.lchild = &node2;node1.rchild = &node6;node2.lchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;//二叉樹的非遞歸遍歷NonRecursion(&node1); } int main() {CreateBinaryTree();return 0; }

?

運行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的数据结构-树2-二叉树各种函数实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。