亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

數組和樹之間的關系

父節點下標*2+1?該節點左
父節點下標*2+2?該節點右

不會啊，我就是按老師的代碼敲的?/************************************************************二叉樹（鏈表表示）課程要求：完成二叉樹的基本操作????1，樹的創建和銷毀????2，樹中結點的搜索????3，樹中結點的添加與刪除????4，樹中結點的遍歷?????????Tree();???//創建樹????~Tree();???????????????//銷毀樹????Node?*SearchNode(Tree?*pTree,int?nodeindex);??//根據索引尋找結點?????bool?AddNode(Tree?*pTree,int?nodeindex,int?direction,Node?*pNode);??//添加結點????bool?DeleteNode(Tree?*pTree,int?nodeindex,Node?*pNode);????????????//刪除結點????void?preorderTraverse();???????????????//先序遍歷二叉樹????void?InorderTraverse();???????????????//中序遍歷二叉樹????void?PosorderTraverse();???????????????//后序遍歷二叉樹?結點要素：索引、數據、左孩子指針、右孩子指針、父結點指針??????????????????3(0)??????????????????5(1)??????????8(2)??????2(3)?????6(4)???9(5)???7(6)?????那個direction是“0”時表示插入到左孩子，是“1”時表示插入到右孩子?先序遍歷結果（根----左----右）0?1?3?4?2?5?6??中序遍歷結果（左----根----右）3?1?4?0?5?2?6????后序遍歷結果（左----右----根）3?4?1?5?6?2?0?*************************************************************/?#include<iostream>#include<stdio.h>?using?namespace?std;?class?Node{public:????Node();//構造函數?????Node?*SearchNode(int?nodeindex);????void?DeleteNode();????void?preorderTraverse();???????????????//先序遍歷二叉樹????void?InorderTraverse();???????????????//中序遍歷二叉樹????void?PosorderTraverse();???????????????//后序遍歷二叉樹????int?index;????int?data;????Node?*pLChild;????Node?*pRChild;????Node?*pParent;????};?class?Tree{public:????Tree();????????????????????????????????//創建樹?????~Tree();???????????????????????????????//銷毀樹?????Node?*SearchNode(int?nodeindex);???????//搜索結點?????bool?AddNode(int?nodeindex,int?direction,Node?*pNode);???//添加結點?????bool?DeleteNode(int?nodeindex,Node?*pNode);??????????????//刪除結點?????void?preorderTraverse();???????????????//先序遍歷二叉樹????void?InorderTraverse();???????????????//中序遍歷二叉樹????void?PosorderTraverse();???????????????//后序遍歷二叉樹private:????Node?*m_pRoot;???};?Node::Node(){????index=0;????data=0;????pLChild=NULL;????pRChild=NULL;????pParent=NULL;????}??Tree::Tree(){????m_pRoot=new?Node();}?Tree::~Tree(){????//DeleteNode(0,NULL);//方法一?????m_pRoot->DeleteNode();//方法二?}?Node?*Node::SearchNode(int?nodeindex){????if(this->index==nodeindex)????????return?this;????Node?*temp=NULL;????if(this->pLChild!=NULL)????{????????if(this->pLChild->index==nodeindex)????????????return?this->pLChild;????????else????????????temp=this->pLChild->SearchNode(nodeindex);?????????????}????if(this->pRChild!=NULL)????{????????if(this->pRChild->index==nodeindex)????????????return?this->pRChild;????????else????????????temp=this->pRChild->SearchNode(nodeindex);????????if(temp!=NULL)????????????return?temp;????}????return?NULL;}?Node?*Tree::SearchNode(int?nodeindex){????return?m_pRoot->SearchNode(nodeindex);}?bool?Tree::AddNode(int?nodeindex,int?direction,Node?*pNode){????Node?*temp=SearchNode(nodeindex);????if(temp==NULL)????????return?false;????Node?*node=new?Node();????if(node==NULL)????????return?false;????node->index=pNode->index;????node->data=pNode->data;?????????node->pParent=temp;????if(direction==0)????????temp->pLChild=node;????if(direction==1)????????temp->pRChild=node;????return?true;}?bool?Tree::DeleteNode(int?nodeindex,Node?*pNode){????Node?*temp=SearchNode(nodeindex);????if(temp==NULL)????????return?false;????if(pNode!=NULL)????{????????pNode->data=temp->data;????}????temp->DeleteNode();????return?true;}?void?Node::DeleteNode(){????if(this->pLChild!=NULL)????????this->pLChild->DeleteNode();????if(this->pRChild!=NULL)????????this->pRChild->DeleteNode();????if(this->pParent!=NULL)????{????????if(this->pParent->pLChild==this)????????????this->pParent->pLChild=NULL;????????if(this->pParent->pRChild==this)????????????this->pParent->pRChild=NULL;????}????delete?this;}?void?Node::preorderTraverse(){????cout?<<?this->index?<<?"???"?<<?this->data?<<?endl;????if(this->pLChild!=NULL)????????this->pLChild->preorderTraverse();????if(this->pRChild!=NULL)????????this->pRChild->preorderTraverse();}??void?Node::InorderTraverse(){????if(this->pLChild!=NULL)????????this->pLChild->InorderTraverse();?????????????cout?<<?this->index?<<?"???"?<<?this->data?<<?endl;?????????if(this->pRChild!=NULL)????????this->pRChild->InorderTraverse();}void?Node::PosorderTraverse(){????if(this->pLChild!=NULL)????????this->pLChild->PosorderTraverse();?????????if(this->pRChild!=NULL)????????this->pRChild->PosorderTraverse();?????????????cout?<<?this->index?<<?"???"?<<?this->data?<<?endl;}?void?Tree::preorderTraverse(){????m_pRoot->preorderTraverse();}??void?Tree::InorderTraverse(){????m_pRoot->InorderTraverse();}??void?Tree::PosorderTraverse(){????m_pRoot->PosorderTraverse();}??int?main(){????Node?*node1=new?Node();????node1->index=1;????node1->data=5;?????????Node?*node2=new?Node();????node2->index=2;????node2->data=8;?????????Node?*node3=new?Node();????node3->index=3;????node3->data=2;?????????Node?*node4=new?Node();????node4->index=4;????node4->data=6;?????????Node?*node5=new?Node();????node5->index=5;????node5->data=9;?????????Node?*node6=new?Node();????node6->index=6;????node6->data=7;?????????Tree?*tree=new?Tree();?????????tree->AddNode(0,0,node1);????tree->AddNode(0,1,node2);?????????tree->AddNode(1,0,node3);????tree->AddNode(1,1,node4);?????????tree->AddNode(2,0,node5);????tree->AddNode(2,1,node6);?????????//printf("刪除最后一個結點：\n");????//tree->DeleteNode(6,NULL);?????????printf("刪除中間某個結點：\n");????tree->DeleteNode(2,NULL);//????printf("前序遍歷的結果：\n");//????tree->preorderTraverse();?????//????printf("中序遍歷的結果：\n");//????tree->InorderTraverse();??????????printf("后序遍歷的結果：\n");????tree->PosorderTraverse();?????delete?tree;????return?0;}

【樹】節點的有限集合

【度】有幾個子節點

【葉子】終端節點

【無序樹】同一節點的幾個子節點可以隨便換順序而不影響邏輯

【深度】：節點深度（不同層不一樣）、樹的深度（所有層里節點的最大深度）

【二叉樹】所有節點的度都≤2

• 遍歷：前序遍歷、中序、后序（前中后是相對于二叉樹的根來說的）

  前（先訪問根，再訪問節點），中（左節點、根、右節點）、后（最后訪問根）

• 用途：壓縮軟件-赫夫曼樹、搜索-人機對戰
  

• 二叉樹的度都小于等于二。
  

• 二叉樹的遍歷是相對于根節點而言的，先訪問根節點則為前序遍歷，后訪問則為后序遍歷，中間訪問則為中序遍歷。

父親節點下標*2+1 該節點左 父親節點下標*2+1 該節點右

關于數組與樹之間的算法轉換

二叉樹表示

二叉樹的遍歷

深度的概念

前序遍歷：根左右

中序遍歷：左根右

后序遍歷：左右根

NULL定義在頭文件stdio.h中

1. 孩子，雙親，度

   
   

2. 什么叫度？

   雙親節點的孩子數稱為度
   

3. 什么叫二叉樹？
   

   所有節點的度<=2