二叉树的初始化及应用：二叉树的插入，删除，二叉树的前序后序遍历

共7个文件

o：2个

c：2个

h：1个

需积分: 1 29 浏览量 2024-05-20 21:55:42 上传评论收藏 9KB ZIP 举报

二叉树是一种特殊的树结构，每个节点最多只有两个子节点，通常分为左子节点和右子节点。在计算机科学中，二叉树被广泛应用在数据结构和算法设计中，如搜索、排序、文件系统等。本节将深入探讨二叉树的初始化、插入操作、删除操作以及前序和后序遍历。 **一、二叉树的初始化** 初始化一个二叉树通常意味着创建一个空的根节点。在编程实现中，可以定义一个二叉树节点类，包含两个指向子节点的指针（通常为null）和一个表示节点值的数据域。在C++或Java中，这样的定义可能如下： ```cpp class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ``` **二、二叉树的插入操作** 二叉树的插入操作根据节点的值与当前节点值的比较来决定插入位置。如果值小于当前节点值，则向左子树递归插入；若值大于当前节点值，则向右子树递归插入。当遇到空指针时，新节点就插入到该位置。例如，插入操作的函数可以这样实现： ```cpp void insert(TreeNode*& root, int val) { if (root == NULL) { root = new TreeNode(val); } else if (val < root->val) { insert(root->left, val); } else { insert(root->right, val); } } ``` **三、二叉树的删除操作** 二叉树的删除操作相对复杂，因为可能有三种情况：要删除的节点是叶子节点、只有一个子节点或者有两个子节点。对于每种情况，都需要找到合适的节点来替代被删除节点的位置。具体实现涉及查找最小右节点、最大左节点或调整父节点的链接。 ```cpp TreeNode* deleteNode(TreeNode* root, int key) { // ... 实现代码 ... } ``` **四、二叉树的遍历** 二叉树的遍历主要包括前序遍历、中序遍历和后序遍历。 1. **前序遍历**：先访问根节点，再遍历左子树，最后遍历右子树。 2. **后序遍历**：先遍历左子树，再遍历右子树，最后访问根节点。例如，前序遍历的递归实现： ```cpp void preOrderTraversal(TreeNode* root) { if (root != NULL) { cout << root->val << " "; preOrderTraversal(root->left); preOrderTraversal(root->right); } } ``` 后序遍历的递归实现： ```cpp void postOrderTraversal(TreeNode* root) { if (root != NULL) { postOrderTraversal(root->left); postOrderTraversal(root->right); cout << root->val << " "; } } ``` 以上就是关于二叉树的初始化、插入、删除以及遍历的基本知识。理解这些概念和操作是学习数据结构和算法的重要基础，对于提升编程能力和解决实际问题具有重要作用。在实际应用中，二叉树还有许多变种，如平衡二叉树（AVL树、红黑树等）、堆（二叉堆、斐波那契堆等），它们在各自领域有着独特的优点和用途。

资源推荐

资源详情

资源评论

收起资源包目录

遍历二叉树.zip （7个子文件）

BTree22

dStruct.h 749B

Makefile 191B

dStruct.c 4KB

dStruct.o 5KB

main.o 2KB

main 13KB

main.c 396B

#include "dStruct.h" //创建新节点 PBTNode createNewNode(char data) { PBTNode new = NULL; new = malloc(sizeof(BTNode)); if(new == NULL) return NULL; new->data = data; new->lchild = NULL; new->rchild = NULL; return new; } //插入左子结点 void insertLeftNode(PBTNode root,char data) { PBTNode new = NULL; if(root == NULL) return ; new = createNewNode(data); if(new == NULL) return ; if(root->lchild == NULL) { root->lchild = new; }else { new->lchild = root->lchild; root->lchild = new; } } //插入右子结点 void insertRightNode(PBTNode root,char data); //前（先）序构造二叉树 PBTNode createBTree(void) { PBTNode proot = NULL; char data; printf("enter your data.\n"); do{ data = getchar(); }while(data == '\n'); if(data == '#'){ printf("create node finish.\n"); return NULL; } proot = createNewNode(data); printf("please input leftchild node\n"); proot->lchild = createBTree(); printf("please input rightchild node\n"); proot->rchild = createBTree(); return proot; } void preOrderTraverse(PBTNode root) { if(root == NULL){ printf("BTree is NULL.\n"); return ; } printf("%c ",root->data); if(root->lchild !=NULL)preOrderTraverse(root->lchild); if(root->rchild !=NULL)preOrderTraverse(root->rchild); } PBTNode searchBTNode(PBTNode root,char data) { if(root == NULL){ printf("BTree is NULL.\n"); return NULL; } if(root->data == data)return root; if(root->lchild != NULL)return searchBTNode(root->lchild,data); if(root->rchild != NULL)return searchBTNode(root->rchild,data); printf("%c is not in BTree.\n",data); return NULL; } PBTNode searchBTFNode(PBTNode root,char data) { PBTNode p; if(root == NULL){ printf("BTree is NULL.\n"); return NULL; } if(root->data == data){ return root; } else{ if((p = searchBTFNode(root->lchild,data)) != NULL)return p; else return searchBTFNode(root->rchild,data); } } void clearBTree(PBTNode *root) { PBTNode p,q; printf("clear-----\n"); if((*root) == NULL) return; p=(*root)->lchild; q=(*root)->rchild; free(*root); (*root) = NULL; clearBTree(&p); clearBTree(&q); } int deleteBTNode(PBTNode *root ,char data) { PBTNode p,pnode;//pnode用来指向深度最深的父结点 int cnt; if(*root == NULL){ printf("BTree is NULL.\n"); return -1; } if((*root)->data == data){ if((*root)->lchild == NULL && (*root)->rchild == NULL){ p = *root; *root = NULL; free(p); return 1; } if((*root)->lchild == NULL || (*root)->rchild == NULL){ p = *root; (*root) = (*root)->lchild == NULL?(*root)->rchild:(*root)->lchild; p->lchild = p->rchild = NULL; free(p); return 1; } if((*root)->lchild != NULL &&(*root)->rchild != NULL){ p = (*root); *root = findDeepestNode(*root,&pnode,&cnt); (*root)->rchild = p->rchild; (*root)->lchild = p->lchild; //将深度最深的叶子结点的父结点指向该结点的指针指向空 if(pnode->lchild != NULL && pnode->lchild == (*root))pnode->lchild = NULL; else if(pnode->rchild ==NULL && pnode->rchild == (*root))pnode->rchild = NULL; p->rchild = p->lchild =NULL; free(p); p = NULL; return 1; } } else{ if(deleteBTNode(&((*root)->lchild),data) == 1) return 1; if(deleteBTNode(&((*root)->rchild),data) == 1) return 1; } return 0 ; } //返回深度最深的叶子结点的地址，并将该结点的父结点的地址存在pnode中 PBTNode findDeepestNode(PBTNode root,PBTNode *pnode,int *cnt){ PBTNode pl,pr,lpnode,rpnode; int lcnt,rcnt; lcnt = rcnt = 0; if(root == NULL)return NULL; *cnt = 1; if(root->lchild == NULL && root->rchild == NULL)return root; if(root->lchild != NULL){ lpnode = root; pl = findDeepestNode(root->lchild,&lpnode,&lcnt); } if(root->rchild != NULL){ rpnode = root; pr = findDeepestNode(root->rchild,&rpnode,&rcnt); } if(lcnt > rcnt){ *cnt += lcnt; *pnode = lpnode; return pl; } else{ *cnt += rcnt; *pnode = rpnode; return pr; } }

评论收藏

内容反馈